UOJ Logo Universal Online Judge

UOJ

#450. 【集训队作业2018】复读机

统计

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

输入格式

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

输出格式

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

样例一

input

4 2 2

output

8

限制与约定

本题采用子任务方式评测

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

子任务二 $(25pts)$:$n\leq 1000,k\leq 100$

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

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

对于所有数据,$n\leq 10^9,k\leq 500000,d\leq 3$。

时间限制:$\texttt{1s}$

空间限制:$\texttt{512MB}$

下载

样例数据下载