Description

We call a sequence $a$ good iff $1\le a_i\le k(1\le i\le n)$ and for all $x$, the occurrences of $x$ in $a$ is a multiple of $d$. Please count the number of good sequences. Since the answer could be extremely large, you just need to calculate it modulo $19491001$.

Input Format

One line with three positive integers $n,k,d$.

Output Format

Output one integer which is the answer modulo $19491001$.

8 3 4

213

12 4 6

5548

Limits

For $50\%$ of the testcases, $d = 4, k\le 2\times 10^3$.

For the rest $50\%$ of the testcases, $d = 6, k\le 10^3$.

It's guaranteed that $n\le 10^9$.