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>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse3,sse4,popcnt,avx,mmx,abm,tune=native")
using namespace std;
namespace output {
void __(short x) { cout << x; }
void __(unsigned x) { cout << x; }
void __(int x) { cout << x; }
void __(long long x) { cout << x; }
void __(unsigned long long x) { cout << x; }
void __(double x) { cout << x; }
void __(long double x) { cout << x; }
void __(char x) { cout << x; }
void __(const char* x) { cout << x; }
void __(const string& x) { cout << x; }
void __(bool x) { cout << (x ? "true" : "false"); }
template <class S, class T>
void __(const pair<S, T>& x) {
  __(1 ? "(" : ""), __(x.first), __(1 ? ", " : " "), __(x.second),
      __(1 ? ")" : "");
}
template <class T>
void __(const vector<T>& x) {
  __(1 ? "{" : "");
  bool _ = 0;
  for (const auto& v : x) __(_ ? 1 ? ", " : " " : ""), __(v), _ = 1;
  __(1 ? "}" : "");
}
template <class T>
void __(const set<T>& x) {
  __(1 ? "{" : "");
  bool _ = 0;
  for (const auto& v : x) __(_ ? 1 ? ", " : " " : ""), __(v), _ = 1;
  __(1 ? "}" : "");
}
template <class T>
void __(const multiset<T>& x) {
  __(1 ? "{" : "");
  bool _ = 0;
  for (const auto& v : x) __(_ ? 1 ? ", " : " " : ""), __(v), _ = 1;
  __(1 ? "}" : "");
}
template <class S, class T>
void __(const map<S, T>& x) {
  __(1 ? "{" : "");
  bool _ = 0;
  for (const auto& v : x) __(_ ? 1 ? ", " : " " : ""), __(v), _ = 1;
  __(1 ? "}" : "");
}
void pr() { cout << "\n"; }
template <class S, class... T>
void pr(const S& a, const T&... b) {
  __(a);
  if (sizeof...(b)) __(' ');
  pr(b...);
}
}  // namespace output
using namespace output;
const int MN = 2020, mod = 1e9 + 7;
int dpr[MN][2][MN], dpl[MN][2][MN], dps[MN][2][MN], c[MN][2][MN], n, m, i, j, k,
    len, res, hsh[MN][2], rhsh[MN][2], th[MN], pw[MN] = {1}, ans;
string s[2], t;
inline int get(int x, int y, int k) {
  res = (hsh[y][k] - 1LL * hsh[x - 1][k] * pw[y - x + 1]) % mod;
  while (res < 0) res += mod;
  return res;
}
inline int rget(int x, int y, int k) {
  res = (rhsh[x][k] - 1LL * rhsh[y + 1][k] * pw[y - x + 1]) % mod;
  while (res < 0) res += mod;
  return res;
}
inline int tget(int x, int y) {
  res = (th[y] - 1LL * th[x - 1] * pw[y - x + 1]) % mod;
  while (res < 0) res += mod;
  return res;
}
int main() {
  cin >> s[0] >> s[1] >> t;
  n = s[0].size(), m = t.size();
  s[0].insert(s[0].begin(), ' ');
  s[1].insert(s[1].begin(), ' ');
  t.insert(t.begin(), ' ');
  for (i = 1; i <= n; i++) {
    pw[i] = pw[i - 1] * 133LL % mod;
    for (k = 0; k < 2; k++)
      hsh[i][k] = (hsh[i - 1][k] * 133LL + s[k][i] - 'a' + 1) % mod;
  }
  for (i = n; i >= 1; i--) {
    for (k = 0; k < 2; k++)
      rhsh[i][k] = (rhsh[i + 1][k] * 133LL + s[k][i] - 'a' + 1) % mod;
  }
  for (i = 1; i <= m; i++) th[i] = (th[i - 1] * 133LL + t[i] - 'a' + 1) % mod;
  for (i = n; i >= 1; i--) {
    for (k = 0; k < 2; k++) {
      for (j = 1; j <= m; j++) {
        if (s[k][i] == t[j]) {
          if (j == m)
            dpr[i][k][j] = 1;
          else
            dpr[i][k][j] = dpr[i + 1][k][j + 1];
        }
      }
    }
    for (k = 0; k < 2; k++) {
      for (j = 1; j <= m; j++) {
        if (s[k][i] == t[j] && j < m) dps[i][k][j] = dpr[i][!k][j + 1];
      }
    }
    for (k = 0; k < 2; k++) {
      for (j = 1; j <= m; j++) {
        if (s[k][i] == t[j]) {
          dpr[i][k][j] += dps[i][k][j];
          dps[i][k][j] = 0;
          if ((m - j + 1) % 2 == 0 && m - j + 1 >= 4) {
            len = m - j + 1;
            if (i + len / 2 - 1 <= n &&
                get(i, i + len / 2 - 1, k) == tget(j, j + len / 2 - 1) &&
                rget(i, i + len / 2 - 1, !k) == tget(j + len / 2, m))
              dpr[i][k][j]++;
          }
          if (dpr[i][k][j] >= mod) dpr[i][k][j] -= mod;
        }
      }
    }
    for (k = 0; k < 2; k++) ans = (ans + dpr[i][k][1]) % mod;
    for (k = 0; k < 2; k++) {
      for (j = 2; 2 * j < m; j++) {
        if (i + j - 1 <= n && get(i, i + j - 1, k) == tget(1, j) &&
            rget(i, i + j - 1, !k) == tget(j + 1, 2 * j))
          c[i - 1][!k][2 * j + 1]++;
      }
    }
  }
  for (i = 1; i <= n; i++) {
    for (k = 0; k < 2; k++) {
      for (j = 1; j <= m; j++) {
        if (s[k][i] == t[j]) {
          if (j == m && m != 1)
            dpl[i][k][j] = 1;
          else
            dpl[i][k][j] = dpl[i - 1][k][j + 1];
        }
      }
    }
    for (k = 0; k < 2; k++) {
      for (j = 1; j <= m; j++) {
        if (s[k][i] == t[j] && j < m && m != 2)
          dps[i][k][j] = dpl[i][!k][j + 1];
        else
          dps[i][k][j] = 0;
      }
    }
    for (k = 0; k < 2; k++) {
      for (j = 1; j <= m; j++) {
        if (s[k][i] == t[j]) {
          dpl[i][k][j] += dps[i][k][j];
          dps[i][k][j] = 0;
          if ((m - j + 1) % 2 == 0 && m - j + 1 >= 4) {
            len = m - j + 1;
            if (i - len / 2 + 1 >= 1 &&
                rget(i - len / 2 + 1, i, k) == tget(j, j + len / 2 - 1) &&
                get(i - len / 2 + 1, i, !k) == tget(j + len / 2, m))
              dpl[i][k][j]++;
          }
          if (dpl[i][k][j] >= mod) dpl[i][k][j] -= mod;
        }
      }
    }
    for (k = 0; k < 2; k++) ans = (ans + dpl[i][k][1]) % mod;
    for (k = 0; k < 2; k++) {
      for (j = 2; 2 * j < m; j++) {
        if (i - j + 1 >= 1 && rget(i - j + 1, i, k) == tget(1, j) &&
            get(i - j + 1, i, !k) == tget(j + 1, 2 * j))
          ans = (ans + dpr[i + 1][!k][2 * j + 1]) % mod;
      }
    }
    for (k = 0; k < 2; k++) {
      for (j = 1; j <= m; j++)
        ans = (ans + 1LL * dpl[i][k][j] * c[i][k][j]) % mod;
    }
  }
  printf("%d\n", ans);
  return 0;
}