409614: GYM103643 Q Kirito's Password

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$$$.

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

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

3 2 1

6

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