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 std::cerr;
using std::endl;
const int N = 2e3 + 10, P = 1e9 + 7, PP = 1e9 + 21, K = 13131;
inline int fpow(int x, int y) {
  int ret = 1;
  for (; y; y >>= 1, x = 1ll * x * x % PP)
    if (y & 1) ret = 1ll * ret * x % PP;
  return ret;
}
char map[3][N], str[N];
int n, m;
long long ans, Ans;
long long powK[N * 2], invK[N * 2];
long long hash_map[3][3][N], hash_str_val;
struct Hash {
  long long val;
  int len;
  Hash() { val = len = 0; }
  Hash(long long a, int b) { val = a, len = b; }
  inline Hash operator+(Hash h) {
    return Hash((val * powK[h.len] + h.val) % PP, len + h.len);
  }
  inline bool operator==(Hash h) { return val == h.val && len == h.len; }
  Hash(int d, int o, int l, int r) {
    if (d == 1) {
      val = (hash_map[d][o][r] - hash_map[d][o][l - 1] * powK[r - l + 1] % PP +
             PP) %
            PP;
      len = r - l + 1;
    } else {
      val = (hash_map[d][o][l] - hash_map[d][o][r + 1] * powK[r - l + 1] % PP +
             PP) %
            PP;
      len = r - l + 1;
    }
  }
};
Hash hash_str_pre[N], hash_str_suf[N];
bool st[3][N][N], ed[3][N][N];
long long f[3][N][N], g[3][N][N];
int cnt;
inline void solve() {
  memset(st, 0, sizeof(st));
  memset(ed, 0, sizeof(ed));
  memset(f, 0, sizeof(f));
  memset(g, 0, sizeof(g));
  for (int i = 1; i <= 2; ++i) {
    for (int j = 1; j <= n; ++j) {
      for (int k = 4; k <= m; k += 2) {
        if (j - k / 2 + 1 >= 1) {
          Hash up(2, i, j - k / 2 + 1, j), dn(1, 3 - i, j - k / 2 + 1, j),
              tmp = up + dn;
          if (tmp == hash_str_pre[k]) st[3 - i][j][k] = 1;
        }
        if (j + k / 2 - 1 <= n) {
          Hash up(1, i, j, j + k / 2 - 1), dn(2, 3 - i, j, j + k / 2 - 1),
              tmp = up + dn;
          if (tmp == hash_str_suf[k]) ed[i][j][k] = 1;
        }
      }
    }
  }
  for (int i = 1; i <= 2; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (st[i][j][m]) ++Ans;
      if (ed[i][j][m]) ++Ans;
      for (int k = 0; k <= m; ++k)
        if (j < n && st[i][j][k] && ed[i][j + 1][m - k]) ++ans;
    }
  }
  for (int k = 1; k <= m; ++k) {
    for (int j = 1; j <= n; ++j) {
      for (int i = 1; i <= 2; ++i) {
        if (map[i][j] != str[k]) continue;
        if (k == 1) {
          f[i][j][k] = 1;
        } else {
          if (st[i][j - 1][k - 1]) f[i][j][k] = 1;
        }
        f[i][j][k] += f[i][j - 1][k - 1] + g[i][j - 1][k - 1];
        f[i][j][k] %= P;
        g[i][j][k] += f[3 - i][j][k - 1];
        g[i][j][k] %= P;
      }
    }
  }
  for (int i = 1; i <= 2; ++i)
    for (int j = 1; j <= n; ++j) {
      (ans += f[i][j][m] + g[i][j][m]) %= P;
      for (int k = 1; k <= m; ++k)
        if (ed[i][j + 1][m - k]) (ans += f[i][j][k] + g[i][j][k]) %= P;
    }
}
signed main() {
  scanf("%s %s %s", map[1] + 1, map[2] + 1, str + 1);
  n = strlen(map[1] + 1), m = strlen(str + 1);
  if (m == 1) {
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= 2; ++j) ans += map[j][i] == str[1];
    return std::cout << ans << std::endl, 0;
  }
  if (m == 2) {
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= 2; ++j)
        ans += (map[1][i] == str[j] && map[2][i] == str[3 - j]) +
               (map[1][i] == str[j] && map[1][i + 1] == str[3 - j]) +
               (map[2][i] == str[j] && map[2][i + 1] == str[3 - j]);
    return std::cout << ans << std::endl, 0;
  }
  powK[0] = invK[0] = 1;
  powK[1] = K, invK[1] = fpow(K, PP - 2);
  for (int i = 2; i < N * 2; ++i) {
    powK[i] = powK[i - 1] * powK[1] % PP;
    invK[i] = invK[i - 1] * invK[1] % PP;
  }
  for (int i = 1; i <= n; ++i) {
    hash_map[1][1][i] = (hash_map[1][1][i - 1] * K + map[1][i]) % PP;
    hash_map[1][2][i] = (hash_map[1][2][i - 1] * K + map[2][i]) % PP;
  }
  for (int i = n; i >= 1; --i) {
    hash_map[2][1][i] = (hash_map[2][1][i + 1] * K + map[1][i]) % PP;
    hash_map[2][2][i] = (hash_map[2][2][i + 1] * K + map[2][i]) % PP;
  }
  hash_str_val = 0;
  for (int i = 1; i <= m; ++i) {
    hash_str_val = (hash_str_val * K + str[i]) % PP;
    hash_str_pre[i] = Hash(hash_str_val, i);
  }
  hash_str_val = 0;
  for (int i = m; i >= 1; --i) {
    hash_str_val = (hash_str_val + str[i] * powK[m - i]) % PP;
    hash_str_suf[m - i + 1] = Hash(hash_str_val, m - i + 1);
  }
  solve();
  std::reverse(str + 1, str + m + 1);
  hash_str_val = 0;
  for (int i = 1; i <= m; ++i) {
    hash_str_val = (hash_str_val * K + str[i]) % PP;
    hash_str_pre[i] = Hash(hash_str_val, i);
  }
  hash_str_val = 0;
  for (int i = m; i >= 1; --i) {
    hash_str_val = (hash_str_val + str[i] * powK[m - i]) % PP;
    hash_str_suf[m - i + 1] = Hash(hash_str_val, m - i + 1);
  }
  solve();
  ans = (ans + Ans / 2) % P;
  std::cout << ans << std::endl;
  return 0;
}