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