Олимпиадный тренинг

Задача 40064. Последовательности длины N


Сколько целых последовательностей длины N, A = (A1,…,AN), удовлетворяют всем приведенным ниже условиям?
1) 1 <= Ai <= M (1 <= i <= N)
2)\(\sum\limits_{i=1}^NA_i \le K\)

Входные данные
На вход подается строка, содержащая три целых числа N, M (1 <= N, M <= 50), K (N <= K <= NM).

Выходные данные
Выведите на ответ на задачу.
 
Примеры
Входные данные Выходные данные Пояснения
1
2 3 4
6
(1,1) (1,2) (1,3) (2,1) (2,2) (3,1)