Difficult Password

Time limit3sMemory limit2048 MB

Summary

Count passwords of length L to R that contain a digit and a letter, have no A equal characters in a row, and have no B-long ascending or descending run, modulo 1e9+7.

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

Problem

The course team set a password complexity policy on the cluster so that students use strong login passwords. At the start of the semester, every enrolled student receives a randomly generated initial password. When a student logs in with the initial password, the cluster asks for a new password. Access to the cluster is granted only after the password is changed. This problem uses the following policy.

The password must have at least $L$ characters, and it must include at least one digit and at least one letter.
The password cannot contain $A$ identical characters in a row. For example, 2333 contains three identical characters in a row.
The password cannot contain $B$ $B$ consecutive characters that form an ascending or descending sequence. An ascending sequence is a consecutive substring of one of the strings 0123456789, ABCDEFGHIJKLMNOPQRSTUVWXYZ, or abcdefghijklmnopqrstuvwxyz. A descending sequence is the reverse of a consecutive substring of one of these strings. For example:
- 6789 is an ascending sequence of length 4, and FED is a descending sequence of length 3.
- 90, AZ, and az are neither ascending nor descending sequences.
- GPU is not an ascending sequence because its letters are not consecutive.
- Def is not an ascending sequence because the letter case is mixed. It does contain the ascending subsequence ef of length 2.
- 1112345678999 is not an ascending sequence, but its subsequence 123456789 is.

The password consists only of digits and uppercase and lowercase letters. Count the passwords of length at most $R$ that satisfy this policy. The count can be very large, so output it modulo $1\,000\,000\,007$ .

Input

The input is a single line with four positive integers $L$ , $R$ , $A$ , $B$ ( $1 \le L \le R \le 10^9$ ; $2 \le A \le 6$ ; $2 \le B \le 26$ ).

Output

Print one non-negative integer: the number of passwords that satisfy the policy and have length at most $R$ , modulo $1\,000\,000\,007$ .

Hint

In Sample 1, the password must contain at least one digit and at least one letter, so there are $2 \cdot 10 \cdot (26 \cdot 2) = 1040$ valid passwords.

Examples3

Example 1
Input
```
2 2 2 2
```
Expected output
```
1040
```
Example 2
Input
```
12 24 3 4
```
Expected output
```
718185656
```
Example 3
Input
```
100 10000000 6 6
```
Expected output
```
146399052
```