Aqua は $r$ 行 $c$ 列に分けられた長方形の盤面で遊ぶ論理パズルです。行は下から上へ $1$ から $r$、列は左から右へ $1$ から $c$ と番号が付いています。$i$ 行 $j$ 列のマスを $(i,j)$ と表します。
盤面は縦と横の境界によって、上下左右に連結な複数の区画に分けられています。正確には、各区画は盤面のマスの空でない部分集合です。各マスはちょうど 1 つの区画に属します。区画のマス集合は連結成分をなします。同じ区画に属する 2 マスの間は、その区画のマスだけを通り、毎回辺を共有する隣接マスへ移動することで行き来できます。
図 A.1：6 行、7 列、8 区画の盤面。
パズルの作成者は各区画の上端から水を注ぎます。重力によって、水は高さが低いマスに落ちます。次のすべての条件を満たすように注ぎます。
各マスは完全に水で満たされるか、完全に空です。
区画は水で満杯、完全に空、または一部だけ水で満たされた状態にできます。
各区画にはある水位 $\ell$ があり、それより下のすべてのマスは満たされ、それより上のすべてのマスは空です。言い換えると、同じ区画の 2 マス $(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：無効な盤面。マスを部分的に満たすことはできません。
パズルの作成者は上記の規則だけでなく、各行の満たされたマス数にも注意します。一部の行では満たされたマス数を固定値にしたいと考え、他の行には制約を設けません。
すべての規則と要求を満たす区画への水の注ぎ方の数を数えてください。一方の方法では満たされ、もう一方では空であるマスが存在する場合に限り、2 つの方法は異なるとみなします。
入力
入力の最初の行には 2 つの整数 $r,c$（$1 \le r,c \le 20$）が含まれます。続く $r+1$ 行は次の規則で盤面を表します。
各行はちょうど $2\cdot c+1$ 文字からなり、各文字は空白、アンダースコア（
_）、縦棒（|）のいずれかです。最初の行と最後の行の偶数添字位置の文字はすべてアンダースコアで、盤面の上と下の境界を表します。
上記以外のすべてのアンダースコアは、同じ列の連続する 2 マス間の横方向の区画境界を表します。
最初の行を除く各行の最初と最後の文字は縦棒で、盤面の左と右の境界を表します。
上記以外のすべての縦棒は、同じ行の連続する 2 マス間の縦方向の区画境界を表します。
理解のため入出力例を参照してください。
定義により：
同じ列の連続する 2 マス間に横方向の区画境界がなければ、2 マスは同じ区画に属します。
同じ行の連続する 2 マス間に縦方向の区画境界がなければ、2 マスは同じ区画に属します。
最後の行には、各行の満たされたマス数への要求を表す $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 個として出力してください。
入出力例
入力 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