Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

data structures

dp

hashing

strings

*2600

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Vasya and Big Integers

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputVasya 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

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

Examples

Input

135

1

15

Output

2

Input

10000

0

9

Output

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/07/2024 00:30:55 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|