JOIN

 Problem Statement

Problem Statement for PowerPartition

### Problem Statement

Yayoi and Iori like traveling together. One day, they arrived to a strange planet. The currency system on the planet is really simple: the denominations are precisely all nonnegative powers of an integer M. I.e., the coins have the following values: 1, M, M^2, M^3, ...

Yayoi and Iori now want to buy souvenirs for their friends. The total price of those souvenirs is X. Yayoi and Iori would like to pay this amount exactly. They have a sufficient supply of coins with each of the available values.

You are given the int M and the long X. Let W be the number of different ways in which they can pay the required amount. Here, two ways are considered different if and only if there is some value such that in each way we use a different number of coins with this value. As W can be huge, return the value (W modulo 1,000,000,007).

### Definition

 Class: PowerPartition Method: count Parameters: int, long Returns: int Method signature: int count(int M, long X) (be sure your method is public)

### Constraints

-M will be between 2 and 1000, inclusive.
-X will be between 1 and 10^18, inclusive.

### Examples

0)

 `2` `4`
`Returns: 4`
 The coins have values 1, 2, 4, 8, 16, etc. The amount Yayoi and Iori want to pay is 4. There are four different ways to do that: 4, 2+2, 2+1+1, and 1+1+1+1.
1)

 `17` `1`
`Returns: 1`
 The price of souvenirs is only 1. There is only one way to pay this amount: by using a single coin with value 1.
2)

 `1000` `1000000007`
`Returns: 500501002`
3)

 `841` `765346961765346961`
`Returns: 89045497`

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
Single Round Match 669 Round 1 - Division I, Level Three