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

[ABC279Ex] Sum of Prod of Min

Score : 600600 points

Problem Statement

You are given positive integers NN and MM. Here, it is guaranteed that NM2NN\leq M \leq 2N.

Print the sum, modulo 200 003200\ 003 (a prime), of the following value over all sequences of positive integers S=(S1,S2,,SN)S=(S_1,S_2,\dots,S_N) such that i=1NSi=M\displaystyle \sum_{i=1}^{N} S_i = M (notice the unusual modulo):

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

Constraints

  • 1N10121 \leq N \leq 10^{12}
  • NM2NN \leq M \leq 2N
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

NN MM

Output

Print the answer as an integer.

3 5
14

There are six sequences SS 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 k=1Nmin(k,Sk)\displaystyle \prod_{k=1}^{N} \min(k,S_k) for each of those SS is as follows.

  • S=(1,1,3)S=(1,1,3) : 1×1×3=31\times 1 \times 3 = 3
  • S=(1,2,2)S=(1,2,2) : 1×2×2=41\times 2 \times 2 = 4
  • S=(1,3,1)S=(1,3,1) : 1×2×1=21\times 2 \times 1 = 2
  • S=(2,1,2)S=(2,1,2) : 1×1×2=21\times 1 \times 2 = 2
  • S=(2,2,1)S=(2,2,1) : 1×2×1=21\times 2 \times 1 = 2
  • S=(3,1,1)S=(3,1,1) : 1×1×1=11\times 1 \times 1 = 1

Thus, you should print their sum: 1414.

1126 2022
40166

Print the sum modulo 200 003200\ 003.

1000000000000 1500000000000
180030