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;
template <typename T>
inline bool chkmin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T>
inline bool chkmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
const int Mod = 1e9 + 7;
const int maxn = 2000, maxm = 2000;
int n, m;
char a[maxn + 5], b[maxn + 5], c[maxn + 5];
int g[2][maxn + 5];
int w[maxn + 5];
bool ok_left[2][maxn + 5][maxm + 5];
bool ok_right[2][maxn + 5][maxm + 5];
int Max[2][maxn + 5][maxm + 5];
int dp[2][maxn + 5][maxn + 5];
int ans = 0;
inline void update(int i, int j, int k, int val) {
  if (k == m || ok_right[i][j][k]) (ans += val) %= Mod;
}
inline void solve(bool ty) {
  memset(ok_left, 0, sizeof ok_left);
  memset(ok_right, 0, sizeof ok_right);
  memset(Max, 0, sizeof Max);
  for (int i = (0), _end_ = (2); i < _end_; ++i) {
    for (int j = n - 1; j >= 0; --j)
      for (int k = m - 1; k >= 0; --k)
        if (g[i][j] == w[k]) Max[i][j][k] = Max[i][j + 1][k + 1] + 1;
  }
  for (int i = (0), _end_ = (2); i < _end_; ++i) {
    for (int j = (0), _end_ = (n); j < _end_; ++j) {
      int k = j;
      int cur = 0;
      while (k >= 0) {
        if (g[i][k] != w[cur++] || (cur << 1) > m) break;
        if (k != j) ok_left[!i][j + 1][cur << 1] = k + Max[!i][k][cur] > j;
        --k;
      }
    }
    for (int j = n - 1; j >= 0; --j) {
      int k = j;
      int cur = m;
      while (k < n) {
        if (g[i][k] != w[--cur] || (cur << 1) < m) break;
        if (j != k)
          ok_right[!i][j][(cur << 1) - m] = j + Max[!i][j][(cur << 1) - m] > k;
        ++k;
      }
    }
  }
  memset(dp, 0, sizeof dp);
  for (int j = (0), _end_ = (n + 1); j < _end_; ++j) {
    for (int i = (0), _end_ = (2); i < _end_; ++i)
      for (int k = (0), _end_ = (m + 1); k < _end_; ++k) {
        if (!k || ok_left[i][j][k]) (++dp[i][j][k]) %= Mod;
        if (ty && k && k < m) update(i, j, k, dp[i][j][k]);
        if (dp[i][j][k]) {
          if (j < n) {
            if (k < m && g[i][j] == w[k]) {
              (dp[i][j + 1][k + 1] += dp[i][j][k]) %= Mod;
              if (ty && k && k + 1 == m) update(i, j + 1, k + 1, dp[i][j][k]);
            }
            if (k + 1 < m && g[i][j] == w[k] && g[!i][j] == w[k + 1]) {
              (dp[!i][j + 1][k + 2] += dp[i][j][k]) %= Mod;
              if (ty && k && k + 2 == m) update(!i, j + 1, k + 2, dp[i][j][k]);
            }
          }
          if (!ty) update(i, j, k, dp[i][j][k]);
        }
      }
  }
}
int main() {
  scanf("%s%s%s", a, b, c);
  n = strlen(a), m = strlen(c);
  for (int i = (0), _end_ = (n); i < _end_; ++i)
    g[0][i] = a[i] - 'a', g[1][i] = b[i] - 'a';
  for (int i = (0), _end_ = (m); i < _end_; ++i) w[i] = c[i] - 'a';
  ans = 0;
  solve(0);
  reverse(w, w + m);
  solve(1);
  (ans += Mod) %= Mod;
  printf("%d\n", ans);
  return 0;
}