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: VERY_HARD
Tags: String algorithms

Sorting

Data structures

Dynamic programming
Skill types: Dynamic programming

Sorting

Data structures

Starter code:

Solutions:
def kmp(pat, text, t):
	s = pat + '?' + text
	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
	elif 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)