문제
민성이는 현대미술을 좋아한다. 오늘도 프랑스 작가 앙데용의 작품 시테니캉을 감상중이다. 이 작품은 격자판에 검은색과 흰색을 번갈아 칠해 놓은 모습인데 상하좌우 어느 인접한 격자도 같은 색이 아닌 형태로 마치 체스보드를 연상하게 한다. 작품을 감상하던 민성이는 작품속에서 등장하는 체스보드는 몇 가지나 될까? 궁금해졌다.
체스보드는 8*8크기에 오른쪽 아래 격자가 흰색이다.
예를 들어 높이는 10이고 너비는 11이며 오른쪽 아래 격자가 검은색인 아래 그림과 같은 작품을 보자. 아래 붉은 실선으로 표시된 것과 같은 체스보드가 모두 6개 구해진다.
민성이가 감상중인 작품 시테니캉의 크기와 오른쪽 아래 격자의 색을 입력받아 가능한 체스보드의 개수는 몇 가지가 있는지 구해보자.
입력
입력은 20개 이하의 테스트 케이스로 이루어지며 테스트 케이스의 마지막은 0 0 0이 입력된다.
각 테스트 케이스는 작품의 높이를 나타내는 H, 너비를 나타내는 W, 그리고 오른쪽 아래 격자의 색을 나타내는 C가 공백으로 구분되어 주어진다. C가 0이면 검은색이고 1이면 흰색이다.
(8 ≤ H, W ≤ 40,000)
출력
각 테스트 케이스에 대하여 각 작품이 포함하고 있는 체스보드의 개수를 행으로 구분하여 출력한다.
테스트 케이스 0 0 0에 대한 결과는 출력하지 않는다.
예제
8 8 0
8 8 1
9 9 1
40000 39999 0
0 0 0
0
1
2
799700028
출처
Ulm local 2007
로그인해야 코드를 작성할 수 있어요.