409558: GYM103630 J Рудольф и разноцветная таблица

J. Рудольф и разноцветная таблицаограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Рудольфу в руки попала занятная прямоугольная таблица из $$$N$$$ строк и $$$M$$$ столбцов, каждая ячейка которой окрашена в определенный цвет. А занятной эта таблица оказалась, поскольку в ней можно менять местами цвета соседних ячеек. Соседними считаются ячейки, имеющие общую сторону.

Рудольф долго развлекался с таблицей, хаотично обменивая цвета ячеек. В конце концов ему стало интересно, а сколько разных таблиц можно получить, сделав некоторое количество (возможно $$$0$$$) обменов. Две таблицы считаются разными, если отличаются цветом хотя бы одной ячейки.

Вычислите для Рудольфа ответ на его вопрос. Так как ответ может быть очень большим, посчитайте его остаток от деления на $$$10^9 + 7$$$

Входные данные

Первая строка входных данных содержит два целых числа $$$N$$$ и $$$M$$$ $$$(1 \le N, M \le 100)$$$ — размеры таблицы.

Далее идут $$$N$$$ строк по $$$M$$$ чисел $$$C_{i, j} (1 \le C_{i, j} \le 10^5)$$$ — цвет ячейки в $$$i$$$-й строке и $$$j$$$-м столбце.

Выходные данные

Выведите одно целое число — количество разных таблиц, которые может получить Рудольф, по модулю $$$10^9 + 7$$$

ПримерыВходные данные

2 1
3
4

Выходные данные

2

Входные данные

2 2
5 4
4 5

Выходные данные

6