문제 설명

어느 프로그래밍 대회에서는 뒤풀이 파티에서 빙고 게임을 하는 관습이 있다. 단, 이 빙고 게임에서 사용하는 빙고 카드는 조금 특수하며, 다음 조건에 따라 만들어진다.

• 빙고 카드는 $N$행 $N$열의 칸으로 나누어져 있으며, 각 칸에는 양의 정수가 $1$개씩 적혀 있다. 그 정수들은 모두 다르다.
• 각 칸에 적혀 있는 정수는 $1$ 이상 $M$ 이하이다.
• 빙고 카드에 적혀 있는 $N \times N$개의 정수의 합은 $S$이다.
• 어느 열을 보더라도, 위에서 아래로 향하면서 정수가 오름차순으로 나열되어 있다.
• 어느 칸의 정수든, 그 칸보다 왼쪽 열에 있는 어떤 정수보다도 크다.

아래는 $N = 5$, $M = 50$, $S = 685$일 때의 빙고 카드의 예이다.

뒤풀이 파티를 위해 위의 조건을 만족하는 빙고 카드를 가능한 한 많이 만들고 싶다. 단, 동일한 카드를 $2$장 이상 만들어서는 안 된다. 만들 수 있는 빙고 카드의 최대 장수를 $100000$으로 나눈 나머지를 출력하는 프로그램을 작성하시오.

입력

입력은 $1$줄로 이루어지며, 그 줄에는 빙고 카드의 크기 $N$ ($1 \le N \le 7$), 칸에 적혀 있는 정수의 상한 $M$ ($1 \le M \le 2000$), 빙고 카드에 적혀 있는 정수의 합 $S$ ($1 \le S \le 3000$)를 나타내는 $3$개의 양의 정수가 공백으로 구분되어 적혀 있다. 단, 주어지는 모든 입력 데이터에서 조건을 만족하는 빙고 카드를 $1$장 이상 만들 수 있다.

출력

만들 수 있는 빙고 카드의 최대 장수를 $100000$으로 나눈 나머지를 $1$줄로 출력하시오.

예제 1

입력

3 9 45

출력

1

예제 2

입력

3 100 50

출력

7

예제 3

입력

5 50 685

출력

74501

보충 설명

예제 $3$에 대하여, 만들 수 있는 빙고 카드의 최대 장수는 $642499974501$장이므로, $100000$으로 나눈 나머지인 $74501$을 출력한다.