In mathematics, Fibonacci numbers or Fibonacci series or Fibonacci sequence are the numbers of the following integer sequence:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...

By definition, the first two numbers in the Fibonacci sequence are 1 and 1, and each subsequent number is the sum of the previous two. In mathematical terms, the sequence F_n of Fibonacci numbers is defined by the recurrence relation F_n = F_{n - 1} + F_{n - 2} with seed values F₁ = 1 and F₂ = 1.

And your task is to find ΣF_i^K, the sum of the K-th power of the first N terms in the Fibonacci sequence. Because the answer can be very large, you should output the remainder of the answer divided by 1000000009.

Input

There are multiple test cases. The first line of input is an integer T indicates the number of test cases. For each test case:

There are two integers N and K (0 <= N <= 10¹⁸, 1 <= K <= 100000).

Output

For each test case, output the remainder of the answer divided by 1000000009.

Sample Input

510 14 2020 29999 99987654321987654321 98765

Sample Output

14348783295274049690113297124108672406

Hint

The first test case, 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 = 143.

The second test case, 1²⁰ + 1²⁰ + 2²⁰ + 3²⁰ =3487832979, and 3487832979 = 3 * 1000000009 + 487832952, so the output is 487832952.

题意：求前n项k次的斐波那契数列和 并模1e9+9 其中 \(n <= 10^{18} \), \(k <= 10^5 \)

思路：这题拿到手很快就想到使用矩阵进行快速幂取模求解，但问题是如果k的数值小一些——那就可以直接构造矩阵储存各个幂次并进行求解了。但1e5级别的高次幂显然要求用另外的方法。事实上这是道数论题。首先从斐波那契数列的通项公式上，\(fib(n)=\frac{1}{\sqrt{5}} [(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n] \)，由于模的是素数，而且5恰好是模1e9+9的二次剩余，故我们使用\(x^2\equiv{5}\pmod{1000000009}\)的解代替其中的\(\sqrt{5}\)，对中括号中的对称式子先进行k次幂的运算，再使用二次项展开，合并相同系数的项后可以发现就是求0到k次等比数列和，注意其中的分母全部要转换成逆元。

具体题目上我们先预处理所有的阶乘和对称式子，而逆元的计算直接使用费马小定理即可。

这题是zju的校赛题，看记录5个小时里还是有挺多人写出来的。

感觉好难orz，自己好菜，但是还是学到挺多的。

/** @Date    : 2017-03-18-15.39  * @Author  : Lweleth (SoungEarlf@gmail.com)  * @Link    : https://github.com/  * @Version :  */#include<bits/stdc++.h>#define LL long long#define PII pair#define MP(x, y) make_pair((x),(y))#define fi first#define se second#define PB(x) push_back((x))#define MMG(x) memset((x), -1,sizeof(x))#define MMF(x) memset((x),0,sizeof(x))#define MMI(x) memset((x), INF, sizeof(x))using namespace std;const int INF = 0x3f3f3f3f;const int N = 1e5+20;const double eps = 1e-8;const LL mod = 1e9 + 9;const LL trem = 383008016;LL fac[N], le[N], ri[N];LL fpow(LL a, LL n){    LL res = 1;    while(n > 0)    {        if(n & 1)            res = res * a % mod;        a = a * a % mod;        n >>= 1;    }    return res;}LL Inv(LL x){    return fpow(x, mod - 2);}void init(){    LL tinv = Inv(2);    fac[0] = 1;    le[0] = ri[0] = 1;    LL l = ((1 + trem + mod)%mod) * tinv % mod;    LL r = ((1 - trem + mod)%mod) * tinv % mod;    for(LL i = 1; i < N; i++)        fac[i] = fac[i - 1] * i % mod;    for(int i = 1; i < N; i++)    {        le[i] = le[i - 1] * l % mod;        ri[i] = ri[i - 1] * r % mod;        //cout << le[i] <<" " <<  ri[i] << endl;    }}int T;LL n, k;int main(){    init();    cin >> T;    while(T--)    {        scanf("%lld%lld", &n, &k);        LL ans = 0;        for(int i = 0; i <= k; i++)        {            LL flag = 1;            if((k - i) % 2)                flag = -1;            LL t = le[i] * ri[k - i] % mod;            LL d = fac[k - i] * fac[i] % mod;            LL c = fac[k] * Inv(d) % mod;            /*--*/            LL x = (t * (1 - fpow(t, n)) % mod) * Inv(1 - t) % mod;            if(t == 1)                x = n % mod;            ans = (ans + flag * c * x ) % mod;            ans = (ans + mod) % mod;            //cout << t << endl;        }        ans = (ans * fpow(Inv(trem) % mod, k) + mod) % mod;        printf("%lld\n", ans);    }    return 0;}

ZOJ 3774 Fibonacci的K次方和