#P1051E. Vasya and Big Integers

    ID: 4420 Type: RemoteJudge 1000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>binary searchdata structuresdphashingstrings*2600

Vasya and Big Integers

No submission language available for this problem.

Description

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

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.

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

Input

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

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

Samples

135
1
15

2

10000
0
9

1

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