Background

Introduction to High-Performance Computing is a professional 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, basic approaches to writing parallel programs, fundamental methods for program performance analysis and optimization, and the relationship between computer architecture and program performance. To allow students to gain practical experience in writing, analyzing, and optimizing parallel programs, the course provides a cluster consisting of five servers, each equipped with 2 sockets × 14 cores and 1 GPU. Students enrolled in the course can perform message-passing parallel programming, shared-memory model parallel programming, and CUDA programming on the cluster. To prevent the abuse of valuable computing resources (such as secretly using servers for cryptocurrency mining), there are many regulations regarding the use of the cluster, including a requirement for students to use high-strength cluster login passwords.

Description

To ensure that students use strong cluster login passwords, the course team has configured a password complexity policy on the cluster. All students receive a randomly generated initial password at the beginning of the semester. After logging into the cluster with the initial password, students are required to enter a new password, and they can only access the cluster normally after the password change is completed. In this problem, we assume the password complexity policy is as follows:

• The password must contain at least $L$ characters and must contain at least one digit and one letter.
• The password cannot contain $A$ consecutive repeated characters (e.g., 2333 contains 3 consecutive repeated characters).
• The password cannot contain an ascending or descending sequence of $B$ consecutive characters. An ascending sequence is defined as a consecutive substring of one of the following three strings: 0123456789, ABCDEFGHIJKLMNOPQRSTUVWXYZ, and abcdefghijklmnopqrstuvwxyz. A descending sequence is defined as the reverse of a consecutive substring of one of these three 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 not ascending or descending sequences.
  • GPU is not an ascending sequence because it is not consecutive.
  • Def is not an ascending sequence because the letter case is inconsistent (though it contains an ascending consecutive subsequence ef of length 2).
  • 1112345678999 is not an ascending sequence, but its subsequence 123456789 is ascending.

Assume that passwords consist only of digits and uppercase/lowercase letters. Calculate how many passwords satisfy the password complexity policy among all passwords with a length not exceeding $R$.

Input

The input consists of a single line containing four positive integers $L, R, A, B$, with meanings as described in the problem statement. It is guaranteed that $1\le L\le R\le 10^9$, $2\le A\le 6$, and $2\le B\le 26$.

Output

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

Examples

Input 1

2 2 2 2

Output 1

1040

Note 1

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

Input 2

12 24 3 4

Output 2

718185656

Input 3

100 10000000 6 6

Output 3

146399052

Subtasks

For $100\%$ of the data, it is guaranteed that $1\le L\le R\le 10^9$, $2\le A\le 6$, and $2\le B\le 26$.

Note

If you do not want to memorize long and complex passwords or manually enter them every time you log in, you can also configure a public key for SSH login.