#include <cstdio>
#include <cstring>

#define maxK 22
#define mod 9901

using namespace std;

int N, M, K;
int mat[maxK][maxK], sol[maxK][maxK], rez[maxK][maxK];
int line[maxK];

void afis(int mat[][maxK]) {
	int i, j;
	for (i = 1; i <= K; i++) {
		for (j = 1; j <= K; j++)
			printf("%d ", mat[i][j]);
		printf("\n");
	}
}

inline void mult(int A[][maxK], int B[][maxK], int C[][maxK]) {
	int i, j, k;

	for (i = 1; i <= K; i++)
		for (j = 1; j <= K; j++)
			for (k = 1; k <= K; k++) 
				C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod;
}

void mat_pow(int power, int mat[][maxK], int rez[][maxK]) {
	int i;
	int matP2[maxK][maxK], aux[maxK][maxK];

	for (i = 1; i <= K; i++)
		rez[i][i] = 1;

	memcpy(matP2, mat, sizeof(matP2));
	for (i = 0; (1 << i) <= power; i++) {
//		fprintf(stderr, "%d\n", i);
		if (power & (1 << i)) {
			memset(aux, 0, sizeof(aux));
			mult(rez, matP2, aux);
			memcpy(rez, aux, sizeof(aux));
		}

		memset(aux, 0, sizeof(aux));
		mult(matP2, matP2, aux);
		memcpy(matP2, aux, sizeof(matP2));
	}
}

int main() {

	int i;

	freopen("pod.in", "r", stdin);
	freopen("pod.out", "w", stdout);

	scanf("%d%d%d", &N, &M, &K);

	mat[1][1] = 1; mat[1][K] = 1;
	for (i = 2; i <= K; i++) 
		mat[i][i - 1] = 1;

//	afis(mat);

	line[0] = 1;
	for (i = 1; i <= K; i++) 
		line[i] = line[i] + line[i - 1];

	mat_pow(N - K + 1, mat, rez);
//	afis(rez);

//	fprintf(stderr, "ajunge");
	int sol = 0;
	for (i = 1; i <= K; i++)
		sol = (sol + rez[i][1]) % mod;

//	printf("%d\n", ((line[1] * rez[1][1]) + (line[K] * rez[K][1])) % mod); 
	printf("%d\n", sol);

	return 0;
}