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;
const int MAXN = 2100;
const unsigned long long P = 23917;
const int MOD = 1000000007;
unsigned long long pw[MAXN];
char s[2][MAXN];
char t[MAXN];
unsigned long long hss[2][MAXN];
unsigned long long bhss[2][MAXN];
unsigned long long hst[MAXN];
int n, m;
int ans = 0;
int dp[2][MAXN][MAXN];
void ad(int &a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
}
void initHash() {
  pw[0] = 1;
  for (int i = 1; i < MAXN; ++i) pw[i] = pw[i - 1] * P;
  for (int i = 0; i < 2; ++i) {
    hss[i][0] = 0;
    for (int j = 0; j < n; ++j) hss[i][j + 1] = hss[i][j] * P + s[i][j];
    bhss[i][n] = 0;
    for (int j = n - 1; j >= 0; --j) bhss[i][j] = bhss[i][j + 1] * P + s[i][j];
  }
  hst[0] = 0;
  for (int j = 0; j < m; ++j) hst[j + 1] = hst[j] * P + t[j];
}
unsigned long long getHs(int x, int l, int r) {
  if (x == 0 || x == 1) {
    return hss[x][r] - hss[x][l] * pw[r - l];
  }
  return hst[r] - hst[l] * pw[r - l];
}
unsigned long long getBHs(int x, int l, int r) {
  return bhss[x][l] - bhss[x][r] * pw[r - l];
}
void solve() {
  initHash();
  for (int i = 0; i < 2; ++i)
    for (int j = 0; j < n; ++j)
      for (int k = 0; k <= m; ++k) dp[i][j][k] = 0;
  dp[0][n][0] = 1;
  dp[1][n][0] = 1;
  for (int i = n - 1; i >= 0; --i) {
    dp[0][i][0] = 1;
    dp[1][i][0] = 1;
    if (s[0][i] == t[m - 1]) dp[0][i][1] = 1;
    if (s[1][i] == t[m - 1]) dp[1][i][1] = 1;
    for (int k = 2; k <= m; ++k) {
      if ((n - i) * 2 < k) break;
      if (s[0][i] == t[m - k]) {
        if (s[1][i] == t[m - k + 1]) ad(dp[0][i][k], dp[1][i + 1][k - 2]);
        ad(dp[0][i][k], dp[0][i + 1][k - 1]);
        if (k > 2 && k % 2 == 0) {
          if (getHs(0, i, i + k / 2) == getHs(2, m - k, m - k + k / 2) &&
              getBHs(1, i, i + k / 2) == getHs(2, m - k + k / 2, m))
            ad(dp[0][i][k], 1);
        }
      }
      if (s[1][i] == t[m - k]) {
        if (s[0][i] == t[m - k + 1]) ad(dp[1][i][k], dp[0][i + 1][k - 2]);
        ad(dp[1][i][k], dp[1][i + 1][k - 1]);
        if (k > 2 && k % 2 == 0) {
          if (getHs(1, i, i + k / 2) == getHs(2, m - k, m - k + k / 2) &&
              getBHs(0, i, i + k / 2) == getHs(2, m - k + k / 2, m))
            ad(dp[1][i][k], 1);
        }
      }
    }
    for (int k = 1; k <= m; ++k) {
      if (k == m) {
        ad(ans, dp[0][i][k]);
        ad(ans, dp[1][i][k]);
      }
      if (2 * i >= m - k && m - k > 2 && (m - k) % 2 == 0) {
        int x = (m - k);
        if (getHs(0, i - x / 2, i) == getHs(2, x / 2, x) &&
            getBHs(1, i - x / 2, i) == getHs(2, 0, x / 2))
          ad(ans, dp[0][i][k]);
        if (getHs(1, i - x / 2, i) == getHs(2, x / 2, x) &&
            getBHs(0, i - x / 2, i) == getHs(2, 0, x / 2))
          ad(ans, dp[1][i][k]);
      }
    }
  }
}
int main() {
  scanf(" %s %s %s", s[0], s[1], t);
  n = strlen(s[0]);
  m = strlen(t);
  solve();
  if (m != 1) {
    reverse(s[0], s[0] + n);
    reverse(s[1], s[1] + n);
    solve();
  }
  if (m == 2) {
    for (int i = 0; i < n; ++i) {
      if (s[0][i] == t[0] && s[1][i] == t[1]) --ans;
      if (s[1][i] == t[0] && s[0][i] == t[1]) --ans;
    }
  }
  ad(ans, MOD);
  cout << ans << "\n";
  return 0;
}