#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void upmax(T &first, T second) {
  first < second ? first = second : 0;
}
template <typename T>
inline void upmin(T &first, T second) {
  first > second ? first = second : 0;
}
template <typename T>
inline void read(T &first) {
  char c;
  while ((c = getchar()) < '0' || c > '9')
    ;
  for (first = c - '0'; (c = getchar()) >= '0' && c <= '9';
       first = first * 10 + c - '0')
    ;
}
const int mo = 1e9 + 7;
const int N = 1e5 + 10;
inline void upd(int &first, int second) {
  (first += second) >= mo ? first -= mo : 0;
}
class AC_Automaton {
 private:
  struct node {
    int ch[10], fail;
    int val;
  } t[N];
  int f[2][N][2][2];
  int tot, Root;

 public:
  void init() {
    Root = 1;
    tot = 2;
  }
  void insert(char *s, int n) {
    int o = Root;
    for (int i = (0), _ = (n - 1); i <= _; ++i) {
      int &to = t[o].ch[s[i] - '0'];
      if (!to) to = tot++;
      o = to;
    }
    t[o].val = 1;
  }
  void build() {
    queue<int> Q;
    for (int i = (0), _ = (9); i <= _; ++i) {
      if (t[Root].ch[i]) {
        t[t[Root].ch[i]].fail = Root;
        Q.push(t[Root].ch[i]);
      } else {
        t[Root].ch[i] = Root;
      }
    }
    while (!Q.empty()) {
      int u = Q.front();
      Q.pop();
      for (int i = (0), _ = (9); i <= _; ++i) {
        if (t[u].ch[i]) {
          t[t[u].ch[i]].fail = t[t[u].fail].ch[i];
          Q.push(t[u].ch[i]);
        } else {
          t[u].ch[i] = t[t[u].fail].ch[i];
        }
      }
    }
  }
  bool check(char *s, int n) {
    int o = Root, res = 0;
    for (int i = (0), _ = (n - 1); i <= _; ++i) {
      o = t[o].ch[s[i] - '0'];
      res |= t[o].val;
    }
    return res;
  }
  int DP(char *s, int len) {
    int p = 0;
    memset(f[0], 0, sizeof(int) * (tot * 4));
    f[p][1][0][0] = 1;
    for (int i = (0), _ = (len - 1); i <= _; ++i) {
      memset(f[p ^ 1], 0, sizeof(int) * (tot * 4));
      int v = s[i] - '0';
      for (int j = (1), _ = (tot - 1); j <= _; ++j) {
        if (t[j].val) {
          for (int k = (0), _ = (1); k <= _; ++k) {
            upd(f[p][j][1][k], f[p][j][0][k]);
            f[p][j][0][k] = 0;
          }
        }
        for (int l = (0), _ = (1); l <= _; ++l) {
          int first = f[p][j][l][0];
          if (first) {
            for (int a = (0), _ = (v); a <= _; ++a) {
              upd(f[p ^ 1][t[j].ch[a]][l][a < v], first);
            }
          }
          first = f[p][j][l][1];
          if (first) {
            for (int a = (0), _ = (9); a <= _; ++a) {
              upd(f[p ^ 1][t[j].ch[a]][l][1], first);
            }
          }
        }
      }
      p ^= 1;
    }
    int ans = 0;
    for (int j = (1), _ = (tot - 1); j <= _; ++j) {
      for (int l = (0), _ = (1); l <= _; ++l) {
        upd(ans, f[p][j][1][l]);
      }
      if (t[j].val) {
        for (int l = (0), _ = (1); l <= _; ++l) {
          upd(ans, f[p][j][0][l]);
        }
      }
    }
    return ans;
  }
} my;
char str[1015];
char cx[55], cy[55];
int main() {
  scanf("%s", str);
  scanf("%s%s", cx, cy);
  int n = strlen(str), d = strlen(cx);
  int half = d >> 1;
  my.init();
  for (int i = (0), _ = (n - half); i <= _; ++i) {
    my.insert(str + i, half);
  }
  my.build();
  int ans = my.DP(cy, d) - my.DP(cx, d);
  ans += my.check(cx, d);
  ans < 0 ? ans += mo : 0;
  cout << ans << endl;
  return 0;
}

### Prompt

Your challenge is to write a cpp solution to the following problem:

Vasily has recently learned about the amazing properties of number π. In one of the articles it has been hypothesized that, whatever the sequence of numbers we have, in some position, this sequence is found among the digits of number π. Thus, if you take, for example, the epic novel "War and Peace" of famous Russian author Leo Tolstoy, and encode it with numbers, then we will find the novel among the characters of number π.

Vasily was absolutely delighted with this, because it means that all the books, songs and programs have already been written and encoded in the digits of π. Vasily is, of course, a bit wary that this is only a hypothesis and it hasn't been proved, so he decided to check it out.

To do this, Vasily downloaded from the Internet the archive with the sequence of digits of number π, starting with a certain position, and began to check the different strings of digits on the presence in the downloaded archive. Vasily quickly found short strings of digits, but each time he took a longer string, it turned out that it is not in the archive. Vasily came up with a definition that a string of length d is a half-occurrence if it contains a substring of length of at least <image>, which occurs in the archive.

