LOTS of rectangles

We have a square on a plane.
First, we divide it into four equal smaller squares, as shown in the figure below.

4-square

Then, each of those squares is again divided into four equal smaller squares:

16-square

We repeat this subdivision process exactly K times in total.

Your task is to determine how many rectangles appear in the resulting figure after all subdivisions.
Since the number can be very large, output the result modulo $1, 000, 000, 009$ .

Constraints

$1 \leq K \leq 1, 000, 000, 000$

Input Format

The first line contains an integer $T$ — the number of test cases.
Each of the following lines contains a single integer $K$ — the number of subdivision steps.

Output Format

Output $T$ lines. On the $i$ -th line, print "Case #i: num", where $n u m$ is the number of rectangles after $K$ subdivisions, modulo $1, 000, 000, 009$ .

Example

Input

Output

Case #1: 9
Case #2: 100
Case #3: 356250848

Explanation

See the picture for all the possible rectangles when $K = 1$ :

sample