cdoj 1397 a hard-working girl lrz

#include <cstdio>
#include <iostream>
using namespace std;
const long long mod = 1000000009;
typedef long long int ll;
void extend_gcd(ll a, ll b, ll &d, ll &x, ll &y) {
    if (!b)
        d = a, x = 1, y = 0;
    else {
        extend_gcd(b, a % b, d, y, x);
        y -= x * (a / b);
    }
}
ll inv(ll a, ll mod) 
{
    ll d, x, y;
    extend_gcd(a, mod, d, x, y);
    ll ret = (d == 1 ? (x + mod) % mod : -1);
    assert(ret > 0);
    return ret;
}
ll cpre[1001000];
void combine1(ll n, ll mod) //计算组合C(n,m)%mod
{
    ll sum = 1; //线性计算
    cpre[0] = 1;
    for (ll i = 1, j = n; i <= n; i++, j--) {
        sum = (sum * j) % mod * inv(i, mod) % mod;
        cpre[i] = sum;
    }
}
ll Pow(ll a, ll p, ll mod) {
    if (p == 0)
        return 1LL;
    if (p == 1)
        return a;
    ll tmp = Pow(a, p / 2, mod);
    tmp = (tmp * tmp) % mod;
    if (p % 2)
        tmp = tmp * a % mod;
    return tmp;
}
ll S(ll A, ll B, ll C, ll n, int k) {
    ll ans = 0;
    for (int j = 0; j <= k; ++j) {
        ll d = Pow(A, (k - j), mod) * Pow(B, j, mod) % mod;
        ll f = ((j % 2 == 0) ? 1 : -1);
        ll di = 0;
        if (d * d % mod == 1) {
            di = (n * d) % mod;
        } else {
            di = (Pow(d, 2 * n + 1, mod) - d + mod) *
                 inv(d * d - 1 + mod, mod) % mod;
        }
        ll th = f * di % mod;
        ans = ((ans + cpre[j] * th) % mod + mod) % mod;
    }
    return (Pow(C, k, mod) * ans) % mod;
}
ll C = 276601605LL, A = 691504013LL, B = 308495997LL;
int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    combine1(k, mod);
    cout << S(A, B, C, n, k) << endl;
    return 0;
}
// a(n) = (phi^(2n-1)+phi^(1-2n))/sqrt(5) where phi=(1+sqrt(5))/2.
// 276601605*(691504013^(2*n-1) + 691504013^(1-2*n))