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>
template <typename T>
bool Chkmax(T &x, T y) {
  return x < y ? x = y, true : false;
}
template <typename T>
bool Chkmin(T &x, T y) {
  return y < x ? x = y, true : false;
}
template <typename T>
void Readin(T &x) {
  x = 0;
  int c = getchar(), k = 1;
  for (; '0' > c || c > '9'; c = getchar())
    if (c == '-') k = -1;
  for (; '0' <= c && c <= '9'; c = getchar()) x = x * 10 + c - '0';
  x *= k;
}
const int MAXN = 2000 + 300, MOD = 1e9 + 7;
namespace Hash {
const unsigned long long HASHVAL = 2333;
unsigned long long base[MAXN * 2];
void Init() {
  base[0] = 1;
  for (int i = 1, _ = MAXN * 2 - 1; i <= _; i++)
    base[i] = base[i - 1] * HASHVAL;
}
void Hash(char *s, unsigned long long *a) {
  int N = strlen(s + 1);
  a[N] = s[N] - 'a' + 1;
  for (int i = N - 1, _ = 1; i >= _; i--)
    a[i] = a[i + 1] * HASHVAL + s[i] - 'a' + 1;
}
void FHash(char *s, unsigned long long *a) {
  int N = strlen(s + 1);
  a[1] = s[1] - 'a' + 1;
  for (int i = 2, _ = N; i <= _; i++)
    a[i] = a[i - 1] * HASHVAL + s[i] - 'a' + 1;
}
}  // namespace Hash
int n, m;
long long ans;
char mp[2][MAXN], s[MAXN];
unsigned long long ha[2][MAXN], a[MAXN], fha[2][MAXN];
int ldp[2][MAXN][MAXN], udp[2][MAXN][MAXN];
template <typename T>
void Mod(T &x) {
  x %= MOD;
}
void Revel() {
  for (int i = 1, _ = n / 2; i <= _; i++) {
    std::swap(mp[0][i], mp[0][n - i + 1]);
    std::swap(mp[1][i], mp[1][n - i + 1]);
  }
}
bool super[2][MAXN][MAXN];
void Dp() {
  memset(ldp, 0, sizeof(ldp));
  memset(udp, 0, sizeof(udp));
  memset(super, 0, sizeof(super));
  for (int i = 0, _ = 1; i <= _; i++)
    for (int j = 1, _ = n; j <= _; j++) ldp[i][j][1] = (mp[i][j] == s[1]);
  for (int i = 0, _ = 1; i <= _; i++)
    for (int j = 0, _ = n; j <= _; j++) ldp[i][j][0] = 1;
  for (int k = 2, _ = m; k <= _; k++)
    for (int i = 1, _ = n; i <= _; i++)
      for (int o = 0, _ = 1; o <= _; o++) {
        if (mp[o][i] == s[k]) {
          Mod(ldp[o][i][k] = ldp[o][i - 1][k - 1] + udp[o][i - 1][k - 1] +
                             super[o][i - 1][k - 1]);
          udp[o][i][k] = ldp[o ^ 1][i][k - 1];
          int p = i - k / 2 + 1;
          unsigned long long base = Hash::base[k / 2];
          unsigned long long hash1 = fha[o ^ 1][i] - fha[o ^ 1][p - 1] * base;
          unsigned long long hash2 = (ha[o][p] - ha[o][i + 1] * base) * base;
          unsigned long long hash3 = a[1] - a[k + 1] * base * base;
          if (k % 2 == 0 && k / 2 > 1 && hash1 + hash2 == hash3)
            super[o][i][k] = true;
          if (k == m)
            Mod(ans += (long long)ldp[o][i][k] + udp[o][i][k] * (m != 2));
        }
      }
}
void Solve() {
  for (int k = (m == 2 ? 2 : 4); k <= m; k += 2)
    for (int i = 1; i + k / 2 - 1 <= n; i++)
      for (int o = 0; o <= 1; o++) {
        int p = i + k / 2 - 1;
        unsigned long long base = Hash::base[k / 2];
        unsigned long long hash1 =
            (fha[o ^ 1][p] - fha[o ^ 1][i - 1] * base) * base;
        unsigned long long hash2 = ha[o][i] - ha[o][p + 1] * base;
        unsigned long long hash3 = a[m - k + 1];
        if (hash1 + hash2 == hash3)
          Mod(ans += ldp[o][i - 1][m - k] + udp[o][i - 1][m - k] +
                     super[o][i - 1][m - k]);
      }
}
void Case1() {
  for (int i = 0, _ = 1; i <= _; i++)
    for (int j = 1, _ = n; j <= _; j++)
      if (mp[i][j] == s[1]) ans++;
  printf("%lld\n", ans);
}
void Init() {
  n = strlen(mp[0] + 1);
  m = strlen(s + 1);
  Hash::Init();
  Hash::Hash(mp[0], ha[0]);
  Hash::Hash(mp[1], ha[1]);
  Hash::FHash(mp[0], fha[0]);
  Hash::FHash(mp[1], fha[1]);
  Hash::Hash(s, a);
}
int main() {
  if (fopen("E.in", "r") != NULL) {
    freopen("E.in", "r", stdin);
    freopen("E.out", "w", stdout);
  }
  scanf("%s%s%s", mp[0] + 1, mp[1] + 1, s + 1);
  Init();
  if (m == 1)
    Case1();
  else {
    Dp();
    Solve();
    Revel();
    Init();
    Dp();
    if (m != 2) Solve();
    printf("%lld\n", ans);
  }
  return 0;
}