Informatica Online Judge

  KMO 토끼 [2096 / 0830]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 7   Total Tried : 12


The Champion of this Problem (C++) : gs17003 - 0ms / 2410byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]
Writer ID : [gs16103]

Background


머리가 상당히 많이 좋은 현우는 2014년에 벌써 고등부 KMO 1차 시험을 보러 갔다. ( 이것
은 출제자의 생각이기 때문에, 사실 여부는 아무도 모른다. 아마 현우도 모를 것이다. )

현우는 토끼를 많이 좋아하기 때문에 "Rabbit"의 첫 글자에 해당하는 "R", 그리고 R이 18번째 알파벳이기 때문에, 현우는 18번 문제부터 풀려고 한다. 18번 문제는 다음과 같다.

「 18. 정수를 원소로 하는 집합 S에 대하여 S+1을 집합 { k+1 | k ∈ S }라 하자. 집합 { 1, 2, 3, …, 10 } 의 공집합이 아닌 부분집합 K 중 K = S∪(S+1) 을 만족하는 집합 S가 존재하는 것의 개수를 구하여라. 」

이 문제를 본 현우는 "O!" 라는 생각을 하였고, 현우의 마음속에서 자유롭게 살고 있는 M마리의 토끼들에게 문제의 조건을 만족하는 K들을 각

각 1개씩 나누어주고 싶어졌다.

하지만 토끼들의 수가 너무 많기 때문에, 모든 토끼들에게 다 나누어줄 수는 없다.

그래서 위의 집합 { 1, 2, 3, …, 10 } 을 { 1, 2, 3, …, N } 으로 확장시키려고 한다. ( N은 10 이상 )

그러면 K로 가능한 경우가 많아질 것이다. 하지만, 그래도 모든 토끼에게 K를 전부 나누어 줄 수 없을 수도 있다.

이 때, 토끼에게 K들을 각각 하나씩 나누어 주는 방법의 수를 구하여라.

만약, 토끼가 5마리 있고, K로 가능한 것이 3개이면 답은 5×4×3 으로 60인 것이다.

단, N과 M이 커짐에 따라, 방법이 너무 많을 수 있으므로 1,000,003로 나눈 나머지를 구하여라.

아 맞다, 토끼를 매우 좋아하는 현우는 모든 토끼의 이름을 알고 있다. ( 당연히, 전부 다르다. )

Input

첫 줄의 테스트 케이스의 개수 T가 주어진다. ( 1 ≤ T ≤ 10000 )
2번째 줄부터 T+1번째 줄까지 매 줄에 집합의 최대원소 N과, 토끼의 수 M이 주어진다.
( 10 ≤ N ≤ 10,000,000,000 , 200 ≤ M ≤ 10,000,000,000 )

Output

T개의 줄에 각각, 테스트 케이스에 해당하는 토끼에게 집합 K들을 각각 1개씩 나누어주는 방법의 수를 1,000,003으로 나눈 나머지를 출력한다.

IO Example

입력 1
3
10 10000
10 10000201
10 1000202

출력 1
899815
0
411985

입력 2
1
10 200

출력 2
396754

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