Трехцветные шахматы
시간 제한2초메모리 제한256 MB
일부 칸의 색이 정해진 n x m 격자를 인접한 칸끼리 다른 색이 되도록 세 가지 색으로 칠하는 경우의 수를 1e9+7로 나눈 나머지로 구합니다.
문제
Один из членов жюри Russian Code Cup решил изобрести трехцветные шахматы – сложную и увлекательную модификацию классических шахмат. Примечательной особенностью этой игры является измененное игровое поле. Оно состоит из n × m клеток, каждая из которых покрашена в один из трех цветов: черный, белый или серый. При этом любые две клетки, имеющие общую сторону, покрашены в различные цвета.
Прежде чем перейти к разработке дальнейших правил, он решил выяснить, насколько удастся разнообразить игру, определяя раскраску игрового поля.
Рассмотрим макет игрового поля, на котором для некоторых клеток известен цвет в который они покрашены, остальные же клетки требуется покрасить в один из трех цветов.
Требуется найти количество игровых полей соответствующих заданному макету. Ответ требуется вывести по модулю 109+7. Игровые поля отличающиеся только поворотом или отражениям считаются различными. Гарантируется что в макете нету двух соседних клеток, уже покрашенных в одинаковый цвет.
입력
Первая строка содержит два целых числа n и m (1 ≤ n ≤ 14, 1 ≤ m ≤ 50) – размеры макета Каждая из следующих n строк содержит по m символов, соответствующих клеткам макета.
출력
Выведите количество игровых полей, соответствующих заданному макету, по модулю 109+7.