시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 5 2 2 40.000%

문제

세로 크기가 N이고, 가로 크기가 M인 2차원 배열이 있다. A[i][j](0 <= i < N, 0 <= j < M)는 i번 줄, j번 칸에 적힌 수이다.

배열 A가 아래 세 조건을 만족하면 아름다운 홀수 배열이다.

  1. 0 <= r <= N-H, 0 <= c < M 인 모든 정수 r,c에 대해, A[r][c]+A[r+1][c]+...+A[r+H-1][c] 가 홀수
  2. 0 <= r < N, 0 <= c <= M-W 인 모든 정수 r,c에 대해, A[r][c]+A[r][c+1]+...+A[r][c+W-1] 가 홀수
  3. 0 <= r < N, 0 <= c < M 인 모든 정수 r,c에 대해, 1 <= A[r][c] <= 9

일부 칸이 비어있는 미완성 2차원 배열 A가 주어진다. 비어있는 칸에 적절히 수를 적어넣어 배열 A를 아름다운 홀수 배열로 만들 수 있다. 이 때, 배열 A에서 만들 수 있는 아름다운 홀수 배열의 개수를 구하자.

입력

첫 줄에 네 자연수 N,M,H,W가 주어진다. (1 <= N, M <= 50, 1 <= H <= min(N,10), 1 <= W <= min(M,10)) 다음 N개의 줄에 걸쳐 미완성 2차원 배열 A에 대한 정보가 공백으로 구분되어 주어진다. i+2번째 줄에 j-1 번째로 주어지는 수는 A[i][j]이며, 만약 그 칸이 비어있으면 0이 주어진다.

출력

미완성 2차원 배열 A에서 만들 수 있는 아름다운 홀수 배열의 개수를 출력한다. 단, 답이 매우 커질 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력

2 2 2 2
1 2
2 0

예제 출력

5

힌트

비어있는 칸에 들어갈 수 있는 수는 1,3,5,7,9 이다.

출처