문제
도형이는 최근에 M×N(1 ≤ M ≤ 12, 1 ≤ N ≤ 12)짜리 땅을 샀다. 도형이는 여기에 목장을 만들기 위해 한 칸 씩 격자모양으로 우리를 만들려고 한다. 그런데 땅이 울퉁불퉁해서 땅의 일부분에는 우리를 만들 수 없다.
소들은 사이가 별로 좋지 않아서 서로 인접한 우리에 넣어두면 싸움을 한다는 사실을 알게 되었다. 그래서 도형이는 인접하지 않는 우리에만 소들을 배치하기로 했다. 도형이는 이렇게 소들을 배치할 수 있는 방법이 모두 몇 가지인지 궁금해졌다.
소들을 한 마리도 배치하지 않는 것도 한 가지의 방법으로 포함을 시키고 소들을 배치할 수 있는 방법이 몇 가지인지 구하는 프로그램을 작성해 보자.
입력
첫 번째 줄에 공백으로 구분된 두 정수 M과 N이 입력된다. 이후 M개의 줄에 N개의 수가 공백으로 구분되어 입력된다.
1은 우리를 만들 수 있는 땅을 나타내고, 0은 만들 수 없는 땅을 나타낸다.
출력
도형이가 택할 수 있는 경우의 수를 1억으로 나눈 나머지를 출력한다.
예제
2 3
1 1 1
0 1 0
9
힌트
태그
로그인해야 코드를 작성할 수 있어요.