How many integer sequences of length
N,
A = (A1,…,AN), satisfy all given below conditions?
1) 1 <= A
i <= M (1 <= i <= N)
2)
\(\sum\limits_{i=1}^NA_i \le K\)
Input
The input is a string containing three integers
N,
M (1 <= N, M <= 50), K (N <= K <= NM).
Imprint
Output the answer to the problem.
Examples
| # |
Input |
Output |
Explanations |
| 1 |
2 3 4
|
6
|
(1,1) (1,2) (1,3) (2,1) (2,2) (3,1) |