/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
正整数 N,M が与えられます。ただし、N\leq M \leq 2N が保証されます。
\displaystyle \sum_{i=1}^{N} S_i = M を満たす全ての正整数列 S=(S_1,S_2,\dots,S_N) について以下の値を求め、 その総和を素数 200\ 003 で割った余りを出力してください (通常とは異なる \bmod の値に注意してください)。
- \displaystyle \prod_{k=1}^{N} \min(k,S_k)
制約
- 1 \leq N \leq 10^{12}
- N \leq M \leq 2N
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
答えを整数として出力せよ。
入力例 1
3 5
出力例 1
14
条件を満たす S は、 S=(1,1,3), S=(1,2,2), S=(1,3,1), S=(2,1,2), S=(2,2,1), S=(3,1,1) の 6 つです。
それぞれの S について \displaystyle \prod_{k=1}^{N} \min(k,S_k) の値を求めると、
- S=(1,1,3) : 1\times 1 \times 3 = 3
- S=(1,2,2) : 1\times 2 \times 2 = 4
- S=(1,3,1) : 1\times 2 \times 1 = 2
- S=(2,1,2) : 1\times 1 \times 2 = 2
- S=(2,2,1) : 1\times 2 \times 1 = 2
- S=(3,1,1) : 1\times 1 \times 1 = 1
となるため、その総和である 14 を出力します。
入力例 2
1126 2022
出力例 2
40166
総和を 200\ 003 で割った余りを出力してください。
入力例 3
1000000000000 1500000000000
出力例 3
180030
Score : 600 points
Problem Statement
You are given positive integers N and M. Here, it is guaranteed that N\leq M \leq 2N.
Print the sum, modulo 200\ 003 (a prime), of the following value over all sequences of positive integers S=(S_1,S_2,\dots,S_N) such that \displaystyle \sum_{i=1}^{N} S_i = M (notice the unusual modulo):
- \displaystyle \prod_{k=1}^{N} \min(k,S_k).
Constraints
- 1 \leq N \leq 10^{12}
- N \leq M \leq 2N
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M
Output
Print the answer as an integer.
Sample Input 1
3 5
Sample Output 1
14
There are six sequences S that satisfy the condition: S=(1,1,3), S=(1,2,2), S=(1,3,1), S=(2,1,2), S=(2,2,1), S=(3,1,1).
The value \displaystyle \prod_{k=1}^{N} \min(k,S_k) for each of those S is as follows.
- S=(1,1,3) : 1\times 1 \times 3 = 3
- S=(1,2,2) : 1\times 2 \times 2 = 4
- S=(1,3,1) : 1\times 2 \times 1 = 2
- S=(2,1,2) : 1\times 1 \times 2 = 2
- S=(2,2,1) : 1\times 2 \times 1 = 2
- S=(3,1,1) : 1\times 1 \times 1 = 1
Thus, you should print their sum: 14.
Sample Input 2
1126 2022
Sample Output 2
40166
Print the sum modulo 200\ 003.
Sample Input 3
1000000000000 1500000000000
Sample Output 3
180030