mehta-and-the-difficult-task-3

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

Source: hackerearth | Difficulty: HARD
Tags: Dynamic programming

Matrices

Mathematics


Solutions: