업그레이드

업그레이드

평소 게임을 즐겨하는 종현이는 이번에 자신이 하던 게임에 “아이템 업그레이드” 시스템이 도입되어 이를 이용해 보려 한다. 종현이는 N개의 서로 다른 아이템을 가지고 있고, 이 아이템들은 모두 1부터 M단계까지의 등급이 존재한다. 아이템을 업그레이드에 필요한 강화석을 한 개 사용하면 아이템의 등급이 1만큼 증가한다. 즉, i등급의 아이템에 강화석을 한 개 이용하여 업그레이드하면 i+1등급이 된다. 강화석을 사용하면 아이템은 무조건 업그레이드가 되지만, 만약 어떤 아이템이 M등급이라면 이미 최고 등급이기 때문에 더 이상 강화석을 사용할 수 없다. 종현이는 최대 M등급까지 존재하는 서로 다른 N개의 1등급 아이템을 가지고 있을 때, K개의 강화석을 모두 사용하여 만들 수 있는 아이템 등급의 경우는 몇 가지인지 구하는 프로그램을 작성하시오. 단, 경우의 수가 많을 수 있으므로 100,000,123으로 나눈 나머지를 구하도록 한다. 만약 강화석을 남김없이 사용할 수 없는 경우엔 -1을 출력하도록 한다.

 

예제1) N = 3, M = 3, K = 4인 경우 총 6가지의 경우가 존재한다.

 

 

예제2)

N = 3, M = 3, K = 10인 경우

1,2,3번 아이템에 강화석을 2개씩 사용하여 모두 최대등급인 3등급 아이템으로 만들어도 강화석이 남기 때문에 이와 같은 경우 강화석을 모두 사용할 수 없다. 즉, -1을 출력한다.

 

 

[제한조건]

1. 최초 N개의 아이템의 등급은 모두 1등급이다.

2. K개의 강화석을 남김없이 사용하여야만 하며, 강화석을 남김없이 사용할 수 없는 경우엔 -1을 출력하도록 한다.

 

[입력]

최초 테스트케이스의 개수 T가 주어지며, 다음 줄부터 T개의 테스트 케이스가 주어진다. 각 테스트 케이스마다 아이템의 개수 N (1 ≤ N ≤ 100,000), 아이템의 최대 등급 M(max(1, K/10) ≤ M ≤ 100,000), 강화석의 개수 K (1 ≤ K ≤ 100,000) 가 각각 공백을 주고 주어진다

[출력]

각각의 테스트 케이스에 대하여 #x (x는 테스트 케이스 번호, 1부터 시작)을 출력하고 공백을 하나 둔 다음, 경우의 수를 100,000,123으로 나눈 나머지를 출력한다. 만약 모든 아이템을 업그레이드 시키고도 강화석이 남는 경우엔 -1을 출력한다.

 

 

[입출력예제]

입력

10

3 3 4

20 10 5

7 22 11

11 10 99

10 13 30

19 708 46

904 98 96

780 230 5

8 46 455

97 25673 4125

 

출력

#1 6

#2 42504

#3 12376

#4 1

#5 80701684

#6 60946391

#7 85772738

#8 60187269

#9 -1

#10 78074709