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

[ABC279Ex] Sum of Prod of Min

题目描述

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

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

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

输入格式

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

N N M M

输出格式

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

题目大意

定义长度为 NN 的正整数数组 SS 的权值为 imin(i,Si)\prod_i \min(i,S_i),求所有满足 iSi=M\sum_i S_i=M 的数组的权值和,对 200003200003 取模。

NM2NN\le M\le 2NN1012N\le 10^{12}

3 5
14
1126 2022
40166
1000000000000 1500000000000
180030

提示

制約

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

Sample Explanation 1

条件を満たす S 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 6 つです。 それぞれの S S について  k=1N min(k,Sk) \displaystyle\ \prod_{k=1}^{N}\ \min(k,S_k) の値を求めると、 - S=(1,1,3) S=(1,1,3) : 1× 1 × 3 = 3 1\times\ 1\ \times\ 3\ =\ 3 - S=(1,2,2) S=(1,2,2) : 1× 2 × 2 = 4 1\times\ 2\ \times\ 2\ =\ 4 - S=(1,3,1) S=(1,3,1) : 1× 2 × 1 = 2 1\times\ 2\ \times\ 1\ =\ 2 - S=(2,1,2) S=(2,1,2) : 1× 1 × 2 = 2 1\times\ 1\ \times\ 2\ =\ 2 - S=(2,2,1) S=(2,2,1) : 1× 2 × 1 = 2 1\times\ 2\ \times\ 1\ =\ 2 - S=(3,1,1) S=(3,1,1) : 1× 1 × 1 = 1 1\times\ 1\ \times\ 1\ =\ 1 となるため、その総和である 14 14 を出力します。

Sample Explanation 2

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