Vasya and Big Integers
Contest: Educational Codeforces Round 51 (Rated for Div. 2)
Difficulty rating: 2600
Tags: binary search, data structures, dp, hashing, strings

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$$$.

Input format:
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.

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
135
1
15

Example output:
2

Example input:
10000
0
9

Example output:
1

Editorial:
Let's use dynamic programming to solve the problem. Let $$$dp_x$$$ be the number of correct partitions for the long integer $$$a_x a_{x+1} \dots a_{n}$$$.
It's easy to see that if we have two big integers without leading zeroes, we know the lengths of these integers, and these lengths are not equal, then we can determine which integer is greater in $$$O(1)$$$.
We will calculate the answers in the following order: $$$dp_{|a|}, dp_{|a| - 1} \dots dp_1$$$. Suppose we want to calculate $$$dp_x$$$.
Let $$$L$$$ be the minimum position such that the number $$$a_x a_x+1 \dots a_L$$$ meets the following condition: $$$l \le a_x a_x+1 \dots a_L \le r$$$.
Let $$$R$$$ be the maximum position such that the number $$$a_x a_x+1 \dots a_R$$$ meets the following condition $$$l \le a_x a_x+1 \dots a_R \le r$$$.
Initially let's consider $$$L = x + |l|$$$ и $$$R = x + |r|$$$. $$$L$$$ will be less if $$$a_x a_{x + 1} ... a_{x + |l|} < l$$$. $$$R$$$ will be less if $$$a_x a_{x + 1} ... a_{x + |r|} > r$$$.
To determine which of the numbers $$$a_x a_{x + 1} ... a_{x + |l|}$$$ and $$$l$$$ is greater let's calculate z-function for the string $$$l + \# + a$$$, where $$$\#$$$ is any character that doesn't occur in $$$a$$$ and $$$l$$$. After calculating z-function we can easily find the first non-equal character in $$$a_x a_{x + 1} ... a_{x + |l|}$$$ and $$$l$$$, and this character will determine which number is greater. To compare $$$a_x a_{x + 1} ... a_{x + |r|}$$$ and $$$r$$$ we can act the same.
All that's left is to set $$$dp_x$$$ to the sum of $$$dp$$$ values from $$$L$$$ to $$$R$$$. This can be done by maintaining suffix sums.
There is a corner case, which applies when $$$a_x = 0$$$. If $$$l > 0$$$, then $$$dp_x = 0$$$ because we cannot afford any leading zeroes. Otherwise $$$dp_x = dp_{x + 1}$$$.