아름다운 홀수 배열

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

배열 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에 대해 A[r][c]가 1 이상 9 이하다.

일부 칸이 비어 있는 미완성 배열 A가 주어진다. 빈 칸마다 1 이상 9 이하의 수를 하나씩 적어 넣어 배열을 완성한다. 이렇게 만들 수 있는 아름다운 홀수 배열이 몇 개인지 구하라. 완성한 배열이 한 칸이라도 다르면 서로 다른 배열로 센다.

첫째 줄에 네 자연수 N, M, H, W가 주어진다. (1 ≤ N, M ≤ 50, 1 ≤ H ≤ min(N, 10), 1 ≤ W ≤ min(M, 10))

다음 N개 줄에는 미완성 배열 A의 정보가 한 줄에 M개씩 공백으로 구분되어 주어진다. i+2번째 줄의 j+1번째 수가 A[i][j]이고, 그 칸이 비어 있으면 0이 주어진다. 비어 있지 않은 칸에 적힌 수는 1 이상 9 이하다.

미완성 배열 A에서 만들 수 있는 아름다운 홀수 배열의 개수를 1,000,000,007로 나눈 나머지를 첫째 줄에 출력한다. 하나도 만들 수 없으면 0을 출력한다.

빈 칸에 홀수를 적어야 한다면 1, 3, 5, 7, 9 중 하나를 고르고, 짝수를 적어야 한다면 2, 4, 6, 8 중 하나를 고른다.