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