U246727 「KDOI-01」浣溪沙

$\texttt{kdyl}$ 在学数论。

$\texttt{kdyl}$ 终于学完了 $\gcd$。他又想起了一个有趣的东西：斐波那契数列！ $\texttt{kdyl}$ 写了一个简单的式子： $$\sum^n_{i=1}\sum^n_{j=i}f^k_{\gcd(i,j)}$$ 他觉得这个式子太难了，于是随手就扔给了 $\texttt{Register-int}$ 。当然， $\texttt{Reg}$ 一眼就秒了它。他想考考你，让你求这个数列的值。

一行两个正整数，表示 $n$ 和 $k$。

一行一个正整数，表示结果 $\bmod\,10^9+9$ 的值。

样例解释： 样例一展开后为 $8\times1^3+2^3+3^3=43$ 。 - - - 数据范围： 对于 $10\%$ 的数据，$n\leq5000$。 对于 $30\%$ 的数据，$k\leq3$。 对于 $65\%$ 的数据，$n\leq10^9$。 对于 $100\%$ 的数据， $1\leq n\leq10^{10},1\leq k\leq4$。