题目背景
高性能计算导论是 T 大学 C 系开设的一门专业选修课。这门课程讲述了高性能计算的基本概念和原理,常见并行编程模型及并行程序的基本编写思路,程序性能分析和优化的基本方法,以及计算机体系结构和程序性能的关系。为了让同学们能够实际体验并行程序的编写、性能分析和优化,课程为同学们提供了五台服务器组成的集群,每台服务器上都配置了 2 socket × 14 core 的处理器和 1 块 GPU。选课的同学可以在集群上进行基于消息传递的并行编程、基于共享内存模型的并行编程和 CUDA 编程。为了防止宝贵的计算资源被滥用(比如偷偷用服务器挖矿),课程在集群使用上有很多的规定,其中就包括要求选课同学使用高强度的集群登录密码。
题目描述
为了确保选课同学使用了较强的集群登录密码,课程组在集群上配置了密码复杂性策略。所有选课的同学在学期初会收到随机生成的初始密码。在使用初始密码登录集群后,集群会要求同学输入新的密码,密码更改完毕后才能正常访问集群。在本题中,我们假设密码复杂性策略为:
- 密码至少包含 L 个字符,且至少包含一个数字和一个字母;
- 密码不能包含连续 A 个重复字符,如
2333
包含了连续 3 个重复字符; - 密码不能包含连续 B 个字符组成的上升序列或下降序列,其中定义上升序列为
0123456789
,ABCDEFGHIJKLMNOPQRSTUVWXYZ
和abcdefghijklmnopqrstuvwxyz
三个字符串中某一个串的连续子串,下降序列为这三个字符串中某一个串的连续子串的反向串,例如:6789
是长度为 4 的上升序列,FED
是长度为 3 的下降序列;90
、AZ
、az
不是上升序列或下降序列;GPU
不是上升序列,因为它不连续;Def
不是上升序列,因为字母大小写不一致(但它包含长度为 2 的上升连续子序列ef
);1112345678999
不是上升序列,但它的子序列123456789
是上升的。
假设密码仅由数字及大小写字母构成。求在长度不超过 R 的所有密码中,有多少个密码满足密码复杂性策略。
输入格式
输入仅一行,包括四个正整数 L,R,A,B,含义如题目描述中所述。保证 1≤L≤R≤109,2≤A≤6,2≤B≤26。
输出格式
输出一个非负整数,表示满足密码复杂性策略且长度不超过 R 的密码数量对 1,000,000,007 取模的结果。
样例数据
样例 1 输入
2 2 2 2
样例 1 输出
1040
样例 1 解释
因为密码必须至少包含一个数字和一个字母,所以满足要求的密码有 2×10×(26×2)=1040 种。
样例 2 输入
12 24 3 4
样例 2 输出
718185656
样例 3 输入
100 10000000 6 6
样例 3 输出
146399052
子任务
对于 100% 的数据,保证 1≤L≤R≤109,2≤A≤6,2≤B≤26。
提示
如果你不想记住又长又复杂的密码,不想每次登录时手动输入密码,也可以配置公钥进行 SSH 登录。