首先，k=1我们发现没有合法的。
其次，对于k>=2的情况，我们可以分成若干链进行求解，链长很短。
如果没有q的限制，则很显然记录最后一个选不选就行了。
由q的限制，则记录最后q个数选的情况。看起来复杂度是2^q的，但是按照不能相邻来剪枝，状态不超过200个。
进行dp即可。

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long ll;

const int N = 1010;
const int MOD = 10086001;

ll n, k, p, cnt;
int idx[2000000], rev[2000000];

bool c(int x, int i) {
    return (x & (1 << i)) > 0;
}

ll qpow(ll x, ll n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * x % MOD;
        x = x * x % MOD;
        n /= 2;
    }
    return res;
}

int tt[65][N];
int dp[N];

void upd(int &x, int y) {
    x += y;
    if (x >= MOD) x -= MOD;
}

ll f(ll x) {
    return x - x / k;
}

int main() {
    //freopen("0.txt", "r", stdin);
    scanf("%lld%lld%lld", &n, &k, &p);
    if (k == 1) {
        printf("%lld\n", 1);
        return 0;
    }
    for (int i = 0; i < (1 << p); i++) {
        bool f = true;
        for (int j = 0; j < p; j++) {
            if (c(i, j) && c(i, j + 1)) f = false;
        }
        if (f) {
            idx[i] = ++cnt;
            rev[cnt] = i;
        }
    }
    tt[0][1] = 1; int r = (1 << (p - 1));
    for (int i = 0; i < 60; i++) {
        for (int j = 1; j <= cnt; j++) {
            if (tt[i][j] == 0) continue;
            upd(tt[i + 1][idx[rev[j] / 2]], tt[i][j]);
            if ((rev[j] % 2 != 1) && idx[rev[j] / 2 + r]) upd(tt[i + 1][idx[rev[j] / 2 + r]], tt[i][j]);
            upd(dp[i], tt[i][j]);
        }
    }
    ll ans = 1;
    for (ll i = 1, t = 1; i <= n; i *= k, t++) 
        ans = ans * qpow(dp[t], f(n / i) - f(n / i / k)) % MOD;
    printf("%lld\n", ans);
    return 0;
}