Pumpkins and Tombstones (part 3)

Note: This problem statement is identical to part 2, but has a higher limit on N.

We are setting up a Halloween decoration in our front yard, which consists of carved pumpkins and tombstones. Here are our decoration rules:

The Halloween decoration is 1 or more slots long.
Zero or more of these slots are occupied by pumpkins.
There are $E \leq 10$ types of pumpkin eyes (denoted by the first $E$ digits from 0-9).
There are $M \leq 10$ types of pumpkin mouths (denoted by the first $M$ letters from A-J).
Two pumpkins in adjacent slots must have the same type of eyes, the same type of mouth, or both.
All the other slots are occupied by tombstones.
No two tombstones can be adjacent to each other.

We record a decoration in string form by looking at slots from the first to the last, and writing down a T if the slot has a tombstone, and the pumpkin's eyes and mouth type (e.g., 2B) if the slot has a pumpkin.

Two decorations are different if their string records are different.

Our decoration is going to be $N$ slots long and contain exactly $K$ tombstones. Calculate the number of different decorations that exist under these constraints and our rules. Because this number can be extremely large, output it modulo $1, 000, 000, 009$ .

Input

The first line contains an integer $T$ - the number of test cases.

Each of the following $T$ lines contains four numbers $N$ , $K$ , $E$ , $M$ - the number of slots, tombstones, eye types, and mouth types, respectively.

$1 \leq N \leq 1, 000, 000$
$0 \leq K \leq N$
$1 \leq E \leq 10$
$1 \leq M \leq 10$

Output

For each test case, print a single line Case #i: num, where num is the number of different Halloween decorations with $N$ slots, exactly $K$ of which are tombstones, and pumpkins use $E$ types of eyes and $M$ types of mouths.

Examples

Input

Output

Case #1: 4
Case #2: 4
Case #3: 56
Case #4: 482220929

Explanation

Case 1. The Halloween decoration has 2 slots, one of which needs to be a tombstone. Pumpkins have 1 type of eyes and 2 types of mouths. Here are the 4 decorations that follow the rules:

T0A
T0B
0AT
0BT

Case 2. The Halloween decoration has 2 slots, both of which must be pumpkins. Pumpkins have 1 type of eyes and 2 types of mouths. Here are all the possible decorations that follow the rules:

0A0A
0A0B
0B0A
0B0B

Case 3. The Halloween decoration has 3 slots, 2 of which must be tombstones. Pumpkins have 8 types of eyes and 7 types of mouths. The tombstones must be placed in the leftmost and rightmost slot (otherwise we'll end up with two adjacent tombstones), which leaves us $8 \cdot 7$ options for the pumpkin in the middle.

Case 4. Don't forget to calculate the result modulo $1, 000, 000, 009$ !