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 = 2010, P = 1000000007;
int n, m, ans, ans2, f[2][maxn][maxn], g[2][maxn][maxn];
int lcp[2][maxn][maxn], lcs[2][maxn][maxn];
bool pre[2][maxn][maxn], suf[2][maxn][maxn];
char s[2][maxn], t[maxn];
void inc(int &x, int y) {
  if ((x += y) >= P) x -= P;
}
int main() {
  scanf("%s %s %s", s[0] + 1, s[1] + 1, t + 1);
  n = strlen(s[0] + 1), m = strlen(t + 1);
  auto solve = [&]() {
    for (int i = n; i; i--) {
      for (int j = m; j; j--) {
        lcp[0][i][j] = s[0][i] == t[j] ? lcp[0][i + 1][j + 1] + 1 : 0;
        lcp[1][i][j] = s[1][i] == t[j] ? lcp[1][i + 1][j + 1] + 1 : 0;
      }
      for (int j = 1; j <= m; j++) {
        lcs[0][i][j] = s[0][i] == t[j] ? lcs[0][i + 1][j - 1] + 1 : 0;
        lcs[1][i][j] = s[1][i] == t[j] ? lcs[1][i + 1][j - 1] + 1 : 0;
      }
    }
    auto chk1 = [&](int x, int y, int k) {
      if (y < k) return 0;
      if (lcs[x ^ 1][y - k + 1][k] < k) return 0;
      if (lcp[x][y - k + 1][k + 1] < k) return 0;
      return 1;
    };
    auto chk2 = [&](int x, int y, int k) {
      if (y + k - 1 > n) return 0;
      if (lcs[x ^ 1][y][m] < k) return 0;
      if (lcp[x][y][m - (k << 1) + 1] < k) return 0;
      return 1;
    };
    memset(f, 0, sizeof(f)), memset(pre, 0, sizeof(pre));
    memset(g, 0, sizeof(g)), memset(suf, 0, sizeof(suf));
    for (int i : {0, 1})
      for (int j = 1; j <= n; j++) {
        for (int k = 1; k <= m; k++) {
          if (k == 1) {
            pre[i][j][k] = g[i][j][k] = s[i][j] == t[1];
            suf[i][j][k] = s[i][j] == t[m];
          } else if (!(k & 1)) {
            pre[i][j][k] = g[i][j][k] = chk1(i, j, k >> 1);
            suf[i][j][k] = chk2(i, j, k >> 1);
          }
          if (k == m) {
            inc(ans2, pre[i][j][k]);
            if (m > 2) inc(ans2, suf[i][j][k]);
          }
        }
      }
    for (int j = 1; j <= n; j++) {
      for (int k = 1; k <= m; k++) {
        for (int i : {0, 1})
          if (s[i][j] == t[k]) {
            inc(f[i][j][k], f[i][j - 1][k - 1]);
            inc(f[i][j][k], g[i][j - 1][k - 1]);
          }
        for (int i : {0, 1})
          if (s[i][j] == t[k]) {
            inc(g[i][j][k], f[i ^ 1][j][k - 1]);
          }
        for (int i : {0, 1})
          if (suf[i][j + 1][m - k]) {
            inc(ans, f[i][j][k]), inc(ans, g[i][j][k]);
          }
      }
    }
  };
  solve(), reverse(t + 1, t + m + 1), solve();
  printf("%d\n", (ans + 1LL * (P + 1) / 2 * ans2) % P);
  return 0;
}