6. 简单的数位DP

【题目描述】

我们定义一个数基情无限当且仅当：

1、这个数的各位数字之和不是21的倍数

2、这个数字不能含有1314的数字子串

3、这个数字的各位数字中奇数数字出现的次数是奇数次

4、这个数字不能是8的倍数

5、这个数字的各位数字中不能有7

6、数字中禁止出现5211314这种吊打单身狗的数字子串

现在给定你区间[L,R],请你求出[L,R]中所有基情无限的数字的平方和

【输入格式】

第一行输入T，表示数据组数，T<=100

以下T行，每行输入两个数L，R表示一个区间

保证1<=L，R<=10^18,保证区间合法

【输出格式】

对于每组数据输出答案模1e9+7之后的值

【样例输入】

3
11 41
43 61
8 41

【样例输出】

9577
21480
9758

【提示】论出题人犯逗的必要性