Informatica Online Judge

  빙고 [0242 / 00F2]

Time Limit(Test case) : 5000(ms)
Number of users who solved : 17   Total Tried : 26


The Champion of this Problem (C++) : t1234 - 70ms / 323byte
My Best Submission (C++) : N/A

[]

Background

어느 프로그래밍 컨테스트에는 경기 후 뒷풀이로 빙고게임을 하는 경우가 있다고 한다. 하지만 그 빙고 게임에서 사용되는 빙고카드는 조금 독특해서 다음과 같은 규칙이 있다고 한다.

- 빙고카드는 N행 N열의 격자로 구성되고, 각 격자에는 정수값이 하나씩 적혀있다. 이들 정수는 모두 다른값이다.
- 격자에 적힌 정수는 1이상 M이하이다.
- 빙고카드에 적힌 N*N개의 정수의 합은 S이다.
- 어떤 열이라도 위에서부터 아래로는 오름차순으로 정렬되어있다.
- 임의의 어떤 칸의 값으로 부터 왼쪽 열의 모든 값은 현재 칸의 값보다 적다.


다음은 N=5, M=50, S=685인 한 빙고카드의 예이다.




뒷풀이 놀이 빙고에서 사용될 카드를 되도록이면 많이 만들고 싶다. 단 동일한 카드를 2장이상 만들면 안된다. 만들수 있는 카드의 수를 100,000으로 나눈 나머지를 출력하는 프로그램을 작성하시오.

Input

첫번째 줄에는 카드의 크기 N(1<=N<=7)이 입력되고 각 눈에 적힌 정수의 상한값 M(1<=M<=2000), 빙고카드에 적힌 정수의 합 S(1<=S<=3000)를 나타내는 정수 3개가 공백으로 구분되어 입력된다. 단 주어진 조건으로 아무리 적어도 빙고카드를 1장 이상은 만들 수 있다.

Output

만들수 있는 빙고카드의 수을 100,000으로 나눈 나머지를 출력하시오.

IO Example

입출력예시1>
입력
3 9 45

출력
1


입출력예시2>
입력
5 50 685

출력
74501

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]