시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 21 18 14 82.353%

## 문제

All bus and train tickets in Soviet Union had an identifier with an even number of digits (2*N). In many places in Russia and Kazakhstan there are tickets still like this. A ticket is called lucky if the sum of the first half of the digits of its identifier is equal to the sum of its last half of the digits​.

Many children believe that if you eat such ticket, something good will happen to you.

Let’s find out how many lucky tickets exist!

## 입력

The first line is the number of test cases T (1 <= T <= 100).

Each of the following T lines contains one integer number N (where 2N is the number of digits in the ticket’s identifier and 1 <= N <= 500);

## 출력

For ith test case print a line containing: "Case #i: " followed by the number of lucky tickets with 2N­digit identifiers. The numbers get quite large soon so print the numbers modulo 1000000007 (10^9 + 7).

## 예제 입력 1

3
1
2
7


## 예제 출력 1

Case #1: 10
Case #2: 670
Case #3: 331247783