Прямоугольную таблицу, состоящую из N строк и M столбцов, раскрашивают следующим образом. Каждый столбец таблицы и каждую строку красят либо в синий, либо в желтый цвет. В итоге клетки, оказавшиеся на пересечении синего столбца и синей строки оказываются синими, желтого столбца и желтой строки — желтыми, а клетки на пересечении синего столбца и желтой строки, или, наоборот, желтого столбца и синей строки — зелеными.
Раскраска всех клеток таблицы (или просто сама таблица) называется правильной, если она может быть получена описанным выше способом.
Вам дана прямоугольная таблица, которую нужно раскрасить таким образом. Про некоторые клетки известно, какого цвета они должны быть, а остальные клетки могут в итоге быть любого цвета. Определите, сколько существует различных правильных таблиц, в которых нужные клетки покрашены в нужный цвет.
Входные данные
Вводятся числа N и M — количество строк и столбцов таблицы (1≤N≤30, 1≤M≤30). Далее записано N строк по M чисел в каждой, задающие цвета, в которые должны быть окрашены клетки:
0 — клетка может в итоге быть любого цвета
1 — клетка должна быть синей
2 — клетка должна быть желтой
3 — клетка должна быть зеленой
Выходные данные
Выведите одно число — количество различных правильных таблиц, в которых нужные клетки покрашены в нужный цвет. Обратите внимание, что если два или более способов раскраски столбцов и строк таблицы приводят к одинаковой раскраске самой таблицы, то это нужно считать как один вариант раскраски таблицы (см. пример 2).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4
1 0 0 0
3 0 0 0
0 0 0 0
|
16
|
|
2
|
2 2
3 3
3 3
|
1
|
|
3
|
2 2
2 2
2 3
|
0
|