Changho's Preparation for Study Abroad

Time limit2sMemory limit1024 MB

Summary

Count the study sequences of length N over X words where each of the Y well-known words never repeats Z or more times in a row, modulo 1e9+7.

Level: Medium7 of 10
Topics: Dynamic programming, Combinatorics, Matrix
Solved: No attempts yet

문제

Changho is preparing to study abroad and has been focusing on foreign language study lately. Jaewoo wanted to help, so he gave Changho a list of $X$ distinct foreign words. However, $Y$ of the words on the list were already well known to Changho. Changho calls these words Well-Known words. To study efficiently, Changho set his own rule: for Well-Known words, he will not study the same word $Z$ or more times in a row. After hearing this rule, Jaewoo became curious about the total number of ways Changho can study the words on the list.

Each study session covers exactly one word. Given the number of study sessions $N$ , the number of words $X$ on the list, the number of Well-Known words $Y$ , and the limit $Z$ , find the total number of ways Changho can study the words on the list. The same word may be studied many times, and some words may never be studied.

입력

The first line contains four integers $N$ ( $1 \leq N \leq 10^{18}$ ), $X$ ( $1 \leq X \leq 10^{18}$ ), $Y$ ( $1 \leq Y \leq X$ ), and $Z$ ( $1 \leq Z \leq 10^{3}$ ), separated by spaces.

출력

Print the total number of ways Changho can study the words on the list, modulo $1\,000\,000\,007$ , because the answer can be large.

Examples3

Example 1
Input
```
2 3 2 2
```
Expected output
```
7
```
Example 2
Input
```
10 3 2 3
```
Expected output
```
36559
```
Example 3
Input
```
16 5 2 4
```
Expected output
```
455819708
```