CF1051E.Vasya and Big Integers

Vasya owns three big integers — $a, l, r$. Let's define a partition of $x$ such a sequence of strings $s_1, s_2, \dots, s_k$ that $s_1 + s_2 + \dots + s_k = x$, where $+$ is a concatanation of strings. $s_i$ is the $i$-th element of the partition. For example, number $12345$ has the following partitions: ["1", "2", "3", "4", "5"], ["123", "4", "5"], ["1", "2345"], ["12345"] and lots of others.

Let's call some partition of $a$ beautiful if each of its elements contains no leading zeros.

Vasya want to know the number of beautiful partitions of number $a$, which has each of $s_i$ satisfy the condition $l \le s_i \le r$. Note that the comparison is the integer comparison, not the string one.

Help Vasya to count the amount of partitions of number $a$ such that they match all the given requirements. The result can be rather big, so print it modulo $998244353$.

瓦西里拥有三个大整数：$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$ 的划分中每个元素均不含前导零，则称其为优美的划分。

瓦西里想知道：满足如下条件的 $a$ 的优美划分的数量是多少？即对划分中的每个元素 $s_i$，均满足 $l \le s_i \le r$。注意，此处的比较是整数比较，而非字符串字典序比较。

请帮助瓦西里计算满足所有给定条件的 $a$ 的划分数量。结果可能非常大，请对 $998244353$ 取模后输出。

The first line contains a single integer $a~(1 \le a \le 10^{1000000})$.

The second line contains a single integer $l~(0 \le l \le 10^{1000000})$.

The third line contains a single integer $r~(0 \le r \le 10^{1000000})$.

It is guaranteed that $l \le r$.

It is also guaranteed that numbers $a, l, r$ contain no leading zeros.

第一行包含一个整数 $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$ 均不含前导零。

Print a single integer — the amount of partitions of number $a$ such that they match all the given requirements modulo $998244353$.

输出一个整数——满足所有给定要求的数字 $a$ 的划分方案数，对 $998244353$ 取模。

In the first test case, there are two good partitions $13+5$ and $1+3+5$.

In the second test case, there is one good partition $1+0+0+0+0$.

在第一个测试用例中，存在两个好的划分：$13+5$ 和 $1+3+5$。

在第二个测试用例中，存在一个好的划分：$1+0+0+0+0$。