Background

Introduction to High-Performance Computing is a specialized elective course offered by the Department of Computer Science at T University. This course covers the basic concepts and principles of high-performance computing, common parallel programming models and basic ideas for writing parallel programs, basic methods for program performance analysis and optimization, and the relationship between computer architecture and program performance. To let students experience parallel programming, performance analysis, and optimization in practice, the course provides a cluster consisting of five servers. Each server is equipped with a $2$ socket $\times\ 14$ core processor and $1$ GPU. Students enrolled in the course can do message-passing parallel programming, shared-memory parallel programming, and CUDA programming on the cluster. To prevent valuable computing resources from being abused (for example, secretly using the servers for crypto mining), the course has many rules for using the cluster, including requiring students to use strong cluster login passwords.

Problem Description

To ensure that students use sufficiently strong cluster login passwords, the course staff configured a password complexity policy on the cluster. At the beginning of the semester, every student receives a randomly generated initial password. After logging into the cluster with the initial password, the cluster requires the student to enter a new password. Only after changing the password can the student access the cluster normally. In this problem, we assume the password complexity policy is:

• The password contains at least $L$ characters, and contains at least one digit and at least one letter.

• The password must not contain $A$ consecutive identical characters. For example, 2333 contains $3$ consecutive identical characters.

• The password must not contain an increasing sequence or decreasing sequence made of $B$ consecutive characters. Here, an increasing sequence is defined as a contiguous substring of one of the three strings 0123456789, ABCDEFGHIJKLMNOPQRSTUVWXYZ, and abcdefghijklmnopqrstuvwxyz. A decreasing sequence is the reverse of a contiguous substring of one of these three strings. For example:

  • 6789 is an increasing sequence of length $4$, and FED is a decreasing sequence of length $3$.

  • 90, AZ, and az are not increasing or decreasing sequences.

  • GPU is not an increasing sequence because it is not contiguous.

  • Def is not an increasing sequence because the letter cases are inconsistent (but it contains an increasing contiguous subsequence ef of length $2$).

  • 1112345678999 is not an increasing sequence, but its subsequence 123456789 is increasing.

Assume the password consists only of digits and uppercase/lowercase letters. Among all passwords with length not exceeding $R$, compute how many passwords satisfy the password complexity policy.

Input Format

The input contains one line with four positive integers $L, R, A, B$, whose meanings are as described above.

Output Format

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

2 2 2 2

1040

12 24 3 4

718185656

100 10000000 6 6

146399052

Hint

[Sample 1 Explanation]

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

[Constraints]

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

[Hint]

If you do not want to remember a long and complex password, and do not want to type it manually every time you log in, you can also set up a public key for SSH login.

Translated by ChatGPT 5