Contest Duration: - (local time) (100 minutes) Back to Home
Ex - Sum of Prod of Min /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

\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 について \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


### 入力例 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