As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
群里有$k$个不同的复读机。为了庆祝平安夜的到来，在接下来的$n$秒内，它们每秒钟都会选出一位优秀的复读机进行复读。非常滑稽的是，一个复读机只有总共复读了$d$的倍数次才会感到快乐。问有多少种不同的安排方式使得所有的复读机都感到快乐。
一行三个正整数$n$,$k$,$d$，意义如题目描述所述。
一行一个正整数，表示方案数对$19491001$取模的值。
4 2 2
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$。
The discussion section is only for posting: Editorials, General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.
This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.
If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.
Guidelines: