8272: ABC279 —— Ex - Sum of Prod of Min
[Creator : ]
Description
You are given positive integers $N$ and $M$. Here, it is guaranteed that $N≤M≤2N$.
Print the sum, modulo $200003$ (a prime), of the following value over all sequences of positive integers $S=(S_1,S_2,…,S_N)$ such that $\sum_{i=1}^{N} S_i=M$ (notice the unusual modulo):
Print the sum, modulo $200003$ (a prime), of the following value over all sequences of positive integers $S=(S_1,S_2,…,S_N)$ such that $\sum_{i=1}^{N} S_i=M$ (notice the unusual modulo):
- $\displaystyle\prod_{k=1}^{N} \min(k,S_k)$.
Input
The input is given from Standard Input in the following format:
$N\ M$
$N\ M$
Output
Print the answer as an integer.
Constraints
$1≤N≤10^{12}$
$N≤M≤2N$
All values in the input are integers.
$N≤M≤2N$
All values in the input are integers.
Sample 1 Input
3 5
Sample 1 Output
14
There are six sequences S that satisfy the condition: S=(1,1,3),S=(1,2,2),S=(1,3,1),S=(2,1,2),S=(2,2,1),S=(3,1,1).
The value $\prod_{k=1}^{N} \min(k,S_k)$ for each of those S is as follows.
The value $\prod_{k=1}^{N} \min(k,S_k)$ for each of those S is as follows.
- 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
Sample 2 Input
1126 2022
Sample 2 Output
40166
Sample 3 Input
1000000000000 1500000000000
Sample 3 Output
180030