传送门——Vjudge

---

要求\(S = \sum\limits_{i=1}^n fib_i^k \mod 10^9+9\)

将通项公式\(fib_i = \frac{1}{\sqrt{5}} ((\frac{1 + \sqrt{5}}{2})^i - (\frac{1 - \sqrt{5}}{2})^i)\)代入，可以得到

\(\begin{align*} S & = (\frac{1}{\sqrt{5}})^k \sum\limits_{i=1}^n ((\frac{1 + \sqrt{5}}{2})^i - (\frac{1 - \sqrt{5}}{2}) ^ i)^k \\ & = (\frac{1}{\sqrt{5}})^k \sum\limits_{i=1}^n \sum\limits_{j=0}^k (-1)^j \binom{k}{j}(\frac{1 + \sqrt{5}}{2})^{i(k-j)} (\frac{1 - \sqrt{5}}{2})^{ij} \\ &= (\frac{1}{\sqrt{5}})^k \sum\limits_{j=0}^k (-1)^j \binom{k}{j} \sum\limits_{i=1}^n [(\frac{1 + \sqrt{5}}{2})^{k-j} (\frac{1 - \sqrt{5}}{2})^j]^i \end{align*}\)

因为\(5\)在\(\mod 10^9+9\)意义下有二次剩余，所以\(\sqrt{5}\)有实际值，那么我们可以从小到大枚举\(j\)，维护\(\binom{k}{j}\)，后面的那一个部分就是一个等比数列求和。注意特别判断公比为\(1\)的情况。

如果\(5\)在某些模数下没有二次剩余，因为\(a \sqrt{5}+b\)在上述需要的运算中是封闭的，所以我们可以开一个pair\((a,b)\)表示\(a\sqrt{5}+b\)，用这一个pair进行运算。

#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;

#define int long long
inline int read(){
    int a = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c) && c != EOF){
        if(c == '-')
            f = 1;
        c = getchar();
    }
    if(c == EOF)
        exit(0);
    while(isdigit(c)){
        a = a * 10 + c - 48;
        c = getchar();
    }
    return f ? -a : a;
}

const int MOD = 1e9 + 9 , INV2 = (MOD + 1) >> 1;
int K , L;

template < class T >
T poww(T a , int b){
    T times = 1;
    while(b){
        if(b & 1) times = times * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return times;
}

struct PII{
    int st , nd;
    PII(int _st = 0 , int _nd = 0) : st(_st) , nd(_nd){}
    PII operator =(int b){return *this = PII(b , 0);}
    bool operator !=(PII a){return st != a.st || nd != a.nd;}
};
PII operator +(PII a , PII b){return PII((a.st + b.st) % MOD , (a.nd + b.nd) % MOD);}
PII operator -(PII a , PII b){return PII((a.st + MOD - b.st) % MOD , (a.nd + MOD - b.nd) % MOD);}
PII operator *(PII a , PII b){return PII((a.st * b.st + 5 * a.nd * b.nd) % MOD , (a.st * b.nd + a.nd * b.st) % MOD);}
PII operator *(PII a , int b){return PII(a.st * b % MOD , a.nd * b % MOD);}
PII operator %(PII a , int b){return a;}
PII operator /(PII a , PII b){return a * PII(b.st , MOD - b.nd) * poww((b.st * b.st - 5 * b.nd * b.nd % MOD + MOD) % MOD , MOD - 2);}

int solve(int x , int k){
    PII all(0 , 0);
    int C = 1 , sgn = poww(MOD - 1 , k);
    for(int j = 0 ; j <= k ; ++j){
        PII cur = poww(PII(INV2 , INV2) , j) * poww(PII(INV2 , MOD - INV2) , k - j);
        if(cur != PII(1 , 0))
            all = all + (poww(cur , x + 1) - PII(1 , 0)) / (cur - PII(1 , 0)) * sgn * C;
        else
            all = all + PII((x + 1) % MOD , 0) * sgn * C;
        C = C * (k - j) % MOD * poww(j + 1 , MOD - 2) % MOD;
        sgn = sgn * (MOD - 1) % MOD;
    }
    all = all * poww(PII(0 , poww(5ll , MOD - 2)) , k);
    return all.st;
}

signed main(){
    for(int T = read() ; T ; --T){
        L = read(); K = read();
        printf("%lld\n" , solve(L , K));
    }
    return 0;
}