문제
진흥이는 학교의 임원으로 환경개선을 위해 학교 담장을 여러 가지 색깔로 예쁘게 색칠하는 중이다.
지금 색칠하는 부분을 N * M개의 같은 크기의 직사각형 모양으로 나누어서 여러 가지 색깔로 각각의 위치를 칠하려고 한다.
이미 다른 색이 일부 칠해져 있고 이번에는 노란색을 칠할 차례이다.
노란색은 어떤 곳이든 여러 곳에 칠할 수 있지만 어떤 한 곳에 칠해지면 그 곳을 중심으로 상하좌우에는 같은 색을 칠해서는 안된다.
물론 노란색을 아예 칠하지 않을 수도 있다.
진흥이는 문득 현재 상태에서 노란색을 칠할 수 있는 방법이 몇가지나 되는지 궁금해졌다.
처음부터 한가지씩 세어보다가 너무 많아서 그냥은 셀 수 없다는 것을 알게 되었다.
진흥이를 위해 노란색을 칠할 수 있는 방법이 몇 가지인지 계산하는 프로그램을 작성하라.
입력
첫 번째 줄에는 색칠을 해야하는 담장의 크기 N과 M이 입력된다. (1 <= N, M <= 15)
다음 줄부터 N줄에 걸쳐 M개의 한 자리 정수가 입력되는데 담장의 상태를 나타낸다.
0은 아직 칠해지지 않은 부분이고 다른 수들은 지금까지 칠해진 색을 의미한다.
출력
노란색을 칠할 수 있는 방법이 몇 가지인지 경우의 수를 구하여 10007로 나눈 나머지를 출력한다.
각 테스트 케이스에 대한 배점 정보와, 제약 조건은 다음과 같다.
•그룹1, 총 10점 상당의 테스트 케이스로 구성되어 있다. N = 1이다.
•그룹2, 총 20점 상당의 테스트 케이스로 구성되어 있다. N = 2이다.
•그룹3, 총 50점 상당의 테스트 케이스로 구성되어 있다. 3 <= N <= 10을 만족한다.
•그룹3, 총 20점 상당의 테스트 케이스로 구성되어 있다. 추가적인 제약 조건이 없다.
예제
2 3
1 0 0
0 0 0
12
힌트
로그인해야 코드를 작성할 수 있어요.