seuOJ571 - 可靠的猪宝宝

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：2000 ms
• 空间限制：256 MiB
• 题目标签：Div.1, 2025 帆软杯

题目描述

为了确认猪宝宝是一名可靠的中级算法竞赛选手，小 L 给它出了这样一道题。

任意正整数 $x$ 都能被唯一表示为 $\overline{d_md_{m-1}\cdots d_0}$，满足：

• $x=\sum\limits_{i=0}^m10^id_i$。
• $1\le d_m\le9$。
• 对于 $i=0,1,\cdots,m-1$，都有 $0\le d_i\le9$。

称这个正整数 $x$ 是好的，当且仅当它满足以下要求：

• $2,3,5,7$ 都不是 $x$ 的约数。
• 对于 $i=0,1,\cdots,m-3$，都有 $d_{i+3}\ne2$ 或 $d_{i+2}\ne0$ 或 $d_{i+1}\ne2$ 或 $d_i\ne5$。

设 $f(x)$ 是定义在正整数集上的函数。若 $x$ 是好的，则 $f(x)=2025^x$；否则，$f(x)=0$。

给定正整数 $L,R$（$L\le R$），求 $\left(\sum\limits_{i=L}^Rf(i)\right)\bmod(10^9+7)$。

输入格式

一行两个整数 $L,R$（$1\le L\le R\le10^{202512}$）。

输出格式

一行一个整数，表示答案。

样例

样例 1

输入

20249 20257

输出

935315683

解释

只有 $20249$ 是好的。$2025^{20249}\bmod(10^9+7)=935315683$。

样例 2

输入

1 20252025202520252025

输出

423849977