Busy Beaver tìm thấy một câu đố kỳ lạ. Câu đố bao gồm một chiếc hộp được chia thành lưới ô vuông $N \times M$. Mỗi ô trong lưới là ô bị chiếm dụng (ký hiệu là '#'), ô trống (ký hiệu là '.'), hoặc ô trống nhưng được đánh dấu bằng 'o'.

Câu đố đi kèm với một loạt các mảnh L-tromino, mỗi mảnh tương ứng với một ô 'o' trên lưới. Một mảnh L-tromino được cấu tạo từ ba khối vuông có hình dạng chữ L như hình minh họa. Tâm của L-tromino là ô vuông kề với cả hai ô vuông còn lại (được đánh dấu bằng 'o' trong hình).

Busy Beaver nhận ra rằng để giải câu đố, anh ấy cần xếp tất cả các mảnh L-tromino vào trong hộp sao cho các mảnh L-tromino được căn chỉnh theo lưới, tâm của mỗi L-tromino nằm tại một ô trống được đánh dấu 'o' và không có hai mảnh L-tromino nào chồng lên nhau hoặc chồng lên một ô bị chiếm dụng. Tất cả các mảnh L-tromino có thể được xoay tự do.

Bạn có thể giúp Busy Beaver đếm số cách để giải câu đố không? Vì kết quả có thể rất lớn, hãy xuất ra kết quả theo modulo $10^9 + 7$.

Dữ liệu vào

Mỗi bài kiểm tra chứa nhiều bộ dữ liệu. Dòng đầu tiên chứa số lượng bộ dữ liệu $T$ ($1 \le T \le 500$). Phần mô tả các bộ dữ liệu theo sau.

Dòng đầu tiên của mỗi bộ dữ liệu chứa hai số nguyên $N$ và $M$ ($2 \le N, M \le 1000$), kích thước của lưới.

$N$ dòng tiếp theo, mỗi dòng chứa $M$ ký tự, mô tả một hàng của lưới. Mỗi ký tự là '#', '.', hoặc 'o'.

Đảm bảo rằng tổng $N$ trên tất cả các bộ dữ liệu không vượt quá 1000. Đảm bảo rằng tổng $M$ trên tất cả các bộ dữ liệu không vượt quá 1000.

Dữ liệu ra

Với mỗi bộ dữ liệu, hãy xuất ra một số nguyên duy nhất: số cách để giải câu đố theo modulo $10^9 + 7$.

Nhiệm vụ con

Gọi $(r, c)$ là ô tại hàng $r$ và cột $c$ ($1 \le r \le N, 1 \le c \le M$).

• (10 điểm) Mỗi ô 'o' có khoảng cách Manhattan ít nhất là 3 so với mỗi ô 'o' khác. Nghĩa là, nếu $(r_1, c_1)$ và $(r_2, c_2)$ là hai ô 'o' khác nhau, thì $|r_1 - r_2| + |c_1 - c_2| \ge 3$.
• (30 điểm) Mỗi ô 'o' kề theo chiều dọc với ít nhất một ô 'o' hoặc '#' khác. Nghĩa là, với bất kỳ ô 'o' nào tại $(r, c)$, thì $(r - 1, c)$ hoặc $(r + 1, c)$ là một ô '#' hoặc một ô 'o' khác.
• (60 điểm) Không có ràng buộc bổ sung.

Ví dụ

Dữ liệu vào 1

5
4 5
###.o
.o...
#..o.
#..##
5 5
..###
.o..#
.o.o.
..#o.
###..
8 31
.########.#..oo..o..o#o..o....o
o.######.o#o...o..o..#..o..oo..
o..####.o.#####..########o..###
..o.o..o..#####.o########..o###
.o##..##.o#####o.########..o###
o.##.o##.o#####..########o..###
..######..#..o..o.o..####..o###
.o######o.#o..o..o..o####o..###
2 3
#.o
.o.
2 2
..
..

Dữ liệu ra 1

4
6
1
0
1

Ghi chú

Lưu ý rằng bộ dữ liệu đầu tiên thỏa mãn các ràng buộc cho nhiệm vụ con thứ nhất và bộ dữ liệu thứ hai thỏa mãn các ràng buộc cho nhiệm vụ con thứ hai.

Trong bộ dữ liệu đầu tiên, 4 cách để giải câu đố như hình minh họa:

Trong bộ dữ liệu thứ hai, 6 cách để giải câu đố như hình minh họa:

Trong bộ dữ liệu thứ ba, cách duy nhất để giải câu đố như hình minh họa:

Trong bộ dữ liệu thứ tư, không có cách nào để giải câu đố.

Trong bộ dữ liệu thứ năm, không có ô 'o' nào, vì vậy cách duy nhất để giải câu đố là không đặt bất kỳ mảnh L-tromino nào.