Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

E. Вася и длинные числа
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Васи есть три длинных числа — $$$a, l, r$$$. Назовем разбиением длинного числа $$$x$$$ такую последовательность строк $$$s_1, s_2, \dots, s_k$$$, что $$$s_1 + s_2 + \dots + s_k = x$$$, где $$$+$$$ означает конкатенацию строк. При этом $$$s_i$$$ называется $$$i$$$-м элементом разбиения. Например, для числа $$$12345$$$ существуют следующие разбиения: ["1", "2", "3", "4", "5"], ["123", "4", "5"], ["1", "2345"], ["12345"] и многие другие.

Назовем разбиение числа $$$a$$$ хорошим, если каждый его элемент не содержит лидирующих нулей.

Вася хочет знать количество хороших разбиений числа $$$a$$$, где каждый элемент разбиения $$$s_i$$$ будет удовлетворять условию $$$l \le s_i \le r$$$. Обратите внимание, что сравнение происходит по правилам сравнения целых чисел, а не сравнения строк.

Помогите Васе! Сообщите ему количество разбиений числа $$$a$$$, удовлетворяющих описанным выше условиям. Полученное число может быть достаточно велико, поэтому выведите его по модулю $$$998244353$$$.

Входные данные

В первой строке содержится целое число $$$a~(1 \le a \le 10^{1000000})$$$.

Во второй строке содержится целое число $$$l~(0 \le l \le 10^{1000000})$$$.

В третьей строке содержится целое число $$$r~(0 \le r \le 10^{1000000})$$$.

Гарантируется, что $$$l \le r$$$.

Так же гарантируется, что числа $$$a, l, r$$$ не содержат лидирующих нулей.

Выходные данные

Выведите одно целое число — количество разбиений числа $$$a$$$, удовлетворяющих описанным выше условиям, по модулю $$$998244353$$$.

Примеры
Входные данные
135
1
15
Выходные данные
2
Входные данные
10000
0
9
Выходные данные
1
Примечание

В первом тестовом примере существует два хороших разбиения $$$13+5$$$ и $$$1+3+5$$$.

Во втором тестовом примере существует одно хорошее разбиение $$$1+0+0+0+0$$$.