Description

为了确保选课同学使用了较强的集群登录密码，课程组在集群上配置了密码复杂性策略。所有选课的同学在学期初会收到随机生成的初始密码。在使用初始密码登录集群后，集群会要求同学输入新的密码，密码更改完毕后才能正常访问集群。在本题中，我们假设密码复杂性策略为：

• 密码至少包含 $L$ 个字符，且至少包含一个数字和一个字母；

• 密码不能包含连续 $A$ 个重复字符，如 2333 包含了连续 3 个重复字符；

• 密码不能包含连续 $B$ 个字符组成的上升序列或下降序列，其中定义上升序列为 0123456789，ABCDEFGHIJKLMNOPQRSTUVWXYZ 和 abcdefghijklmnopqrstuvwxyz 三个字符串中某一个串的连续子串，下降序列为这三个字符串中某一个串的连续子串的反向串，例如：

  • 6789 是长度为 4 的上升序列，FED 是长度为 3 的下降序列；

  • 90、AZ、az 不是上升序列或下降序列；

  • GPU 不是上升序列，因为它不连续；

  • Def 不是上升序列，因为字母大小写不一致（但它包含长度为 2 的上升连续子序列 ef）；

  • 1112345678999 不是上升序列，但它的子序列 123456789 是上升的。

假设密码仅由数字及大小写字母构成。求在长度不超过 $R$ 的所有密码中，有多少个密码满足密码复杂性策略。

Input Format

输入仅一行，包括四个正整数 $L, R, A, B$，含义如题目描述中所述。

Output Format

输出一个非负整数，表示满足密码复杂性策略且长度不超过 $R$ 的密码数量对 $1,000,000,007$ 取模的结果。

2 2 2 2

1040

12 24 3 4

718185656

100 10000000 6 6

146399052

Hint

【样例 1 解释】

因为密码必须至少包含一个数字和一个字母，所以满足要求的密码有 $2\times 10 \times (26\times 2) = 1040$ 种。

【数据范围与约定】

保证 $1\le L\le R\le 10^9$，$2\le A\le 6$，$2\le B\le 26$。

【提示】

如果你不想记住又长又复杂的密码，不想每次登录时手动输入密码，也可以配置公钥进行 SSH 登录。