Giải bài trực tuyến

Một sàn nhà kích thước M*N, được chia thành các hình vuông nhỏ kích thước 1*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*2 và 2*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 file text 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⁹ + 7.

Input

Dòng đầu chứa số nguyên dương T (1 ≤ T ≤ 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 ≤ M, N ≤ 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.

Bộ test có thể download ở: link

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*N mod 10⁹ + 7.

Chấm điểm

Trong quá trình thi, chương trình của bạn sẽ được chấm với 5 test đầu tiên. Trong quá trình thi, điểm mà bạn nhận được thể hiện phần trăm test mà bạn giải đúng trong số 5 test này (trên thang điểm 100).

Example

Input:
4
5 4
....
.#..
....
....
....

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

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

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

Output:
0
95
23
8