传送门

题意是说给 N, C, K 求这样一个东西：

其中F_{NC}表示斐波那契数列的第NC项。

---

做法是先查一下斐波那契数列的通项公式：

找到其中根号5的二次剩余。

383008016^2 ≡616991993^2≡5 (mod 10^9+9)

然后就可以替换掉通项里的东西。

F_n=C(A^n-B^n)

可得

F_{cn}^k=C^k(A^{cn}-B^{cn})^k

\sum\limits_{i=0}^n F_{ci}^k=C^k\sum\limits_{i=0}^n(A^{ci}-B^{ci})^k

对其二项式展开, 并变换枚举顺序

\sum\limits_{i=0}^nF_{ci}^k= C^k\sum\limits_{i=0}^n \sum\limits_{r=0}^k \binom{k}{r}(A^{ci(k-r)}B^{cir}(-1)^r)

\sum\limits_{i=0}^nF_{ci}^k= C^k \sum\limits_{r=0}^k \binom{k}{r} (-1)^r \sum\limits_{i=0}^n (A^{ci(k-r)}B^{cir})

然后观察到内层的 \sum\limits_{i=0}^n (A^{ci(k-r)}B^{cir}) 其实是以(A^{c(k-r)}B^{cr})为公比的等比数列（几何级数），可以直接使用公式求和。

• 注意本题从0累加到n实际上有n + 1项，求几何级数的时候需要注意。但是第0项等于0，所以也可以看作从1开始枚举，用通项的时候单独减去1。两种处理方法都可以。

• 第二个需要注意的点是公式仅适用于r =\not 1。如果r=1直接用r * n或者r*(n+1)即可。取决于上面一步是什么处理方法。

在实际代码中，每一轮的公比实际是上一轮的A和B自乘一个单位，所以可以先预处理。不然这题时间卡的非常紧会T掉。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 9;
const int C = 276601605; // 1 / sqrt(5)
const int A = 691504013; // (1 + sqrt(5)) / 2
const int AA = 691504012; // A ^ -1
const int B = 308495997; // (1 - sqrt(5)) / 2
const int maxn = 1e5 + 233;
LL f[maxn], finv[maxn];


inline int ksm(int n, int k)
{
    n %= mod;
    int res = 1;
    while(k)
    {
        if(k & 1) res = (LL)res * n % mod;
        n = (LL)n * n % mod;
        k >>= 1; 
    }
    return res % mod;
}

void init(int n) {
    f[0] = 1;
    for(int i = 1; i <= n; i++) {
        f[i] = 1LL*f[i-1]*i%mod;
    }
    finv[n] = ksm(f[n], mod-2);
    for(int i = n; i > 0; i--) {
        finv[i-1] = 1LL*finv[i]*i%mod;
    }
}
inline int Comb(int n, int m) {
    if(m > n) return 0;
    return 1LL*f[n]*finv[m]%mod*finv[n-m]%mod;
}

int main()
{
    init(100001);

    cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
    // freopen("t.txt", "w", stdout);
    int T; cin >> T;
    // int base = 10;
    while(T--)
    {
        LL n, c;
        int k; cin >> n >> c >> k;
        int ans = 0;
        int R1 = ksm(A, c % (mod - 1) * k % (mod - 1) );
        int R2 = ksm(B, c % (mod - 1) * 0 % (mod - 1) );
        int invR1 = ksm(ksm(A, c % (mod - 1)), mod - 2);
        int uniR2 = ksm(B, c % (mod - 1));
        for(int i = 0; i <= k; i++)
        {
            int Co = Comb(k, i);
            if(i & 1) Co = mod - Co;
            // int R = ksm(A, (c % (mod - 1) * (k - i) % (mod - 1)), base) * ksm(B, c % (mod - 1) * i % (mod - 1), base) % mod;
            int R = (LL)R1 * R2 % mod;
            // 1 + R + R^2 + ... + R^n = S(n + 1)
            // cerr << R << endl;
            int n1 = (n + 1) % (mod - 1);
            if(R == 1) ans = ((LL)ans + n % mod * Co % mod) % mod;
            else 
            {
                int S = (ksm(R, n1) - 1LL) * ksm(R - 1, mod - 2) % mod;
                S = S - 1; // F1 ~ FN except 1
                ans = ((LL)ans + (LL)Co * S % mod) % mod;
            }         
            R1 = (LL)R1 * invR1 % mod;
            R2 = (LL)R2 * uniR2 % mod;
        }
        cout << ((LL)ans * ksm(C, k) % mod + mod) % mod << endl;
    }

}