You are given a grid with 7 columns and N rows (numbered from 1 to N). 4 players will start their journey in that grid. Initially all of them are in the 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 their journey, any cell of the grid cannot be visited by more than one player.

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

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case contains an integer N (1 ≤ N < 2³¹) in a line. The next line will contain 7 integers, which 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. You can assume that there will be exactly 4 players and are numbered from 1 to 4.

For each case, print the case number and number of ways to reach the N^th row. You have to print the result modulo 1000000007 (10⁹ + 7).