기근
시간 제한2초메모리 제한1024 MB
n×m 격자에서 고정된 칸을 지키면서 모든 2×2 정사각형에 굶는 도시와 먹는 도시가 두 개씩 있도록 배치하는 경우의 수를 10^9+7로 나눈 나머지로 구합니다.
문제
셋째 인을 떼셨을 때 나는 셋째 생물이 "와서 보라" 하고 말하는 소리를 들었다.
내가 보니 검은 말이 있었고, 그 위에 저울을 손에 든 기수가 타고 있었다.
네 생물 사이에서 한 음성이 들렸다. "밀 한 되가 데나리온 한 닢, 보리 세 되가 데나리온 한 닢이다. 기름과 포도주는 해치지 마라."
요한계시록
세상 끝이 얼마 남지 않았지만, 요한계시록의 셋째 기수인 기근은 어느 도시를 벌하고 어느 도시를 벌하지 않을지 아직 정하지 못했다. 그래서 그는 작은 나라 하나에서 먼저 연습하기로 했다.
이 나라는 크기의 격자이며, 각 칸이 도시 하나다. 기근은 도시에 기근을 내리거나 그냥 살려 둘 수 있다. 식량이 다음 종말까지 버틸 만큼 있는 도시는 기근이 굶주리게 만들 수 없고, 애초에 식량이 없던 도시는 어떤 경우에도 굶주린다.
심판은 공정해야 하므로, 모든 크기의 정사각형 안에서 굶주리는 도시와 배부른 도시의 수가 같아야 한다. 기근이 도시를 굶주리는 쪽과 배부른 쪽으로 나누는 서로 다른 방법의 수를 구하라.
입력
첫 줄에 정수 과 이 주어진다 (). 나라의 크기다. 이어서 각각 개의 문자로 이루어진 개의 줄이 주어진다. '+'는 해당 도시가 굶주릴 수 없다는 뜻이고, '-'는 해당 도시가 어떤 경우에도 굶주린다는 뜻이며, '.'는 기근이 그 도시를 어떻게 할지 정할 수 있다는 뜻이다.
출력
기근이 내릴 수 있는 서로 다른 배치의 수를 로 나눈 나머지를 출력한다.