Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
49 - ZOJ Monthly, December 2005 - 1002
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


Submit    Status