#arc107d. [arc107_d]Number of Multisets
[arc107_d]Number of Multisets
Problem Statement
You are given two positive integers and . How many multisets of rational numbers satisfy all of the following conditions?
- The multiset has exactly elements and the sum of them is equal to .
- Each element of the multiset is one of $1, \\frac{1}{2}, \\frac{1}{4}, \\frac{1}{8}, \\dots$. In other words, each element can be represented as .
The answer may be large, so print it modulo .
Constraints
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
Output
Print the number of multisets of rational numbers that satisfy all of the given conditions modulo .
Sample Input 1
4 2
Sample Output 1
2
The following two multisets satisfy all of the given conditions:
- ${\\frac{1}{2}, \\frac{1}{2}, \\frac{1}{2}, \\frac{1}{2}}$
Sample Input 2
2525 425
Sample Output 2
687232272