Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VMTILE - Lát gạch 5

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/vmtile


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 109 + 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 109 + 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

Được gửi lên bởi:VOJ Team
Ngày:2012-07-20
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:TEXT

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.