Aqua는 $r$행 $c$열로 나뉜 직사각형 판에서 하는 논리 퍼즐 게임입니다. 행은 아래에서 위로 $1$부터 $r$까지, 열은 왼쪽에서 오른쪽으로 $1$부터 $c$까지 번호가 붙습니다. $i$행 $j$열의 칸을 $(i,j)$라고 합니다.

판은 수직 및 수평 경계로 여러 개의 상하좌우로 연결된 구역으로 나뉩니다. 정확히 말하면 각 구역은 판의 칸들의 비어 있지 않은 부분집합이고, 각 칸은 정확히 한 구역에 속합니다. 한 구역의 칸들은 연결 요소를 이룹니다. 두 칸이 같은 구역에 속하면 그 구역의 칸들만 지나면서 한 칸에서 다른 칸으로 이동할 수 있으며, 각 이동은 변을 공유하는 인접 칸 사이에서 이루어집니다.

그림 A.1: 6행, 7열, 8개 구역인 판.

퍼즐 제작자는 각 구역의 위쪽 가장자리에서 물을 붓습니다. 중력 때문에 물은 더 낮은 칸으로 떨어집니다. 다음 조건을 모두 만족하도록 물을 붓습니다.

• 각 칸은 완전히 물로 채워지거나 완전히 비어 있습니다.

• 구역은 물로 가득 차거나, 완전히 비거나, 일부만 물로 찰 수 있습니다.

• 각 구역에는 어떤 수위 $\ell$이 있어서 그보다 낮은 구역의 모든 칸은 채워지고, 그보다 높은 모든 칸은 비어 있습니다. 즉, 같은 구역의 두 칸 $(r_1,c_1)$, $(r_2,c_2)$가 $r_1 \le r_2$를 만족할 때, $(r_2,c_2)$가 채워지면 $(r_1,c_1)$도 채워져야 합니다.

• 구역들은 각각 독립적으로 처리합니다. 따라서 위 규칙은 서로 다른 구역의 칸 사이에는 적용되지 않습니다.

다음은 유효한 판의 예입니다.

그림 A.2: 유효한 판.

다음은 유효하지 않은 판들의 예입니다.

그림 A.3: 유효하지 않은 판. 칸 $(5,5)$와 $(5,7)$은 같은 구역의 같은 행에 있으므로 둘 다 채워지거나 둘 다 비어 있어야 합니다.

그림 A.4: 유효하지 않은 판. 칸 $(4,2)$, $(4,3)$, $(4,4)$가 비어 있지만, 물로 채워진 칸 $(5,2)$와 같은 구역에 있습니다.

그림 A.5: 유효하지 않은 판. 칸은 일부만 채워질 수 없습니다.

퍼즐 제작자는 위 규칙뿐 아니라 각 행에서 채워진 칸의 수도 고려합니다. 일부 행에서는 채워진 칸 수가 특정 값이기를 원하며, 다른 행에는 제한을 두지 않습니다.

위의 모든 규칙과 요구를 만족하도록 구역에 물을 붓는 방법의 수를 구하세요. 어떤 칸이 한 방법에서는 채워지고 다른 방법에서는 비어 있을 때, 그리고 그때만 두 방법이 다르다고 합니다.

입력

입력의 첫 줄에는 두 정수 $r,c$($1 \le r,c \le 20$)가 주어집니다. 다음 $r+1$개의 줄은 다음 규칙으로 판을 설명합니다.

• 각 줄에는 정확히 $2\cdot c+1$개의 문자가 있으며, 각각 공백, 밑줄(_), 세로선(|) 중 하나입니다.

• 첫 줄과 마지막 줄의 짝수 인덱스 위치의 문자는 모두 밑줄이며, 판의 위쪽과 아래쪽 테두리를 나타냅니다.

• 위에서 언급한 것 외의 모든 밑줄은 같은 열의 연속한 두 칸 사이의 수평 구역 경계를 나타냅니다.

• 첫 줄을 제외한 모든 줄의 첫 문자와 마지막 문자는 세로선이며, 판의 왼쪽과 오른쪽 테두리를 나타냅니다.

• 위에서 언급한 것 외의 모든 세로선은 같은 행의 연속한 두 칸 사이의 수직 구역 경계를 나타냅니다.

더 잘 이해하려면 예제를 참고하세요.

정의에 따라:

• 같은 열의 연속한 두 칸 사이에 수평 구역 경계가 없으면 두 칸은 같은 구역에 속합니다.

• 같은 행의 연속한 두 칸 사이에 수직 구역 경계가 없으면 두 칸은 같은 구역에 속합니다.

마지막 줄에는 각 행의 채워진 칸 수의 요구를 나타내는 $r$개의 정수 $x_1,x_2,\ldots,x_r$($-1 \le x_i \le c$)가 주어집니다. $x_i=-1$이면 $r-i+1$번째 행에는 임의의 수의 칸이 물로 채워져도 됩니다. 그렇지 않으면 그 행의 채워진 칸 수가 정확히 $x_i$여야 합니다.

판의 구역 수는 최대 20개임이 보장됩니다.

출력

주어진 조건을 만족하는 유효한 판의 수를 $10^9+7$로 나눈 나머지를 정수 하나로 출력하세요.

예제

입력 1

6 7
 _ _ _ _ _ _ _ 
| |  _ _|  _  |
| | |_ _| |_| |
| |_ _ _|  _ _|
| |  _ _| |   |
| | |_ _| |   |
|_|_ _ _|_|_ _|
6 3 7 2 2 2

출력 1

1

참고

첫 예제는 위의 그림 A.2에 해당합니다.

입력 2

2 3
 _ _ _ 
|     |
|_ _ _|
-1 -1

출력 2

3

입력 3

3 3
 _ _ _ 
|  _  |
| | | |
|_|_|_|
-1 1 1

출력 3

1