Lucky Tickets

Every bus and train ticket issued in the Soviet Union had an identifier with an even number of digits, 2N. Many places in Russia and Kazakhstan still use identifiers of this form. A ticket is lucky when the sum of the first N digits of its identifier equals the sum of the last N digits.

An identifier is a string of 2N digits from 0 to 9, and identifiers whose first digit is 0 are included.

Many children believe that eating such a ticket brings them good luck.

Given N, count the lucky tickets.

The first line contains the number of test cases T. ($1 \le T \le 100$)

Each of the next T lines contains one integer N. A ticket identifier has 2N digits. ($1 \le N \le 500$)

For each test case, print one line that starts with Case #i: and then gives the number of lucky tickets whose identifier has 2N digits. Here i is the test case number, counted from 1. The counts grow large quickly, so print each of them modulo 1000000007 ($10^9 + 7$).