22111번 - Трехцветные шахматы 다국어

Один из членов жюри Russian Code Cup решил изобрести трехцветные шахматы – сложную и увлекательную модификацию классических шахмат. Примечательной особенностью этой игры является измененное игровое поле. Оно состоит из n × m клеток, каждая из которых покрашена в один из трех цветов: черный, белый или серый. При этом любые две клетки, имеющие общую сторону, покрашены в различные цвета.

Прежде чем перейти к разработке дальнейших правил, он решил выяснить, насколько удастся разнообразить игру, определяя раскраску игрового поля.

Рассмотрим макет игрового поля, на котором для некоторых клеток известен цвет в который они покрашены, остальные же клетки требуется покрасить в один из трех цветов.

Требуется найти количество игровых полей соответствующих заданному макету. Ответ требуется вывести по модулю 10⁹+7. Игровые поля отличающиеся только поворотом или отражениям считаются различными. Гарантируется что в макете нету двух соседних клеток, уже покрашенных в одинаковый цвет.

Первая строка содержит два целых числа n и m (1 ≤ n ≤ 14, 1 ≤ m ≤ 50) – размеры макета Каждая из следующих n строк содержит по m символов, соответствующих клеткам макета.

Выведите количество игровых полей, соответствующих заданному макету, по модулю 10⁹+7.