Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

E. Vasya and Big Integers
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Vasya owns three big integers — a,l,r. Let's define a partition of x such a sequence of strings s1,s2,,sk that s1+s2++sk=x, where + is a concatanation of strings. si 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 si satisfy the condition lsir. 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 (1a101000000).

The second line contains a single integer l (0l101000000).

The third line contains a single integer r (0r101000000).

It is guaranteed that lr.

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.