Background

Introduction to High-Performance Computing is a specialized elective course offered by the C Department at T University. This course covers the fundamental concepts and principles of high-performance computing, common parallel programming models, basic approaches to writing parallel programs, basic methods for performance analysis and optimization, and the relationship between computer architecture and program performance. To provide students with practical experience in writing parallel programs, performance analysis, and optimization, the course provides a cluster consisting of five servers, each equipped with a 2 socket × 14 core processor and 1 GPU. Students can engage in message-passing-based parallel programming, shared-memory-model-based parallel programming, and CUDA programming on the cluster. To prevent the precious computing resources from being misused (such as secretly using the servers for mining), the course has many regulations, including requiring students to use high-strength cluster login passwords.

Problem Description

To ensure that students use strong cluster login passwords, the course team has configured a password complexity policy on the cluster. All students will receive a randomly generated initial password at the beginning of the semester. After logging into the cluster with the initial password, the cluster will require the student to enter a new password, which must be changed before they can access the cluster normally. In this problem, we assume the password complexity policy is as follows:

• The password must contain at least $L$ characters, and at least one digit and one letter;
• The password must not contain consecutive $A$ repeated characters, such as 2333 which contains 3 consecutive repeated characters;
• The password must not contain consecutive $B$ characters forming an ascending or descending sequence, where an ascending sequence is defined as a consecutive substring of 0123456789, ABCDEFGHIJKLMNOPQRSTUVWXYZ, or abcdefghijklmnopqrstuvwxyz, and a descending sequence is the reverse of a consecutive substring of these strings. For example:
• 6789 is a 4-character ascending sequence, FED is a 3-character descending sequence;
• 90, AZ, az are not ascending or descending sequences;
• GPU is not an ascending sequence because it is not consecutive;
• Def is not an ascending sequence because the case of the letters is inconsistent (but it contains a 2-character ascending consecutive subsequence ef);
• 1112345678999 is not an ascending sequence, but its subsequence 123456789 is ascending.

Assume the password consists only of digits and upper and lower case letters. Find the number of passwords that satisfy the password complexity policy among all passwords with lengths not exceeding $R$.

Input Format

The input consists of a single line containing four positive integers $L, R, A, B$, as described in the problem statement.

Output Format

Output a non-negative integer representing the number of passwords that satisfy the password complexity policy and have lengths not exceeding $R$, modulo $1,000,000,007$.

Sample Input and Output

Input Sample #1

2 2 2 2

Output Sample #1

1040

Input Sample #2

12 24 3 4

Output Sample #2

718185656

Input Sample #3

100 10000000 6 6

Output Sample #3

146399052

Notes

Sample 1 Explanation

Since the password must contain at least one digit and one letter, there are $2 \times 10 \times (26 \times 2) = 1040$ valid passwords.

Data Range and Constraints

It is guaranteed that $1 \le L \le R \le 10^9$, $2 \le A \le 6$, $2 \le B \le 26$.

Hints

If you don't want to remember long and complex passwords and don't want to manually enter passwords each time you log in, you can also configure public keys for SSH login.

见题面 Input 部分

见题面 Output 部分