Informatica Online Judge

  Bingo Card [0551 / 0227]

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


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[]

Background

I am coder 프로그래밍 컨테스트에는 경기 후 GSHS학생들은 따로 모여 뒷풀이로 빙고게임을 한다.
하지만 그 빙고 게임에서 사용되는 빙고카드는 조금 독특해서 다음과 같은 규칙이 있다고 한다.

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

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

1 18 26 35 41
3 19 27 36 43
4 20 30 37 44
7 23 31 39 46
11 24 33 40 47



뒷풀이 놀이 빙고에서 사용될 카드를 되도록이면 많이 만들고 싶다. 단 동일한 카드를 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

입출력예시1의 설명

가능한 경우는 다음값 뿐이다.

1 4 7
2 5 8
3 6 9

그 외에
1 2 3
4 5 6
7 8 9

는 불가능하다. 1,2의 값은 2인데 왼쪽열에 벌써 2보다 큰 4, 7이 있으므로 이 케이스는 아니다.

따라서 답은 1

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