← 返回题目列表

Codeforces · 1051/E

E. Vasya 和大整数

中文机器翻译题面 查看原题

Vasya 拥有三个大整数 — $$$a、l、r$$$。让我们定义 $$$x$$$ 的分区,这样的字符串序列 $$$s_1, s_2, \dots, s_k$$$ 使得 $$$s_1 + s_2 + \dots + s_k = x$$$,其中 $$$+$$$ 是字符串的串联。 $$$s_i$$$ 是分区的第 $$$i$$$ 个元素。例如,数字 $$$12345$$$ 具有以下分区:["1", "2", "3", "4", "5"], ["123", "4", "5"], ["1", "2345"], ["12345"] 等等。

如果 $$$a$$$ 的某个分区的每个元素都不包含前导零,我们就称其为漂亮分区。

Vasya 想知道编号 $$$a$$$ 的漂亮分区的数量,其中每个 $$$s_i$$$ 满足条件 $$$l \le s_i \le r$$$。请注意,比较是整数比较,而不是字符串比较。

帮助 Vasya 计算编号为 $$$a$$$ 的分区数量,使其满足所有给定的要求。结果可能相当大,因此打印它对 $$$998244353$$$ 取模。

输入

第一行包含一个整数$$$a~(1 \le a \le 10^{1000000})$$$。

第二行包含一个整数$$$l~(0 \le l \le 10^{1000000})$$$。

第三行包含一个整数$$$r~(0 \le r \le 10^{1000000})$$$。

保证$$$l \le r$$$。

还保证数字 $$$a、l、r$$$ 不包含前导零。

输出

打印一个整数 - 数字 $$$a$$$ 的分区数量,以便它们匹配所有给定的要求模 $$$998244353$$$。

示例

输入 #1

135
1
15

输出 #1

2

输入 #2

10000
0
9

输出 #2

1

注意

在第一个测试用例中,有两个好的分区 $$$13+5$$$ 和 $$$1+3+5$$$。

在第二个测试用例中,有一个好的分区$$$1+0+0+0+0$$$。