Busy Beaver는 이상한 퍼즐을 발견했습니다. 이 퍼즐은 $N \times M$ 격자로 나누어진 상자로 구성되어 있습니다. 격자의 각 칸은 점유되어 있거나('#'), 비어 있거나('.'), 또는 비어 있지만 'o'로 표시되어 있습니다.

이 퍼즐에는 여러 개의 L-트로미노 조각이 포함되어 있으며, 격자의 각 'o' 칸마다 하나씩 대응됩니다. L-트로미노는 그림과 같이 L자 모양의 세 개의 정사각형 블록으로 구성됩니다. L-트로미노의 중심은 다른 두 정사각형과 인접한 정사각형(그림에서 'o'로 표시됨)입니다.

Busy Beaver는 퍼즐을 풀기 위해 모든 L-트로미노를 상자 안에 배치해야 합니다. 이때 L-트로미노는 격자에 맞춰져야 하며, 각 L-트로미노의 중심은 'o'로 표시된 빈 칸에 위치해야 하고, 두 L-트로미노가 서로 겹치거나 점유된 칸과 겹쳐서는 안 됩니다. 모든 L-트로미노는 자유롭게 회전할 수 있습니다.

Busy Beaver가 퍼즐을 푸는 방법의 수를 세도록 도와줄 수 있을까요? 정답이 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력하세요.

입력

각 테스트는 여러 개의 테스트 케이스를 포함합니다. 첫 번째 줄에는 테스트 케이스의 수 $T$ ($1 \le T \le 500$)가 주어집니다. 그 뒤를 이어 각 테스트 케이스에 대한 설명이 나옵니다.

각 테스트 케이스의 첫 번째 줄에는 격자의 크기를 나타내는 두 정수 $N$과 $M$ ($2 \le N, M \le 1000$)이 주어집니다.

다음 $N$개의 줄에는 각각 $M$개의 문자가 주어지며, 이는 격자의 한 행을 나타냅니다. 각 문자는 '#', '.', 또는 'o'입니다.

모든 테스트 케이스에 대해 $N$의 합은 1000을 넘지 않습니다. 모든 테스트 케이스에 대해 $M$의 합은 1000을 넘지 않습니다.

출력

각 테스트 케이스마다 퍼즐을 푸는 방법의 수를 $10^9 + 7$로 나눈 나머지를 한 줄에 하나씩 출력하세요.

서브태스크

$(r, c)$를 $r$행 $c$열의 칸이라고 합시다 ($1 \le r \le N, 1 \le c \le M$).

• (10점) 각 'o' 칸은 다른 모든 'o' 칸으로부터 맨해튼 거리가 최소 3 이상 떨어져 있습니다. 즉, $(r_1, c_1)$과 $(r_2, c_2)$가 서로 다른 두 'o' 칸이라면, $|r_1 - r_2| + |c_1 - c_2| \ge 3$입니다.
• (30점) 각 'o' 칸은 최소한 하나의 다른 'o' 칸 또는 '#' 칸과 수직으로 인접해 있습니다. 즉, $(r, c)$에 있는 임의의 'o' 칸에 대해, $(r - 1, c)$ 또는 $(r + 1, c)$ 중 하나는 '#' 칸이거나 다른 'o' 칸입니다.
• (60점) 추가 제약 조건 없음.

예제

예제 입력 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
..
..

예제 출력 1

4
6
1
0
1

참고

첫 번째 테스트 케이스는 첫 번째 서브태스크의 제약 조건을 만족하며, 두 번째 테스트 케이스는 두 번째 서브태스크의 제약 조건을 만족합니다.

첫 번째 테스트 케이스에서 퍼즐을 푸는 4가지 방법은 다음과 같습니다:

두 번째 테스트 케이스에서 퍼즐을 푸는 6가지 방법은 다음과 같습니다:

세 번째 테스트 케이스에서 퍼즐을 푸는 유일한 방법은 다음과 같습니다:

네 번째 테스트 케이스에서는 퍼즐을 푸는 방법이 없습니다.

다섯 번째 테스트 케이스에는 'o' 칸이 없으므로, 퍼즐을 푸는 유일한 방법은 L-트로미노를 하나도 배치하지 않는 것입니다.