| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 96 | 69 | 56 | 69.136% |
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 2Ndigit identifiers. The numbers get quite large soon so print the numbers modulo 1000000007 (10^9 + 7).
3 1 2 7
Case #1: 10 Case #2: 670 Case #3: 331247783