마법소녀(홀수 퍼즐) timer 1s memory 64MB

마법 소녀 정인이는 악의 세력으로부터 지구를 지키는 화이트 마녀이다. 지구의 여러 곳을 순찰하던 정인이는 어느 날 전설로 내려오는 고대 마법의 주문이 적힌 석판을 발견하였다. 

그러나 아쉽게도 석판에 적힌 일부(또는 전부) 문자들이 지워져 있었다.

석판은 직사각형 모양이었고 각 격자(행과 열이 교차하는 곳)에는 숫자가 있거나 숫자가 있었던 흔적이 있었다. 

전설에 따르면 각 격자에는 1에서 9까지의 숫자 중에 하나가 적혀있었으며 각 열에서는 임의의 연속한 H개의 숫자의 합이 홀수이고, 

각 행에서는 임의의 연속한 W개의 숫자의 합이 홀수였다고 한다.   예를 들어 석판의 크기가 2행 2열 이고 석판의 상태가 아래와 같다고 하자. 편의상 지워진 자리는 ‘.’으로 표시한다. 21 1. 그리고 W와 H가 2, 2라고 할 경우 아래와 같이 4가지 경우를 생각할 수 있다.

2 1   2 1   2 1   2 1

1 2,  1 4,  1 6,  1 8

정인이가 발견한 고대 마법의 석판 정보가 주어진다. 석판을 복원할 때 나올 수 있는 경우 수를 구하는 프로그램을 작성하시오.