Aqua adalah permainan teka-teki logika yang dimainkan pada papan persegi panjang yang dibagi menjadi $r$ baris dan $c$ kolom. Baris-barisnya dinomori dari $1$ hingga $r$ dari bawah ke atas, dan kolom-kolomnya dinomori dari $1$ hingga $c$ dari kiri ke kanan. Sel pada baris ke-$i$ dan kolom ke-$j$ dinyatakan sebagai $(i,j)$.

Papan dibagi menjadi beberapa kandang (area) yang terhubung secara ortogonal menggunakan batas vertikal dan horizontal. Lebih tepatnya, setiap kandang adalah himpunan bagian tak kosong dari sel-sel papan. Setiap sel pada papan termasuk dalam tepat satu kandang. Himpunan sel dari sebuah kandang membentuk satu komponen terhubung: Jika dua sel termasuk dalam kandang yang sama, selalu mungkin untuk berpindah dari satu sel ke sel lainnya hanya dengan melewati sel-sel dari kandang tersebut, sehingga setiap langkah adalah perpindahan antar sel yang bersebelahan sisi.

Gambar A.1: Papan dengan 6 baris, 7 kolom, dan 8 kandang.

Di setiap kandang, pembuat teka-teki menuangkan air dari tepi atas kandang. Karena gravitasi, air jatuh ke sel-sel pada ketinggian yang lebih rendah. Ia menuangkan air sedemikian rupa sehingga memenuhi semua ketentuan di bawah ini:

• Setiap sel terisi penuh dengan air atau sepenuhnya kosong.

• Sebuah kandang dapat terisi penuh dengan air, sepenuhnya kosong, atau terisi sebagian.

• Di setiap kandang, terdapat suatu batas ketinggian air $\ell$ sedemikian sehingga semua sel di bawah batas ini pada kandang tersebut terisi penuh, dan semua sel di atas batas ini pada kandang tersebut kosong. Dengan kata lain, misalkan $(r_1,c_1)$ dan $(r_2,c_2)$ adalah dua sel pada kandang yang sama dengan $r_1 \le r_2$; jika sel $(r_2,c_2)$ terisi penuh, maka sel $(r_1,c_1)$ juga harus terisi penuh.

• Setiap kandang diperlakukan secara independen dan terpisah. Oleh karena itu, aturan di atas tidak berlaku untuk sel-sel yang termasuk dalam kandang yang berbeda.

Berikut adalah contoh papan yang valid:

Gambar A.2: Sebuah papan yang valid.

Berikut adalah beberapa contoh papan yang tidak valid:

Gambar A.3: Papan yang tidak valid — sel $(5,5)$ dan $(5,7)$ seharusnya sama-sama terisi penuh atau sama-sama kosong, karena keduanya berada di kandang yang sama dan pada baris yang sama.

Gambar A.4: Papan yang tidak valid — sel $(4,2)$, $(4,3)$, dan $(4,4)$ kosong, tetapi berada di kandang yang sama dengan sel $(5,2)$ yang terisi air.

Gambar A.5: Papan yang tidak valid — sel tidak boleh hanya terisi sebagian.

Pembuat teka-teki tidak hanya mengikuti aturan di atas, tetapi juga memperhatikan banyaknya sel yang terisi pada setiap baris. Pada beberapa baris, ia ingin banyaknya sel yang terisi sama dengan nilai tetap tertentu, sementara tidak memberikan batasan apa pun pada baris lainnya.

Tugas Anda adalah menghitung banyaknya cara menuangkan air ke dalam kandang-kandang yang memenuhi semua aturan dan persyaratan di atas. Dua cara dianggap berbeda jika dan hanya jika terdapat sebuah sel yang terisi pada satu cara, tetapi kosong pada cara lainnya.

Masukan

Baris pertama masukan berisi dua bilangan bulat $r,c$ ($1 \le r,c \le 20$). Sebanyak $r+1$ baris berikutnya mendeskripsikan papan sesuai dengan aturan berikut:

• Setiap baris berisi tepat $2\cdot c+1$ karakter, yang masing-masing berupa salah satu dari berikut ini: spasi, garis bawah (_), atau garis vertikal (|).

• Semua karakter pada posisi indeks genap di baris pertama dan baris terakhir adalah garis bawah, yang menunjukkan batas atas dan batas bawah papan.

• Setiap garis bawah pada masukan, kecuali yang disebutkan di atas, merepresentasikan batas kandang horizontal antara dua sel berurutan pada kolom yang sama.

• Karakter pertama dan terakhir dari semua baris (kecuali baris pertama) adalah garis vertikal, yang menunjukkan batas kiri dan batas kanan papan.

• Setiap garis vertikal pada masukan, kecuali yang disebutkan di atas, merepresentasikan batas kandang vertikal antara dua sel berurutan pada baris yang sama.

Lihat contoh untuk pemahaman yang lebih baik.

Berdasarkan definisi:

• Jika tidak ada batas kandang horizontal antara dua sel berurutan dalam suatu kolom, kedua sel ini termasuk dalam kandang yang sama.

• Jika tidak ada batas kandang vertikal antara dua sel berurutan dalam suatu baris, kedua sel ini termasuk dalam kandang yang sama.

Baris terakhir berisi $r$ bilangan bulat $x_1,x_2,\ldots,x_r$ ($-1 \le x_i \le c$) yang mendeskripsikan persyaratan mengenai banyaknya sel yang terisi pada setiap baris. Jika $x_i=-1$, baris ke-($r-i+1$) dapat memiliki sembarang banyaknya sel berisi air. Jika tidak, banyaknya sel yang terisi pada baris ini harus tepat $x_i$.

Dijamin bahwa papan memiliki paling banyak 20 kandang.

Keluaran

Keluaran berisi tepat satu bilangan bulat — banyaknya papan valid yang memenuhi kondisi yang diberikan, modulo $10^9+7$.

Contoh

Masukan 1

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

Keluaran 1

1

Catatan

Contoh pertama sesuai dengan Gambar A.2 di atas.

Masukan 2

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

Keluaran 2

3

Masukan 3

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

Keluaran 3

1