Một sàn nhà kích thước ~M \times N~, được chia thành các hình vuông nhỏ kích thước ~1 \times 1~. Trên đó có một số ô cấm.

Người ta cần lát kín sàn bằng các viên gạch ~1 \times 2~ và ~2 \times 1~, sao cho:

• Không có 2 viên gạch nào chồng lên nhau
• Không có viên gạch nào lát đè lên ô cấm
• Ngoài các ô cấm, tất cả các ô còn lại đều được lát bởi đúng 1 viên gạch

Nhiệm vụ: Bạn được download input là thông tin về 10 sàn nhà. hãy tính số cách lát sàn thỏa mãn các điều kiện trên, và submit 1 code in ra kết quả gồm 10 dòng, mỗi dòng chứa một số nguyên dương duy nhất, là số cách lát sàn nhà thỏa mãn, lấy modulo ~10^{9} + 7~.

Bộ test có thể download ở đây

Input

Dòng đầu chứa số nguyên dương ~T~ ~(1 \leq T \leq 10)~.

Tiếp theo là ~T~ test, mỗi test gồm:

• Dòng đầu chứa 2 số nguyên dương ~M, N~ ~(1 \leq M, N \leq 1000)~.
• Tiếp theo là ~M~ dòng, mỗi dòng gồm đúng ~N~ ký tự. Ký tự ở hàng ~i~, cột ~j~ là '#' nếu ô tương ứng là ô cấm, và '.' trong trường hợp ngược lại.

Output

Gồm ~T~ dòng, mỗi dòng chứa một số nguyên dương duy nhất là số cách lát sàn ~M \times N~ mod ~10^{9} + 7~.

Sample Input

4
5 4
....
.#..
....
....
....

5 4
....
....
....
....
....

5 4
...#
....
....
....
#...

5 5
#####
.....
.....
#####
#####

Sample Output

0
95
23
8