The farmer AnhDQ grows flower in his MxN garden (M rows and N columns). He wants to grow flower satisfying that: Each row of the garden has at least k color(s) of flower; and he has 7 types of flower: red, orange, yellow, green, blue, indigo, and violet to use.

Request

Count the number of ways to grow flower on his garden.

Input

- Contains several lines, there are three number M, N, k on each.

Output

- Contains the answer for each line of Input, mod 2370823708, written on separate lines.

Example

Input:
1 7 7

Output:
5040

Limitations

- 1 ≤ M, N ≤ 10¹⁵.
- The number of lines in Input does not exceed 5000.