群里有$k$个不同的复读机。为了庆祝平安夜的到来，在接下来的$n$秒内，它们每秒钟都会选出一位优秀的复读机进行复读。非常滑稽的是，一个复读机只有总共复读了$d$的倍数次才会感到快乐。问有多少种不同的安排方式使得所有的复读机都感到快乐。

输入格式

一行三个正整数$n$,$k$,$d$，意义如题目描述所述。

输出格式

一行一个正整数，表示方案数对$19491001$取模的值。

样例一

input

4 2 2

output

8

限制与约定

本题采用子任务方式评测

子任务一 $(5pts)$：$d=1$

子任务二 $(25pts)$：$n\le 1000,k\le 100$

子任务三 $(30pts)$： $k\le 500000,d=2$

子任务四 $(40pts)$： $k\le 1000,d=3$

对于所有数据，$n\le {10}^9,k\le 500000,d\le 3$。

时间限制：$\mathtt{\text{1s}}$

空间限制：$\mathtt{\text{512MB}}$

下载

样例数据下载