던전 마스터

아주 먼 옛날, 어느 판타지 세계에서 몬스터들은 모험가들을 위해 동굴과 던전을 팠다. 몬스터들은 모험가들이 목표에 도달하는 과정을 더 어렵고 더 흥미진진하게 만들기 위해 동굴에 장애물을 몇 개 놓았다.

어느 날 동굴에 사는 몬스터 중 하나인 에밀스는 동굴에 관한 의문을 품었다. 장애물의 위치를 바꾸어 동굴을 몇 가지 모양으로 만들 수 있을까?

의문의 내용은 이러하다. 동굴은 W × H개의 칸으로 이루어진다. 몬스터들은 일부 칸에 장애물을 놓아 모험가들이 그 칸으로 들어가지 못하게 할 수 있다. 장애물의 총 개수는 정해져 있고, 한 칸에 장애물이 두 개 이상 있을 수는 없다. 모험가들은 동굴의 왼쪽 위 칸에서 들어와 오른쪽 아래 칸에 도달하려 한다. 모험가들은 목적지 칸에 장애물이 없으면 한 칸에서 인접한 네 칸 중 어느 곳으로든 이동할 수 있다. 장애물이 없는 두 칸 사이에는 항상 경로가 하나 이상 있어야 한다. 왼쪽 위 칸과 오른쪽 아래 칸에는 장애물이 없어야 한다. 문제는 동굴의 너비 W와 높이 H, 장애물의 개수 S가 주어졌을 때 몬스터들이 만들 수 있는 동굴의 모양이 몇 가지인지 구하는 것이다. 장애물은 모양이 같으므로 서로 구별하지 않는다.

아주 흥미로운 수학 문제였다. 에밀스는 혼자서 이 문제를 풀지 못해 동료들에게 물어보았다. 그러나 아무도 답을 하지 못했다. 그 뒤 이 문제는 동굴에서 일하는 몬스터들 사이에서 빠르게 퍼졌고, 결국 몬스터들은 항상 이 문제만 생각하느라 잠을 제대로 이루지 못하게 되었다.

여러분은 이 문제의 답을 구하는 프로그램을 작성해야 한다.

입력은 한 줄로 이루어지며, 공백으로 구분된 세 정수 W, H, S가 주어진다. W와 H는 동굴의 가로와 세로 크기이고, S는 동굴에 놓을 장애물의 개수이다. 2 ≤ W, H ≤ 8이고 0 ≤ S ≤ W × H임이 보장된다.

동굴의 모양이 몇 가지인지 한 줄에 출력한다.