Vasya owns three big integers — a, l, r. Let's define a partition of x such a sequence of strings s_1, s_2, ..., s_k that s_1 + s_2 + ... + 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 ≤ s_i ≤ 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 ≤ a ≤ 10^{1000000}).

The second line contains a single integer l~(0 ≤ l ≤ 10^{1000000}).

The third line contains a single integer r~(0 ≤ r ≤ 10^{1000000}).

It is guaranteed that l ≤ 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.
#include <bits/stdc++.h>
using namespace std;
const int N = 1000005, M = 1000005;
const long long MOD = 1e9 + 7;
const double eps = 1e-9;
int n, len[2], dp[N], sum[N], mod = 998244353;
char a[N], l[N], r[N];
vector<int> z[2];
string s[2];
vector<int> ZAlgorithm(string &s) {
  int n = s.size();
  vector<int> z(n);
  int l = 0, r = 0;
  for (int i = 0; i < n; i++) {
    if (i > r) {
      l = i, r = i;
      while (r < n && s[r - i] == s[r]) r++;
      r--;
      z[i] = r - l + 1;
    } else {
      if (r - i + 1 > z[i - l])
        z[i] = z[i - l];
      else {
        l = i;
        while (r < n && s[r - i] == s[r]) r++;
        r--;
        z[i] = r - l + 1;
      }
    }
  }
  return z;
}
int cmp(int idx, int i, int j) {
  int ln = j - i + 1;
  if (ln != len[idx]) return (ln < len[idx] ? -1 : +1);
  int at = z[idx][len[idx] + 1 + i];
  if (at == ln) return 0;
  return a[i + at] < s[idx][at] ? -1 : +1;
}
int main() {
  scanf("%s%s%s", a, l, r);
  n = strlen(a);
  s[0] = string(l) + "#" + string(a);
  s[1] = string(r) + "#" + string(a);
  len[0] = strlen(l);
  len[1] = strlen(r);
  z[0] = ZAlgorithm(s[0]);
  z[1] = ZAlgorithm(s[1]);
  dp[n] = 1;
  sum[n] = 1;
  for (int i = n - 1; i >= 0; i--) {
    if (a[i] == '0') {
      dp[i] = (l[0] == '0' ? dp[i + 1] : 0);
      sum[i] = (sum[i + 1] + dp[i]) % mod;
      continue;
    }
    int L = -1, R = -1;
    int l = i, r = n - 1, m;
    while (l <= r) {
      m = (l + r) / 2;
      if (cmp(0, i, m) >= 0) {
        L = m;
        r = m - 1;
      } else
        l = m + 1;
    }
    l = i, r = n - 1;
    while (l <= r) {
      m = (l + r) / 2;
      if (cmp(1, i, m) <= 0) {
        R = m;
        l = m + 1;
      } else
        r = m - 1;
    }
    R = min(R, n - 1);
    L = min(L, n - 1);
    if (L <= R) dp[i] = (sum[L + 1] - sum[R + 2] + mod) % mod;
    sum[i] = (sum[i + 1] + dp[i]) % mod;
  }
  printf("%d\n", dp[0]);
  return 0;
}
