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