复读机 - 問題

#13644. 复读机

統計

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

输入格式

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

输出格式

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

样例一

input

4 2 2

output

限制与约定

本题采用子任务方式评测

子任务一 $(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$。

About Issues

We understand that our problem archive is not perfect. If you find any issues with the problem, including the statement, scoring configuration, time/memory limits, test cases, etc.

You may use this form to submit an issue regarding the problem. A problem moderator will review your issue and proceed it properly.

STOP! Before you submit an issue, please READ the following guidelines:

This is not a place to publish a discussion, editorial, or requests to debug your code. Your issue will only be visible by you and problem moderators. Other users will not be able to view or reply your issues.
Do not submit duplicated issues. If you have already submitted one, please wait for an moderator to review it. Submitting multiple issues will not speed up the review process and might cause your account to be banned.
Issues must be filed in English or Chinese only.
Be sure your issue is related to this problem. If you need to submit an issue regarding another problem, contest, category, etc., you should submit it to the corresponding page.

Active Issues 0

No issues in this category.

Closed/Resolved Issues 0