配点 : 600 点
問題文
正整数 N,M が与えられます。ただし、N≤M≤2N が保証されます。
i=1∑NSi=M を満たす全ての正整数列 S=(S1,S2,…,SN) について以下の値を求め、
その総和を素数 200 003 で割った余りを出力してください (通常とは異なる mod の値に注意してください)。
- k=1∏Nmin(k,Sk)
制約
- 1≤N≤1012
- N≤M≤2N
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
答えを整数として出力せよ。
3 5
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 について k=1∏Nmin(k,Sk) の値を求めると、
- S=(1,1,3) : 1×1×3=3
- S=(1,2,2) : 1×2×2=4
- S=(1,3,1) : 1×2×1=2
- S=(2,1,2) : 1×1×2=2
- S=(2,2,1) : 1×2×1=2
- S=(3,1,1) : 1×1×1=1
となるため、その総和である 14 を出力します。
1126 2022
40166
総和を 200 003 で割った余りを出力してください。
1000000000000 1500000000000
180030