Block Stacking

Time limit2sMemory limit128 MB

Summary
Count A by B height-grids with heights 0 to C that are non-increasing along both rows and columns, modulo 1e18.
Level

Hard8 of 10

Topics
Dynamic programming, Combinatorics, Matrix
Solved
No attempts yet

Problem

There is a rectangular box of size A x B x C. Its base is an A-row by B-column grid, and each cell may contain a vertical stack of 0 to C unit blocks of size 1 x 1 x 1.

The height of every cell must satisfy these conditions.

  1. If a cell has a cell to its left, its height cannot be greater than the height of that left cell.
  2. If a cell has a cell above it, its height cannot be greater than the height of that upper cell.

A cell may also contain no blocks. Given A, B, and C, compute the number of possible block arrangements.

Input

The first line contains three integers A, B, and C.

Output

Print the number of possible block arrangements modulo 1,000,000,000,000,000,000.

Constraints

  • 1 <= A <= 20
  • 1 <= B, C <= 6

Examples1

  1. Example 1

    Input
    1 1 1
    Expected output
    2