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

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

Difficulty: interview

Starter code:

Solutions:
def kmp(pat,text,t):
    s=pat+"?"+text;
    #z[i] es el tamaño del prefijo mas largo de, formado por una subcadena s[i:...]
    z=[0 for i in range(len(s))]
    L=0;R=0;n=len(s);
    for i in range(1,len(s)):
        if i>R:
            L=R=i
            while R<n and s[R-L]==s[R]:
                R+=1
            z[i]=R-L
            R-=1
        elif z[i-L]+i<=R:
            z[i]=z[i-L]
        else:
            L=i
            while R<n and s[R-L]==s[R]:
                R+=1
            z[i]=R-L
            R-=1
    for i in range(len(pat)+1,len(z)):
        dp[t][i-(len(pat)+1)]=z[i]%len(pat)
from sys import stdin
mod=998244353
a=stdin.readline().strip()
l=stdin.readline().strip()
r=stdin.readline().strip()
x=len(l)
y=len(r)
n=len(a)
dp=[[0 for i in range(len(a))]for j in range(2)]
ans=[0 for i in range(len(a)+1)]
ans[-1]=1
kmp(l,a,0)
kmp(r,a,1)
auxl=x-1
auxr=y-1
acum=[0 for i in range(n+2)]
acum[n]=1
for i in range(n-1,-1,-1):
    if a[i]=="0":
        if l[0]=="0":
            ans[i]=ans[i+1]
        acum[i]=(acum[i+1]+ans[i])%mod
        continue
    if auxl>=n:
        acum[i]=(acum[i+1]+ans[i])%mod
        continue
    if auxl!=auxr:
        if (auxl+i)<n and a[dp[0][i]+i]>=l[dp[0][i]]:
            ans[i]=(ans[i]+ans[i+auxl+1])%mod
        if (auxr+i)<n and a[dp[1][i]+i]<=r[dp[1][i]]:
            ans[i]=(ans[i]+ans[i+auxr+1])%mod
    else:
        if (auxl+i)<n and a[dp[0][i]+i]>=l[dp[0][i]] and a[dp[1][i]+i]<=r[dp[1][i]]:
            ans[i]=(ans[i]+ans[i+auxl+1])%mod
    lim1=auxl+i+2
    lim2=min(auxr+i+1,n+1)
    if lim1<lim2:
        ans[i]=(ans[i]+acum[lim1]-acum[lim2])%mod
    acum[i]=(acum[i+1]+ans[i])%mod
print(ans[0]%mod)