Problem Description
On the last day before the famous mathematician Swan's death, he left a problem to the world: Given integers n and ai for 0≤i≤4, calculate the number of n-digit integers which have at most ai-digit i in its decimal representation (and have no 5,6,7,8 or 9). Leading zeros are not allowed in this problem.
Input
There is one integer T (1<T≤10) in the beginning of input, which means that you need to process T test cases. In each test case, there is one line containing six integers representing n and a0 to a4, where 2≤n≤15000 and 0≤ai≤30000.
Output
For each test case, you should print first the identifier of the test case and then the answer to the problem, module 109+7.
Sample Input
10
5 0 1 2 3 4
5 1 1 1 1 1
5 2 2 2 2 2
5 3 3 3 3 3
5 3 2 1 3 2
5 3 2 0 0 0
5 0 0 0 5 0
7000 41 2467 6334 2500 3169
7000 7724 3478 5358 2962 464
7000 5705 4145 7281 827 1961
Sample Output
Case #1: 535
Case #2: 96
Case #3: 1776
Case #4: 2416
Case #5: 1460
Case #6: 4
Case #7: 1
Case #8: 459640029
Case #9: 791187801
Case #10: 526649529