题目描述
正整数 N,M が与えられます。ただし、N≤ M ≤ 2N が保証されます。
i=1∑N Si = M を満たす全ての正整数列 S=(S1,S2,…,SN) について以下の値を求め、 その総和を素数 200 003 で割った余りを出力してください (通常とは異なる mod の値に注意してください)。
- k=1∏N min(k,Sk)
输入格式
入力は以下の形式で標準入力から与えられる。
N M
输出格式
答えを整数として出力せよ。
题目大意
定义长度为 N 的正整数数组 S 的权值为 ∏imin(i,Si),求所有满足 ∑iSi=M 的数组的权值和,对 200003 取模。
N≤M≤2N,N≤1012。
3 5
14
1126 2022
40166
1000000000000 1500000000000
180030
提示
制約
- 1 ≤ N ≤ 1012
- N ≤ M ≤ 2N
- 入力は全て整数
Sample Explanation 1
条件を満たす 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∏N min(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 を出力します。
Sample Explanation 2
総和を 200 003 で割った余りを出力してください。