問題文

正整数 $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