Migrated from Lutece 1474 Bob and Alice are eating food

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Bob likes eating food very much.His girl friend Alice likes too.

On the table there are six types of food:apples,pears,peaches,bananas,oranges and lemons.

Bob and his girl friend Alice are different people.They wants to eat exactly k pieces food.

And they wants to eat exactly even pieces apples and even pieces pears.Others are no limits.

So do you know how many different ways to eat these food?

Input

First line is a positive integer $T$ , represents there are $T$ test cases.

For each test case:

First line includes a number k(1<=k<=1e15),means Bob want to eat k pieces fruits.

Output

For the $i$-th test case , first output Case #i: in a single line.

Then output the answer mod 1e9+7 of $i$-th test case.

Samples

3
1
2
3

Case #1: 4
Case #2: 18
Case #3: 88

Resources

“玲珑杯”ACM比赛 Round #2