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 base = 27, mod = 1e9 + 7;
char mat[2][2222], str[2222];
int n, m, ans, hs[2222][2222], tx[2][2222][2222];
int dp[2][2002][2002], wss[2][2002][2002];
void solve() {
  int i, j, s, p, q;
  for (i = 0; i < m; i++) {
    hs[i][i] = str[i] - '0' + 1;
    for (j = i + 1; j < m; j++) {
      hs[i][j] = (int)((long long)base * (long long)hs[i][j - 1] % mod) +
                 str[j] - '0' + 1;
      hs[i][j] %= mod;
    }
    for (j = i - 1; j >= 0; j--) {
      hs[i][j] = (int)((long long)base * (long long)hs[i][j + 1] % mod) +
                 str[j] - '0' + 1;
      hs[i][j] %= mod;
    }
  }
  for (j = 0; j < 2; j++) {
    for (i = 0; i < n; i++) {
      tx[j][i][i] = mat[j][i] - '0' + 1;
      for (s = i + 1; s < n; s++) {
        tx[j][i][s] =
            (int)((long long)base * (long long)tx[j][i][s - 1] % mod) +
            mat[j][s] - '0' + 1;
        tx[j][i][s] %= mod;
      }
      for (s = i - 1; s >= 0; s--) {
        tx[j][i][s] =
            (int)((long long)base * (long long)tx[j][i][s + 1] % mod) +
            mat[j][s] - '0' + 1;
        tx[j][i][s] %= mod;
      }
    }
  }
  memset(dp, 0, sizeof(dp));
  for (j = 0; j < 2; j++)
    for (i = 0; i < n; i++) {
      if (mat[j][i] == str[0]) dp[j][i][0] = 1;
    }
  memset(wss, 0, sizeof(wss));
  for (s = 0; s < 2; s++) {
    for (i = 0; i < n; i++) {
      for (j = i - 1; j >= max(0, i - m + 1); j--) {
        if (tx[s][i][j] == hs[0][i - j]) {
          if (2 * (i - j) + 1 < m &&
              tx[1 - s][j][i] == hs[i - j + 1][2 * (i - j) + 1]) {
            if (i + 1 < n && 2 * (i - j) + 2 < m &&
                str[2 * (i - j) + 2] == mat[1 - s][i + 1])
              dp[1 - s][i + 1][2 * (i - j) + 2]++;
            if (s == 0 && 2 * (i - j) + 1 == m - 1) ans++;
          }
        }
      }
      for (j = i + 1; j <= min(n - 1, i + m - 1); j++) {
        if (tx[s][i][j] == hs[m - 1][m - (j - i) - 1]) {
          if (2 * (j - i) + 1 < m &&
              tx[1 - s][i][j] == hs[m - 2 * (j - i) - 2][m - (j - i) - 2]) {
            wss[1 - s][i][m - 2 * (j - i) - 2]++;
            if (s == 0 && m - 2 * (j - i) - 2 == 0) ans++;
          }
        }
      }
    }
  }
  for (i = 0; i < n; i++)
    for (j = 0; j < m; j++) {
      for (s = 0; s < 2; s++) {
        if (dp[s][i][j] == 0) continue;
        if (j >= 1 && wss[s][i][j] != 0) {
          ans += (int)((long long)dp[s][i][j] * (long long)wss[s][i][j] % mod);
          ans %= mod;
        }
        if (j == m - 1) {
          ans = (ans + dp[s][i][j]) % mod;
        }
        if (i + 1 < n && j + 1 < m && mat[s][i + 1] == str[j + 1])
          dp[s][i + 1][j + 1] = (dp[s][i + 1][j + 1] + dp[s][i][j]) % mod;
        if (j + 1 == m - 1 && mat[1 - s][i] == str[j + 1]) {
          if (m > 2 || s == 0) ans = (ans + dp[s][i][j]) % mod;
        }
        if (i + 1 < n && j + 2 < m && mat[1 - s][i] == str[j + 1] &&
            mat[1 - s][i + 1] == str[j + 2])
          dp[1 - s][i + 1][j + 2] =
              (dp[1 - s][i + 1][j + 2] + dp[s][i][j]) % mod;
      }
    }
}
int main() {
  int i;
  scanf("%s%s%s", mat[0], mat[1], str);
  n = strlen(mat[0]);
  m = strlen(str);
  ans = 0;
  solve();
  if (m > 1) {
    for (i = 0; i < m / 2; i++) swap(str[i], str[m - 1 - i]);
    solve();
  }
  printf("%d\n", ans);
  return 0;
}