其实是一道还好的题罢，虽然做了我 2147483647（bushi，其实是 1.5h），估计也只是因为 HDU 不支持数据下载所以错误总 debug 出来
首先看到 \(10^9+9\) 及斐波那契数列，顿时心里一个激灵，这题和通项公式逃不掉了（
套用斐波那契数列通项公式 \(f_n=\dfrac{1}{\sqrt{5}}((\dfrac{1+\sqrt{5}}{2})^n-(\dfrac{1-\sqrt{5}}{2})^n)\) 得：
\[\begin{aligned} \text{Ans}&=\sum\limits_{i=0}^nF_{ic}^k \\&=\sum\limits_{i=0}^n(\dfrac{1}{\sqrt{5}}((\dfrac{1+\sqrt{5}}{2})^{ic}-(\dfrac{1-\sqrt{5}}{2})^{ic}))^k \\&=\dfrac{1}{(\sqrt{5})^k}\sum\limits_{i=0}^n((\dfrac{1+\sqrt{5}}{2})^{ic}-(\dfrac{1-\sqrt{5}}{2})^{ic})^k \end{aligned} \]看到二项式的 \(k\) 次方，可以套路地想到二项式定理，用二项式定理展开一下可继续推得：
\[\begin{aligned} \text{Ans}&=\dfrac{1}{(\sqrt{5})^k}\sum\limits_{i=0}^n((\dfrac{1+\sqrt{5}}{2})^{ic}-(\dfrac{1-\sqrt{5}}{2})^{ic})^k\\ &=\dfrac{1}{(\sqrt{5})^k}\sum\limits_{i=0}^n\sum\limits_{j=0}^k\dbinom{k}{j}(\dfrac{1+\sqrt{5}}{2})^{icj}(-(\dfrac{1-\sqrt{5}}{2})^{ic})^{k-j}\\ &=\dfrac{1}{(\sqrt{5})^k}\sum\limits_{i=0}^n\sum\limits_{j=0}^k\dbinom{k}{j}(\dfrac{1+\sqrt{5}}{2})^{icj}(\dfrac{1-\sqrt{5}}{2})^{ic(k-j)}(-1)^{k-j} \end{aligned} \]方便起见，我们设 \(A=\dfrac{1+\sqrt{5}}{2},B=\dfrac{1-\sqrt{5}}{2}\)，那么式子可进一步化为
\[\begin{aligned} \text{Ans} &=\dfrac{1}{(\sqrt{5})^k}\sum\limits_{i=0}^n\sum\limits_{j=0}^k\dbinom{k}{j}A^{icj}B^{ic(k-j)}(-1)^{k-j}\\ &=\dfrac{1}{(\sqrt{5})^k}\sum\limits_{i=0}^n\sum\limits_{j=0}^k\dbinom{k}{j}A^{icj}B^{ick}\dfrac{1}{B^{icj}}(-1)^{k-j}\\ &=\dfrac{1}{(\sqrt{5})^k}\sum\limits_{i=0}^n\sum\limits_{j=0}^k\dbinom{k}{j}(\dfrac{A}{B})^{icj}B^{ick}(-1)^{k-j}\\ &=\dfrac{1}{(\sqrt{5})^k}\sum\limits_{j=0}^k(-1)^{k-j}\dbinom{k}{j}\sum\limits_{i=0}^n(\dfrac{A}{B})^{icj}B^{ick} \end{aligned} \]推到这里，前面一个 \(\sum\) 显然直接枚举是不会出问题的，至于后面一个 \(\sum\)，如果我们设 \(P=(\dfrac{A}{B})^{cj}\times B^{ck}\)，那么里面的式子可写为 \(\sum\limits_{i=0}^nP^i\)，这显然就是一个等比数列求和的形式，直接求即可。
时间复杂度 \(Tk\log n\)，顺带说一句，本题略微有点卡常，有以下卡常技巧：
- 式子里有些东西是可以预处理出来的，大可不必每枚举一遍 \(j\) 都重新快速幂计算一遍，否则常数肯定上天
- 在等比数列求和时，由于 \(10^9+9\) 是质数，可以通过欧拉降幂 \(a^m\equiv a^{m\bmod (10^9+8)}\pmod{10^9+9}\) 减少快速幂的指数，这样常数可小一半
const int S5=383008016;
const int MOD=1e9+9;
const int INV2=5e8+5;
const int MAXN=1e5;
int qpow(int x,ll e){
int ret=1;
for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;
return ret;
}
int IV5,A,B,MUL,fac[MAXN+5],ifac[MAXN+5];
void init_fac(int n){
for(int i=(fac[0]=ifac[0]=ifac[1]=1)+1;i<=n;i++) ifac[i]=1ll*ifac[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=1ll*ifac[i-1]*ifac[i]%MOD;
}
int binom(int n,int k){return 1ll*fac[n]*ifac[k]%MOD*ifac[n-k]%MOD;}
int sum(int x,ll y){if(x==1) return (y+1)%MOD;return 1ll*(qpow(x,(y+1)%(MOD-1))-1+MOD)*qpow((x-1+MOD)%MOD,MOD-2)%MOD;}
void solve(){
ll n,c;int k;scanf("%lld%lld%d",&n,&c,&k);c%=(MOD-1);
int mul=qpow(IV5,k),ans=0,M=qpow(qpow(B,c),k),stp=qpow(MUL,c);
for(int i=0,pw=1;i<=k;i++,pw=1ll*pw*stp%MOD){
int t=1ll*pw*M%MOD;
int add=1ll*binom(k,i)*sum(t,n)%MOD;
if((k-i)&1) ans=(ans-add+MOD)%MOD;
else ans=(ans+add)%MOD;
} ans=1ll*ans*mul%MOD;printf("%d\n",ans);
}
int main(){
IV5=qpow(S5,MOD-2);
A=1ll*(1+S5)*INV2%MOD;
B=1ll*(1-S5+MOD)*INV2%MOD;
MUL=1ll*A*qpow(B,MOD-2)%MOD;
init_fac(MAXN);int qu;scanf("%d",&qu);
while(qu--) solve();
return 0;
}