Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2630
Plane Partition

Time Limit: 2 Seconds      Memory Limit: 65536 KB

A plane partition is a two-dimensional array of integers ni,j that are nonincreasing both from left to right and top to bottom. In other words,

ni,j <= ni,j+1
ni,j <= ni+1,j

Implicit in this definition is the requirement that the array be flush on top and to the left and contain no holes.

For example, one plane partition of 22 is illustrated above and the corresponding two-dimensional array is

5 4 2 1 1
3 2 0 0 0
2 2 0 0 0

Now given 3 integers a, b, c, how many plane partitions whose diagrams fit inside an a * b rectangle and whose heights do not exceed c(in other words, with all ni,j <= c)?

Input

Each line contains 3 integers - a, b, c(0 < a, b, c <= 6). The input ends with EOF.

Output

Output the total number in one line for each test case.

Sample Input

1 1 1
2 2 2
3 3 3

Sample Output

2
20
980


Author: ZHANG, Zheng
Source: ZOJ Monthly, December 2005
Submit    Status