题目描述

小婷制作了一台数字变换机，小泽可以把任意正整数 $X$ 放入机器。给定机器参数 $M$，机器按照下面的函数进行一次变换：

$$f(X)= \begin{cases} \dfrac{X}{M}, & M\mid X,\\[4pt] X+1, & M\nmid X. \end{cases}$$

对于正整数 $a$，$f(a)$ 是机器作用一次后的结果，$f(f(a))$ 是作用两次后的结果，以此类推。

小泽想知道，有多少个正整数 $a$ 在反复放入机器后，第一次得到 $1$ 恰好发生在第 $N$ 次变换之后。请你帮助小婷和小泽计算这个数量。

答案对 $10^9+9$ 取模。

输入格式

输入一行两个正整数 $M,N$。

输出格式

输出一个整数，表示答案对 $10^9+9$ 取模后的值。

样例 1

3 4

6

样例 2

23 34

589927352

样例 3

89726 21882

332605792

样例解释

当 $M=3,N=4$ 时，符合要求的数为

$$5,7,18,24,26,81,$$

共 $6$ 个。注意，即使从 $3$ 出发作用四次后也会得到 $1$，但它第一次作用时就已经得到 $1$，所以不符合要求。

考点说明

本题主要考查逆向思考、动态规划和滑动窗口优化。可以从目标值 $1$ 反向分析每一步的来源，并利用连续状态之和优化转移，同时注意排除提前到达 $1$ 的情况。

数据范围

• 对于 $20\%$ 的数据，$N,M\le 8$；
• 对于另外 $25\%$ 的数据，$N<M$；
• 对于 $100\%$ 的数据，$1\le N,M\le 10^6$。