Танхаус, часовщик в городе Винден, делает необычные часы, измеряющие время в \(h\) часах, пронумерованных от \(0\) до \(h-1\). Однажды он решил сделать из таких часов загадку.
Загадка состоит из таблицы размера \(n \times m\) с часами, где каждые часы показывают какой-то час ровно (то есть время не лежит между двумя ровными часами). За один ход он может выбрать строку или столбец и перевести все часы в строке или столбце на час вперед\(^\dagger\).
Таблица с часами называется решаемой, если можно сделать так, чтобы все часы показывали одно и то же время.
При создании закагки Танхаус вдруг забеспокоился, что, возможно, его загадка не получится решаемой. В некоторых клетках таблицы уже находятся часы, которые показывают определенное время, а некоторые клетки еще пустые.
Вам дана частично заполненная таблица с часами, найдите количество способов\(^\ddagger\) заполнить пустые клетки часами так, чтобы таблица была решаемой. Так как ответ может быть большим, выведите его по модулю \(10^9 + 7\).
\(^\dagger\) Если часы показывают \(t\) часов, и их переводят на час вперед, они будут показывать \((t+1) \bmod h\) часов.
\(^\ddagger\) Два способа считаются различными, если существует клетка с часами, в двух способах показывающими различное время.
Выходные данные
Для каждого набора входных данных выведите число способов заполнить пустые клетки таблицы так, чтобы загадка была решаемой. Так как ответ может быть большим, выведите его по модулю \(10^9 + 7\).
Примечание
В первом примере например подходит следующая конфигурация часов:
Она решаемая, например, так:
- Перевести часы в среднем столбце на час.
- Перевести часы в третьем столбце на час.
- Перевести часы в третьем столбце на час.
- Перевести часы во второй строке на час.
После этого все часы показывают один час.
Во втором примере можно показать, что нет решаемых конфигураций.