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

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

題目描述：

一個 7 x n 的格子，一開始會有 4 個人在第一排，

每個人只能往下一排移動，移動的時候往斜上或斜下走，而且四個人不會撞在一起。

問走到最後一排的方法數有多少種。

題目解法：