最小值的乘积之和

题目描述

给你正整数 $N$ 和 $M$。这里保证 $N\le M \le 2N$。

对所有满足 $\displaystyle \sum_{i=1}^{N} S_i = M$ 的正整数序列 $S=(S_1,S_2,\dots,S_N)$,求出

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

的和,并输出对 $200003$(一个质数)取模后的结果(请注意这个特殊的模数)。

输入格式

输入按以下格式从标准输入给出:

$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)$。

其中每个 $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$。

1126 2022

40166

输出对 $200003$ 取模后的结果。

1000000000000 1500000000000

180030

数据范围

• $1 \le N \le 10^{12}$
• $N \le M \le 2N$
• 输入中的所有值均为整数。