빙고 게임

어떤 프로그래밍 대회에서는 경기가 끝나면 뒤풀이로 빙고 게임을 하는 독특한 관습이 있습니다. 이 빙고 게임에서 쓰는 "빙고 표"는 보통 빙고와 달리, 아래 조건을 모두 만족하도록 빈 칸을 채워야 합니다.

• 빙고 표는 $N$행 $N$열의 칸으로 이루어지고, 각 칸에는 정수 하나가 적혀 있습니다. 적힌 정수는 모두 서로 다릅니다.
• 각 칸에 적힌 정수는 $1$ 이상 $M$ 이하입니다.
• $N \times N$개의 정수의 총합은 $S$입니다.
• 모든 열은 위에서 아래로 내려갈수록 값이 커집니다(각 열이 오름차순).
• 어떤 칸의 정수는 그 칸보다 왼쪽에 있는 열들의 모든 정수보다 커야 합니다.

예를 들어 $N = 5$, $M = 50$, $S = 685$일 때 위 조건을 만족하는 빙고 표를 적어도 하나는 만들 수 있습니다. (각 열을 위에서 아래로 읽으면 값이 증가하고, 각 열의 값은 그 왼쪽 열들의 모든 값보다 큽니다.)

뒤풀이에 참석하려는 사람이 많아 최대한 많은 빙고 표를 만들려고 합니다. 다만 모든 사람이 자신만의 표를 원하므로 완전히 같은 표를 두 개 이상 만들 수는 없습니다. 만들 수 있는 서로 다른 빙고 표의 최대 개수를 $100000$으로 나눈 나머지를 출력하세요.

입력은 한 줄이며, 세 정수 $N$, $M$, $S$가 공백으로 구분되어 주어집니다. $N$은 빙고 표의 크기($1 \le N \le 7$), $M$은 칸에 적을 수 있는 정수의 최댓값($1 \le M \le 2000$), $S$는 표에 적힌 모든 정수의 총합($1 \le S \le 3000$)입니다.

주어지는 모든 입력에 대해, 조건을 만족하는 빙고 표를 적어도 하나는 만들 수 있음이 보장됩니다.

만들 수 있는 서로 다른 빙고 표의 최대 개수를 $100000$으로 나눈 나머지를 한 줄에 출력하세요.

예를 들어 $N = 5$, $M = 50$, $S = 685$인 경우 만들 수 있는 빙고 표는 모두 $642499974501$개이며, 이를 $100000$으로 나눈 나머지는 $74501$입니다.