题目描述
NS is a cigarettes lover. If he feels hungry, he will take out some cigarettes and eat them. If he feels bored, he will take out some cigarettes and play them.
Oneday, he find a magic thing -- he can make digits with cigarettes. That is to say he can make numbers. What a fantastic thing! Then he make the standard format: use 7 cigarettes to make the digit "8", other digits can be obtained from the digit "8" by removing some cigarettes. You can get more infomation from the picture.
NS has n cigarettes. Now he want to know how many different numbers he can make with m kinds of digits.
NOTE:
1.NS should use all cigarettes.
2.NS use cigarettes to make specified digits only.
3.NS numbers with leading zero are not counted.
NS has n cigarettes. Now he want to know how many different numbers he can make with m kinds of digits.
NOTE:
1.NS should use all cigarettes.
2.NS use cigarettes to make specified digits only.
3.NS numbers with leading zero are not counted. 输入
The first line is integer T(T <= 100), the number of test cases.The first line of each case contains two integer n and m(1 <= n <= 1000000000, 1 <= m <= 10), n is the number of cigarettes, m is the number of specified digits.The next line contans m integers: a1, a2, a3...am(0 <= ai <= 9).
输出
For each case, print the case number and the answer. The answer may be very large, just output the the remainder of dividing the answer to the problem by 1000000007 (10^9 + 7).
You can get more in sample output.
样例输入 Copy
5
3 1
7
4 2
1 4
6 4
1 3 6 9
8 2
0 1
7 10
0 1 2 3 4 5 6 7 8 9
样例输出 Copy
Case 1: 1
Case 2: 2
Case 3: 3
Case 4: 2
Case 5: 12