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