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.