Problem: Oleg Petrov loves crossword puzzles and every Thursday he buys his favorite magazine with crosswords and other word puzzles. In the last magazine Oleg found a curious puzzle, and the magazine promised a valuable prize for it's solution. We give a formal description of the problem below.

The puzzle field consists of two rows, each row contains n cells. Each cell contains exactly one small English letter. You also are given a word w, which consists of k small English letters. A solution of the puzzle is a sequence of field cells c1, ..., ck, such that:

  * For all i from 1 to k the letter written in the cell ci matches the letter wi;
  * All the cells in the sequence are pairwise distinct;
  * For all i from 1 to k - 1 cells ci and ci + 1 have a common side.



Oleg Petrov quickly found a solution for the puzzle. Now he wonders, how many distinct solutions are there for this puzzle. Oleg Petrov doesn't like too large numbers, so calculate the answer modulo 109 + 7.

Two solutions ci and c'i are considered distinct if the sequences of cells do not match in at least one position, that is there is such j in range from 1 to k, such that cj ≠ c'j.

Input

The first two lines contain the state of the field for the puzzle. Each of these non-empty lines contains exactly n small English letters.

The next line is left empty.

The next line is non-empty and contains word w, consisting of small English letters.

The length of each line doesn't exceed 2 000.

Output

Print a single integer — the number of distinct solutions for the puzzle modulo 109 + 7.

Examples

Input

code
edoc

code


Output

4


Input

aaa
aaa

aa


Output

14

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
int n, m, f[2][2000 + 5][2000 + 5], g[2][2000 + 5], p[2][2000 + 5][2000 + 5],
    q[2][2000 + 5][2000 + 5];
char w[2000 + 5], s[2][2000 + 5];
struct Hash {
  unsigned long long x, y;
  inline Hash() { x = y = 0; }
  inline Hash(const unsigned long long& a) { x = y = a; }
  inline Hash(const unsigned long long& a, const unsigned long long& b)
      : x(a), y(b) {}
  inline Hash operator+(const Hash& o) const { return Hash(x + o.x, y + o.y); }
  inline Hash operator-(const Hash& o) const { return Hash(x - o.x, y - o.y); }
  inline Hash operator*(const Hash& o) const { return Hash(x * o.x, y * o.y); }
  inline bool operator==(const Hash& o) const { return x == o.x && y == o.y; }
} seed(20050413, 20201118), P[2 * 2000 + 5], U[2000 + 5], V[2000 + 5],
    S[2][2000 + 5];
int ans;
inline void Solve(const int& tg) {
  register int i, j, o;
  for (i = 1; i <= m; ++i) U[i] = U[i - 1] + P[i] * w[i];
  for (i = m; i; --i) V[i] = V[i + 1] + P[m - i + 1] * w[i];
  for (o = 0; o <= 1; ++o)
    for (i = 1; i <= n; ++i)
      for (j = 1; 2 * j <= m && j <= i; ++j)
        p[o][i][j << 1] = (S[o ^ 1][i] - S[o ^ 1][(i - j + 1) - 1]) * P[m] ==
                              (V[1] - V[(j) + 1]) * P[i] &&
                          (S[o][i] - S[o][(i - j + 1) - 1]) * P[j << 1] ==
                              (U[j << 1] - U[(j + 1) - 1]) * P[i];
  for (o = 0; o <= 1; ++o)
    for (i = 1; i <= n; ++i)
      for (j = 1; 2 * j <= m && j <= n - i + 1; ++j)
        q[o][i][j << 1] = (S[o ^ 1][i + j - 1] - S[o ^ 1][(i)-1]) ==
                              (V[m - j + 1] - V[(m) + 1]) * P[i - 1] &&
                          (S[o][i + j - 1] - S[o][(i)-1]) * P[m - j + 1] ==
                              (U[m - j] - U[(m - 2 * j + 1) - 1]) * P[i + j];
  for (memset(f, 0, sizeof(f)), i = 1; i <= n; ++i) {
    for (j = m; j ^ 2; --j)
      for (o = 0; o <= 1; ++o)
        s[o][i] == w[j] &&
            ((f[o][i][j] += (0LL + p[o][i][j] + f[o][i - 1][j - 1] +
                             (s[o ^ 1][i] == w[j - 1] ? f[o ^ 1][i - 1][j - 2]
                                                      : 0))) >= 1000000007 &&
             (f[o][i][j] -= 1000000007));
    f[0][i][1] = s[0][i] == w[1], f[1][i][1] = s[1][i] == w[1],
    s[0][i] == w[2] && (f[0][i][2] = p[0][i][2] + f[0][i - 1][1]),
    s[1][i] == w[2] && (f[1][i][2] = p[1][i][2] + f[1][i - 1][1]);
  }
  for (o = 0; o <= 1; ++o)
    for (i = 1; i <= n; ++i)
      for (j = 1; j <= m; ++j)
        s[o][i] == w[j] && (q[o][i][m - j + 1] || j == m) &&
            ((ans += (j ^ 1 ? f[o][i - 1][j - 1] : 1)) >= 1000000007 &&
             (ans -= 1000000007));
  if (tg)
    for (o = 0; o <= 1; ++o)
      for (i = 1; i <= n; ++i) p[o][i][m] && ++ans, q[o][i][m] && --ans;
}
int main() {
  register int i, o;
  scanf("%s%s%s", s[0] + 1, s[1] + 1, w + 1), n = strlen(s[0] + 1),
                                              m = strlen(w + 1);
  if (m == 1) {
    for (i = 1; i <= n; ++i) ans += (s[0][i] == w[1]) + (s[1][i] == w[1]);
    return printf("%d\n", ans), 0;
  }
  if (m == 2) {
    for (o = 0; o <= 1; ++o)
      for (i = 1; i <= n; ++i)
        s[o][i] == w[1] &&
            (ans += (s[o][i - 1] == w[2]) + (s[o][i + 1] == w[2]) +
                    (s[o ^ 1][i] == w[2]));
    return printf("%d\n", ans), 0;
  }
  for (P[0] = i = 1; i <= n + m; ++i) P[i] = P[i - 1] * seed;
  for (i = 1; i <= n; ++i)
    S[0][i] = S[0][i - 1] + P[i] * s[0][i],
    S[1][i] = S[1][i - 1] + P[i] * s[1][i];
  return Solve(0), reverse(w + 1, w + m + 1), Solve(1), printf("%d\n", ans), 0;
}