409614: GYM103643 Q Kirito's Password

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Q. Kirito's Passwordtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

The year is 2022, and the virtual reality massively multiplayer online role-playing game called Sword Art Online has just been released. This next generation world of the metaverse is nearly indistinguishable from reality.

Kirito just had a blast gamin in the world. However, when he tries to logout, he realizes he forgot his password! Luckily, Kirito knows his password has some peculiar properties:

  1. His password consists of $$$N$$$ $$$(1 \leq N \leq 10^7)$$$ numbers in a row.
  2. Each number is an integer from $$$0$$$ to $$$M$$$ inclusive $$$(1 \leq M \leq 10^6)$$$.
  3. The password contains at least $$$1$$$ non-zero number.
  4. There are at least $$$K$$$ $$$(1 \leq K \leq 10)$$$ zeros between any pair of non-zero numbers.
  5. The $$$\gcd$$$ of all non-zero numbers is $$$1$$$.

Kirito wants you to find how many passwords could be his. Of course, Kirito hasn't touched grass in quite a while, so he also doesn't know this number can be quite large. Thus, find the number$$$\mod 10^9 + 7$$$.

Input

The first and only line contains $$$3$$$ integers, $$$N$$$, $$$M$$$, $$$K$$$.

Output

Print the number of passwords that could be Kirito's$$$\mod 10^9 + 7$$$.

ExampleInput
3 2 1
Output
6
Note

For the example, $$$6$$$ passwords could be Kirito's: $$$(1,\; 0,\; 0)$$$, $$$(0,\; 1,\; 0)$$$, $$$(0,\; 0,\; 1)$$$, $$$(1,\; 0,\; 1)$$$, $$$(2,\; 0,\; 1)$$$, or $$$(1,\; 0,\; 2)$$$.

$$$---------------------------------------------$$$

Problem Idea: codicon

Problem Preparation: codicon

Occurrences: Advanced 11

加入题单

上一题 下一题 算法标签: