Tetris

Building the Panama Canal required 20 million hours of human labor. Meanwhile, in the year 2003 alone, people around the world spent 9 billion hours playing computer Solitaire. Sadly, we do not know how much time humanity has devoted to Tetris — but judging from our own experience, we suspect it is a great deal as well.

You are given a rectangular board that is 4 columns wide and $n$ rows tall. The state of every cell in the first row is given. You may use 7 different types of pieces (see the figure), with an unlimited supply of each type. These are the pieces normally used in the game of Tetris. Note, however, that the "long" piece occupies three cells, not four. Pieces may be rotated.

You want to cover the entire board with pieces. Pieces may not overlap one another, may not extend outside the board, and may not cover a cell that is already covered. In how many different ways can the whole board be completely covered?

The first line contains a natural number $d$ ($1 \le d \le 100$) — the number of tests.

Each test consists of two lines. The first line contains an integer $n$ ($1 \le n \le 10^9$) — the height of the board. The second line contains 4 characters describing the first row; each character is either * or .. A * denotes a cell that is already covered, and a . denotes a free cell.

For each test, determine the number of different ways to completely cover the board with the available pieces, and print that value modulo $10^6$, one per line.