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 mod = (int)1e9 + 7;
const int maxn = 2050;
char mp[2][maxn], str[maxn];
int n, m, dp[3][2][maxn][maxn];
int ext[maxn], mat[maxn][maxn];
void add(int &x, int y) { x = (x + y % mod) % mod; }
void prep(int k) {
  memset(dp[k], 0, sizeof dp[k]);
  for (int t = 0; t < 2; t++) {
    for (int i = 1; i <= n; i++) {
      ext[i] = 0;
      while (ext[i] < min(i, m) && mp[t][i - ext[i]] == str[1 + ext[i]])
        ext[i]++;
    }
    memset(mat, 0, sizeof mat);
    for (int i = n; i > 0; i--)
      for (int j = 1; j <= m; j++)
        mat[i][j] = str[j] != mp[!t][i] ? 0 : mat[i + 1][j + 1] + 1;
    for (int j = 0; j <= n; j++)
      for (int l = 0; l <= m; l++) {
        if (l == 0) {
          dp[k][!t][j][l] = 1;
          continue;
        }
        if (l < 4 || l % 2 || j == 0) continue;
        if (ext[j] >= l / 2 && mat[j - l / 2 + 1][l / 2 + 1] >= l / 2)
          dp[k][!t][j][l] = 1;
      }
  }
}
void solve() {
  for (int i = 0; i < 2; i++)
    for (int j = 0; j <= n; j++)
      for (int z = 0; z <= m; z++) dp[1][i][j][z] = dp[0][i][j][z];
  for (int j = 0; j < n; j++)
    for (int i = 0; i < 2; i++)
      for (int z = 0; z <= m; z++)
        if (dp[1][i][j][z] != 0) {
          if (z + 1 <= m && str[z + 1] == mp[i][j + 1])
            add(dp[1][i][j + 1][z + 1], dp[1][i][j][z]);
          if (z + 2 <= m && str[z + 1] == mp[i][j + 1] &&
              str[z + 2] == mp[!i][j + 1])
            add(dp[1][!i][j + 1][z + 2], dp[1][i][j][z]);
        }
}
int calc() {
  prep(0);
  solve();
  reverse(str + 1, str + 1 + m);
  for (int i = 0; i < 2; i++) reverse(mp[i] + 1, mp[i] + 1 + n);
  prep(2);
  int ans = 0;
  for (int i = 0; i < 2; i++)
    for (int j = 0; j <= n; j++) {
      add(ans, dp[1][i][j][m]);
      for (int z = 0; z < m; z++)
        add(ans, 1ll * dp[1][i][j][z] * dp[2][i][n + 1 - (j + 1)][m - z] % mod);
    }
  return ans;
}
int main() {
  for (int i = 0; i < 2; i++) scanf("%s", mp[i]);
  scanf("%s", str);
  n = strlen(mp[0]);
  m = strlen(str);
  for (int i = n; i > 0; i--) mp[0][i] = mp[0][i - 1], mp[1][i] = mp[1][i - 1];
  for (int i = m; i > 0; i--) str[i] = str[i - 1];
  int ans = calc();
  int two = 0;
  for (int i = 0; i < 2; i++)
    for (int j = 1; j <= n; j++) {
      add(two, dp[0][i][j][m]);
      add(two, dp[2][i][(n + 1) - j][m]);
    }
  for (int j = 1; j <= n; j++) {
    if (m == 1) {
      if (mp[0][j] == str[1]) add(two, 1);
      if (mp[1][j] == str[1]) add(two, 1);
    } else if (m == 2) {
      if (mp[0][j] == str[1] && mp[1][j] == str[2]) add(two, 1);
      if (mp[1][j] == str[1] && mp[0][j] == str[2]) add(two, 1);
    }
  }
  reverse(str + 1, str + 1 + m);
  add(ans, calc());
  add(ans, mod - two);
  printf("%d\n", ans);
  return 0;
}