### 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 {Bk} by B0 = x and Bk+1 = f(Bk). Let g(x) be the smallest index k of this sequence such that Bk = 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

0)

 `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
1)

 `487` `0`
`Returns: 1`
 B0 = 1 means x = 1.
2)

 `19` `10`
`Returns: 512`
3)

 `3` `4`
`Returns: 6`
4)

 `10` `487`
`Returns: 829515032`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10761

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14240&pm=10761

lyrically

#### Testers:

PabloGilberto , ivan_metelsky , soul-net

#### Problem categories:

Dynamic Programming