Bob's Prob
The currency in Bob's country is Dollahs. The different denominations of money in Bob's country are in powers of Dollahs. This means that they have -Dollah bills, -Dollah bills, -Dollah bills, -Dollah bills, and so on.
Bob is very wealthy and does not really care about a lot of things. He doesn't really think much because he can pay others to think for him. However, all this will change one fateful day at the grocery store. On that day, Bob was already in front of the queue for the cashier. As he was about to pay for his -Dollah purchase, the Ghost of Combinatorics appears before him and asks: "How many different ways can you pay for your -Dollah purchase (modulo )? Answer this or you will die."
Input Format
The input consists of exactly one line containing two positive integers and , in that order.
Output Format
Output a single line containing a single integer, , which is the number of ways Bob can pay for his -Dollah purchase, modulo .
Constraints
Sample Input
12 3
Sample Output
7
Explanation
Bob can form 12 Dollahs in any of the following ways.
twelve 1-Dollah bills
nine 1-Dollah bills, one 3-Dollah bill
six 1-Dollah bills, two 3-Dollah bills
three 1-Dollah bills, three 3-Dollah bills
four 3-Dollah bills
three 1-Dollah bills, one 9-Dollah bill
one 3-Dollah bill, one 9-Dollah bill
Note
Remember that modulo means that you should output only the remainder of when divided by , not itself. For example, if is 1000000011
, you should print 11
.