题目描述
Background:
After returning from ACM ICPC 2014, Mehta is back with a much greater stamina and enthusiasm to solve much complicated tasks. So, he comes across the following problem.
Task:
You have to report the count of numbers which have the following properties.
-> Their length i.e number of digits in their decimal representation should be less than or equal to N.
-> Count of prime digits i.e 2,3,5,7 modulo 2 should be A,B,C,D respectively, whereas count of other digits may be odd or even.
Input:
First Line of the input contains an integer T denoting the number of test cases.
Each test case consists of single line having five integers N,A,B,C,D separated by a single space as explained in the problem statement.
Output:
Output the answer modulo 10^9 + 7 for each test case in a separate line.
Constraints:
T ≤ 50
1 ≤ N ≤ 10^18
A,B,C,D will all be either 0 or 1 as they are all counts of prime digits modulo 2
Note:
0 is an even number and length of number zero is 1.
SAMPLE INPUT
6
1 0 0 0 0
2 0 0 0 0
3 0 0 0 0
1 0 1 1 0
2 0 1 1 0
3 0 1 1 0
SAMPLE OUTPUT
6
40
288
0
2
36
输入格式
见题面
输出格式
见题面