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 = 1e9 + 7;
const int maxn = 2000 + 10;
int n, m, ans;
char a[maxn], b[maxn], c[maxn];
int g[2][maxn], w[maxn];
bool left1[2][maxn][maxn], right1[2][maxn][maxn];
bool left2[2][maxn][maxn], right2[2][maxn][maxn];
int suf1[2][maxn][maxn], suf2[2][maxn][maxn];
int dp1[2][maxn][maxn], dp2[2][maxn][maxn];
inline void update1(int i, int j, int k, int val) {
  if (k == m || right1[i][j][k]) (ans += val) %= mod;
}
inline void update2(int i, int j, int k, int val) {
  if (k == m || right2[i][j][k]) (ans += val) %= mod;
}
inline void solve1() {
  for (int i = 0; i <= 1; i++)
    for (int j = n - 1; j >= 0; j--)
      for (int k = m - 1; k >= 0; k--)
        if (g[i][j] == w[k]) suf1[i][j][k] = suf1[i][j + 1][k + 1] + 1;
  for (int i = 0; i <= 1; i++) {
    for (int j = 0, k, len; j < n; j++) {
      k = j;
      len = 0;
      while (k >= 0) {
        if (g[i][k] != w[len++] || (len << 1) > m) break;
        if (k != j) left1[i ^ 1][j + 1][len << 1] = k + suf1[i ^ 1][k][len] > j;
        k--;
      }
    }
    for (int j = n - 1, k, len; j >= 0; j--) {
      k = j;
      len = m;
      while (k < n) {
        if (g[i][k] != w[--len] || (len << 1) < m) break;
        if (j != k)
          right1[i ^ 1][j][(len << 1) - m] =
              j + suf1[i ^ 1][j][(len << 1) - m] > k;
        k++;
      }
    }
  }
  for (int j = 0; j <= n; j++)
    for (int i = 0; i <= 1; i++)
      for (int k = 0; k <= m; k++) {
        if (!k || left1[i][j][k]) (dp1[i][j][k] += 1) %= mod;
        if (dp1[i][j][k]) {
          if (j < n)
            if (k < m && g[i][j] == w[k]) {
              (dp1[i][j + 1][k + 1] += dp1[i][j][k]) %= mod;
              if (k + 1 < m && g[i ^ 1][j] == w[k + 1])
                (dp1[i ^ 1][j + 1][k + 2] += dp1[i][j][k]) %= mod;
            }
          update1(i, j, k, dp1[i][j][k]);
        }
      }
}
inline void solve2() {
  for (int i = 0; i <= 1; i++)
    for (int j = n - 1; j >= 0; j--)
      for (int k = m - 1; k >= 0; k--)
        if (g[i][j] == w[k]) suf2[i][j][k] = suf2[i][j + 1][k + 1] + 1;
  for (int i = 0; i <= 1; i++) {
    for (int j = 0, k, cur; j < n; j++) {
      k = j;
      cur = 0;
      while (k >= 0) {
        if (g[i][k] != w[cur++] || (cur << 1) > m) break;
        if (k != j) left2[i ^ 1][j + 1][cur << 1] = k + suf2[i ^ 1][k][cur] > j;
        k--;
      }
    }
    for (int j = n - 1, k, cur; j >= 0; j--) {
      k = j;
      cur = m;
      while (k < n) {
        if (g[i][k] != w[--cur] || (cur << 1) < m) break;
        if (j != k)
          right2[i ^ 1][j][(cur << 1) - m] =
              j + suf2[i ^ 1][j][(cur << 1) - m] > k;
        k++;
      }
    }
  }
  for (int j = 0; j <= n; j++)
    for (int i = 0; i <= 1; i++)
      for (int k = 0; k <= m; k++) {
        if (!k || left2[i][j][k]) (dp2[i][j][k] += 1) %= mod;
        if (k && k < m) update2(i, j, k, dp2[i][j][k]);
        if (dp2[i][j][k]) {
          if (j < n) {
            if (k < m && g[i][j] == w[k]) {
              (dp2[i][j + 1][k + 1] += dp2[i][j][k]) %= mod;
              if (k && k + 1 == m) update2(i, j + 1, k + 1, dp2[i][j][k]);
            }
            if (k + 1 < m && g[i][j] == w[k] && g[i ^ 1][j] == w[k + 1]) {
              (dp2[i ^ 1][j + 1][k + 2] += dp2[i][j][k]) %= mod;
              if (k && k + 2 == m) update2(i ^ 1, j + 1, k + 2, dp2[i][j][k]);
            }
          }
        }
      }
}
int main() {
  if (fopen("in.in", "r") != NULL) {
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
  }
  scanf("%s%s%s", a, b, c);
  n = strlen(a);
  m = strlen(c);
  for (int i = 0; i < n; i++) {
    g[0][i] = a[i] - 'a';
    g[1][i] = b[i] - 'a';
  }
  for (int i = 0; i < m; i++) w[i] = c[i] - 'a';
  solve1();
  reverse(w, w + m);
  solve2();
  printf("%d\n", ans);
  return 0;
}