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.

Loading Editor...
  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score