PowerPartition | Topcoder Archive

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

```
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.
```
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.
```
1000
```
```
1000000007
```
```
Returns: 500501002
```
```
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)2024, Topcoder, Inc. All rights reserved.