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_{0} = 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 B_{k} = 1. 

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

Examples 
0)  
  Returns: 4  There are four positive integers x such that f(f(f(x))) = 1.
The sequences {B_{k}} for them are as follows:
 3 > 4 > 5 > 1
 20 > 4 > 5 > 1
 24 > 25 > 5 > 1
 125 > 25 > 5 > 1



1)  
 
2)  
 
3)  
 
4)  
 