BunnySequence | Topcoder Archive

Problem Statement

Bunnies like programming and they sometimes make useless devices.

One group of bunnies made a simple computer that calculates the following function f:
For a positive integer x,

f(x) = x / m if x is a multiple of m.
f(x) = x + 1 otherwise.

where m is a fixed positive integer greater than 1.

For a positive integer x, we define a sequence {B_k} by B₀ = x and B_k+1 = f(B_k). Let g(x) be the smallest index k of this sequence such that B_k = 1. Calculate the number of positive integers x satisfying g(x) = n, and return the answer modulo 1,000,000,009.

Definition

Class:: BunnySequence
Method:: getNumber
Parameters:: int, int
Returns:: int
Method signature:: int getNumber(int m, int n)
(be sure your method is public)

Notes

For any positive integer x, there always exists k such that Bk = 1.

Constraints

m will be between 2 and 1,000,000, inclusive.
n will be between 0 and 1,000,000, inclusive.

Examples

```
5
```
```
3
```
```
Returns: 4
```
There are four positive integers x such that f(f(f(x))) = 1. The sequences {Bk} for them are as follows: 3 -> 4 -> 5 -> 1 20 -> 4 -> 5 -> 1 24 -> 25 -> 5 -> 1 125 -> 25 -> 5 -> 1
```
487
```
```
0
```
```
Returns: 1
```
B0 = 1 means x = 1.
```
19
```
```
10
```
```
Returns: 512
```
```
3
```
```
4
```
```
Returns: 6
```
```
10
```
```
487
```
```
Returns: 829515032
```

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.