To complete the investigation, Vasily took 2 large numbers x, y (x ≤ y) with the same number of digits and now he wants to find the number of numbers in the interval from x to y, which are half-occurrences in the archive. Help Vasily calculate this value modulo 109 + 7.

Input

The first line contains string s consisting of decimal digits (1 ≤ |s| ≤ 1000) that Vasily will use to search substrings in. According to hypothesis, this sequence of digis indeed occurs in the decimal representation of π, although we can't guarantee that.

The second and third lines contain two positive integers x, y of the same length d (x ≤ y, 2 ≤ d ≤ 50). Numbers x, y do not contain leading zeroes.

Output

Print how many numbers in the segment from x to y that are half-occurrences in s modulo 109 + 7.

Examples

Input

02
10
19


Output

2


Input

023456789
10
19


Output

9


Input

31415926535
10
29


Output

20

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void upmax(T &first, T second) {
  first < second ? first = second : 0;
}
template <typename T>
inline void upmin(T &first, T second) {
  first > second ? first = second : 0;
}
template <typename T>
inline void read(T &first) {
  char c;
  while ((c = getchar()) < '0' || c > '9')
    ;
  for (first = c - '0'; (c = getchar()) >= '0' && c <= '9';
       first = first * 10 + c - '0')
    ;
}
const int mo = 1e9 + 7;
const int N = 1e5 + 10;
inline void upd(int &first, int second) {
  (first += second) >= mo ? first -= mo : 0;
}
class AC_Automaton {
 private:
  struct node {
    int ch[10], fail;
    int val;
  } t[N];
  int f[2][N][2][2];
  int tot, Root;

 public:
  void init() {
    Root = 1;
    tot = 2;
  }
  void insert(char *s, int n) {
    int o = Root;
    for (int i = (0), _ = (n - 1); i <= _; ++i) {
      int &to = t[o].ch[s[i] - '0'];
      if (!to) to = tot++;
      o = to;
    }
    t[o].val = 1;
  }
  void build() {
    queue<int> Q;
    for (int i = (0), _ = (9); i <= _; ++i) {
      if (t[Root].ch[i]) {
        t[t[Root].ch[i]].fail = Root;
        Q.push(t[Root].ch[i]);
      } else {
        t[Root].ch[i] = Root;
      }
    }
    while (!Q.empty()) {
      int u = Q.front();
      Q.pop();
      for (int i = (0), _ = (9); i <= _; ++i) {
        if (t[u].ch[i]) {
          t[t[u].ch[i]].fail = t[t[u].fail].ch[i];
          Q.push(t[u].ch[i]);
        } else {
          t[u].ch[i] = t[t[u].fail].ch[i];
        }
      }
    }
  }
  bool check(char *s, int n) {
    int o = Root, res = 0;
    for (int i = (0), _ = (n - 1); i <= _; ++i) {
      o = t[o].ch[s[i] - '0'];
      res |= t[o].val;
    }
    return res;
  }
  int DP(char *s, int len) {
    int p = 0;
    memset(f[0], 0, sizeof(int) * (tot * 4));
    f[p][1][0][0] = 1;
    for (int i = (0), _ = (len - 1); i <= _; ++i) {
      memset(f[p ^ 1], 0, sizeof(int) * (tot * 4));
      int v = s[i] - '0';
      for (int j = (1), _ = (tot - 1); j <= _; ++j) {
        if (t[j].val) {
          for (int k = (0), _ = (1); k <= _; ++k) {
            upd(f[p][j][1][k], f[p][j][0][k]);
            f[p][j][0][k] = 0;
          }
        }
        for (int l = (0), _ = (1); l <= _; ++l) {
          int first = f[p][j][l][0];
          if (first) {
            for (int a = (0), _ = (v); a <= _; ++a) {
              upd(f[p ^ 1][t[j].ch[a]][l][a < v], first);
            }
          }
          first = f[p][j][l][1];
          if (first) {
            for (int a = (0), _ = (9); a <= _; ++a) {
              upd(f[p ^ 1][t[j].ch[a]][l][1], first);
            }
          }
        }
      }
      p ^= 1;
    }
    int ans = 0;
    for (int j = (1), _ = (tot - 1); j <= _; ++j) {
      for (int l = (0), _ = (1); l <= _; ++l) {
        upd(ans, f[p][j][1][l]);
      }
      if (t[j].val) {
        for (int l = (0), _ = (1); l <= _; ++l) {
          upd(ans, f[p][j][0][l]);
        }
      }
    }
    return ans;
  }
} my;
char str[1015];
char cx[55], cy[55];
int main() {
  scanf("%s", str);
  scanf("%s%s", cx, cy);
  int n = strlen(str), d = strlen(cx);
  int half = d >> 1;
  my.init();
  for (int i = (0), _ = (n - half); i <= _; ++i) {
    my.insert(str + i, half);
  }
  my.build();
  int ans = my.DP(cy, d) - my.DP(cx, d);
  ans += my.check(cx, d);
  ans < 0 ? ans += mo : 0;
  cout << ans << endl;
  return 0;
}

```