Description

Minesweeper is Libra's favourite game.

A mine-sweeper map can be expressed as an $n\times m$ grid. Each cell of the grid is either a mine cell or a non-mine cell. A mine cell has no number on it. Each non-mine cell has a number representing the number of mine cells around it.

Now, Libra and Rahn are playing mine-sweeper on a $3\times N$ grid, where all cells in row 2 are no-mine cells. And they have got the number on each cell in row 2.

Libra and Rahn want to find out the number of ways to set the mines in row 1 and row 3 vaildly.

Format

Input

The first line contains one integer $T(1\le T\le 100)$ --- the number of test cases.

Each test case consists of one string with length $N(1\le N\le 10000)$, consisting of numbers, representing that the grid has 3 rows and $N$ columns. The $i$-th number in the string represents the number in row 2, column $i$ of the grid.

Output

For each test case, print a single number representing the answer. Since the answer may be large, you need to print the answer modulo $10^9+7$.

Samples

2
22
000

6
1