Problem Description

Saito-kun is a staff member at Maximum Elementary School and is in charge of creating the school lunch menu. It's about time to start making the menu, so Saito-kun decided to think about it. The menu needs to be balanced; a menu consisting only of Japanese food or only Western food would bore the students.

Therefore, he first decided to determine the genre of the menu for the day. The menus are:

• Japanese menu
• Western menu
• Chinese menu
• Mixed Japanese and Western menu
• Mixed Japanese and Chinese menu
• Mixed Western and Chinese menu
• Mixed Japanese, Western, and Chinese menu

There are 7 types of menus.

What we want to consider now is a menu for N days that satisfies the condition "within any consecutive K days, the number of days with the same genre should be no more than L days."

Here, if a mixed menu or a mixed menu with all genres is served, it counts as serving all the genres included in it. For example, if a mixed Japanese and Western menu is served, it counts as serving both Japanese and Western menus that day. Please refer to the table below for details.

Now, you, the master of combinations, thought:

"How many combinations are possible...?"

Please find the total number of combinations of menus that satisfy this condition.

Since the answer can be very large, output it in the form of a remainder of $1000000007$.

About the Conditions

Consider $N = 5, K = 5, L = 3$.

In Example 1, all genres (Japanese, Western, Chinese) appear within 3 days out of 5, so it satisfies the condition.

On the other hand, in Example 2, Western food appears 4 days out of 5, so it does not satisfy the condition.

Input Format

The input is given from the standard input in the following format:

$N$ $K$ $L$

Output Format

Output the answer in one line.

Sample Input and Output

Sample Input #1

3 3 1

Sample Output #1

6

Sample Input #2

15 3 2

Sample Output #2

213221133

Sample Input #3

365 5 3

Sample Output #3

792323641

Sample Input #4

5 5 1

Sample Output #4

0

Notes/Hints

Constraints

• $K \leq N \leq 365$
• $2 \leq K \leq 5$
• $1 \leq L \leq K$

Output the answer in the form of a remainder of $1000000007$.

Sample Explanation 4

There is a possibility that no menu can be created.

见题面 Input 部分

见题面 Output 部分