#abc163d. [abc163_d]Sum of Large Numbers
[abc163_d]Sum of Large Numbers
Problem Statement
We have integers: , , ..., .
We will choose or more of these integers. Find the number of possible values of the sum of the chosen numbers, modulo .
Constraints
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
Output
Print the number of possible values of the sum, modulo .
Sample Input 1
3 2
Sample Output 1
10
The sum can take values, as follows:
- $(10^{100})+(10^{100}+3)=(10^{100}+1)+(10^{100}+2)=2\\times 10^{100}+3$
- $(10^{100})+(10^{100}+1)+(10^{100}+2)=3\\times 10^{100}+3$
- $(10^{100})+(10^{100}+1)+(10^{100}+3)=3\\times 10^{100}+4$
- $(10^{100})+(10^{100}+2)+(10^{100}+3)=3\\times 10^{100}+5$
- $(10^{100}+1)+(10^{100}+2)+(10^{100}+3)=3\\times 10^{100}+6$
- $(10^{100})+(10^{100}+1)+(10^{100}+2)+(10^{100}+3)=4\\times 10^{100}+6$
Sample Input 2
200000 200001
Sample Output 2
1
We must choose all of the integers, so the sum can take just value.
Sample Input 3
141421 35623
Sample Output 3
220280457