atcoder#ABC279H. [ABC279Ex] Sum of Prod of Min

[ABC279Ex] Sum of Prod of Min

配点 : 600600

問題文

正整数 N,MN,M が与えられます。ただし、NM2NN\leq M \leq 2N が保証されます。

i=1NSi=M\displaystyle \sum_{i=1}^{N} S_i = M を満たす全ての正整数列 S=(S1,S2,,SN)S=(S_1,S_2,\dots,S_N) について以下の値を求め、 その総和を素数 200 003200\ 003 で割った余りを出力してください (通常とは異なる mod\bmod の値に注意してください)。

  • k=1Nmin(k,Sk)\displaystyle \prod_{k=1}^{N} \min(k,S_k)

制約

  • 1N10121 \leq N \leq 10^{12}
  • NM2NN \leq M \leq 2N
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

NN MM

出力

答えを整数として出力せよ。

3 5
14

条件を満たす SS は、 $S=(1,1,3), S=(1,2,2), S=(1,3,1), S=(2,1,2), S=(2,2,1), S=(3,1,1)$ の 66 つです。

それぞれの SS について k=1Nmin(k,Sk)\displaystyle \prod_{k=1}^{N} \min(k,S_k) の値を求めると、

  • S=(1,1,3)S=(1,1,3) : 1×1×3=31\times 1 \times 3 = 3
  • S=(1,2,2)S=(1,2,2) : 1×2×2=41\times 2 \times 2 = 4
  • S=(1,3,1)S=(1,3,1) : 1×2×1=21\times 2 \times 1 = 2
  • S=(2,1,2)S=(2,1,2) : 1×1×2=21\times 1 \times 2 = 2
  • S=(2,2,1)S=(2,2,1) : 1×2×1=21\times 2 \times 1 = 2
  • S=(3,1,1)S=(3,1,1) : 1×1×1=11\times 1 \times 1 = 1

となるため、その総和である 1414 を出力します。

1126 2022
40166

総和を 200 003200\ 003 で割った余りを出力してください。

1000000000000 1500000000000
180030