F	Finding Paths in Grid

Given a grid having 7 columns. 4 players will start there journey in that grid. Initially all of them are in first row. A player can move diagonally to the next row. For example, a player is in row 3 and column 4, which can also be represented as (3,4), this player has only two valid moves, (4,3) and (4,5). But If the player is in (3, 1), he has only one valid move, which is (4,2). In there journey, any cell of the grid can not be visited more than one player.

In this problem you have to find, in how many ways all of the players can reach to row N.

Input

The first line of input is an integer T (T<100) that indicates the number of test cases. Each case starts with a line containing only 1 integer N (1≤N≤1000000000), followed by a line having 7 integers (r₁ to r₇), which will represent the state of first row. r_i = 0 represents that, there is no player in row i, otherwise r_i will represent the player number. Player numbers will be between 1 to 4.

Output

For each case, output the number of ways to reach row N. You have to give your output modulo 1000000007.

Sample Input Output for Sample Input

3 1 1 0 2 0 3 0 4 2 1 0 2 0 3 0 4 2 1 2 3 4 0 0 0

1 0 3

Problem Setter : Md. Arifuzzaman Arif
Special Thanks : Abdullah Al Mahmud