블록 쌓기

크기가 A x B x C인 직육면체 공간이 있다. 바닥은 A행 B열 격자이고, 각 칸에는 0개 이상 C개 이하의 1 x 1 x 1 블록을 수직으로 쌓을 수 있다.

각 칸의 높이는 다음 조건을 만족해야 한다.

1. 왼쪽 칸이 있는 경우, 현재 칸의 높이는 왼쪽 칸의 높이보다 클 수 없다.
2. 위쪽 칸이 있는 경우, 현재 칸의 높이는 위쪽 칸의 높이보다 클 수 없다.

블록을 하나도 놓지 않는 칸도 허용된다. A, B, C가 주어질 때 가능한 블록 배치의 수를 구하시오.

첫째 줄에 세 정수 A, B, C가 주어진다.

가능한 블록 배치의 수를 1,000,000,000,000,000,000으로 나눈 나머지를 출력한다.

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