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 long long mod = 1000000007;
const int N = 2005;
string pat;
char a[2][N];
bool fw[2][N][N], bw[2][N][N];
int n, m, mxf[2][N][N], mxb[2][N][N];
long long mem[2][N][N];
long long f(int row, int col, int ind) {
  if (ind == m) return 1;
  if (col == n) return 0;
  if (a[row][col] != pat[ind]) return 0;
  if (mem[row][col][ind] != -1) return mem[row][col][ind];
  long long ret = 0;
  int len = m - ind;
  if (len > 2 && len % 2 == 0) {
    if (fw[row][col][len >> 1]) ret++;
  }
  ret += f(row, col + 1, ind + 1);
  if (ind + 1 < m && a[row ^ 1][col] == pat[ind + 1]) {
    ret += f(row ^ 1, col + 1, ind + 2);
  }
  while (ret >= mod) ret -= mod;
  return mem[row][col][ind] = ret;
}
long long compute() {
  for (int row = 0; row < 2; row++) {
    for (int col = 0; col < n; col++) {
      for (int j = 0; j < m; j++) {
        mxb[row][col][j] = 0;
        if (a[row][col] == pat[j]) {
          mxb[row][col][j] = 1;
          if (col > 0 && j + 1 < m)
            mxb[row][col][j] += mxb[row][col - 1][j + 1];
        }
      }
    }
  }
  for (int row = 0; row < 2; row++) {
    for (int col = n - 1; col >= 0; col--) {
      for (int j = 0; j < m; j++) {
        mxf[row][col][j] = 0;
        if (a[row][col] == pat[j]) {
          mxf[row][col][j] = 1;
          if (col + 1 < n && j + 1 < m)
            mxf[row][col][j] += mxf[row][col + 1][j + 1];
        }
      }
    }
  }
  for (int row = 0; row < 2; row++) {
    for (int col = 0; col < n; col++) {
      for (int l = 1; l <= m; l++) {
        bw[row][col][l] = false;
        if (mxb[row][col][0] < l) continue;
        if (mxf[row ^ 1][col - l + 1][l] < l) continue;
        bw[row][col][l] = true;
      }
      for (int l = 1; l <= m; l++) {
        fw[row][col][l] = false;
        if (m - 2 * l < 0) continue;
        if (mxf[row][col][m - 2 * l] < l) continue;
        if (mxb[row ^ 1][col + l - 1][m - l] < l) continue;
        fw[row][col][l] = true;
      }
    }
  }
  memset(mem, -1, sizeof(mem));
  long long ret = 0;
  for (int row = 0; row < 2; row++) {
    for (int col = 0; col < n; col++) {
      ret += f(row, col, 0);
      for (int l = 2; l <= m; l++) {
        if (bw[row][col][l]) {
          ret += f(row ^ 1, col + 1, 2 * l);
        }
      }
    }
  }
  ret %= mod;
  return ret;
}
long long owo() {
  long long ret = 0;
  for (int row = 0; row < 2; row++) {
    for (int col = 0; col < n; col++) {
      if (a[row][col] == pat[0]) ret++;
    }
  }
  return ret;
}
long long uwu() {
  long long ret = 0;
  for (int row = 0; row < 2; row++) {
    for (int col = 1; col < n; col++) {
      if (a[row][col - 1] == pat[0] && a[row][col] == pat[1]) ret++;
      if (a[row][col - 1] == pat[1] && a[row][col] == pat[0]) ret++;
    }
  }
  for (int col = 0; col < n; col++) {
    if (a[0][col] == pat[0] && a[1][col] == pat[1]) ret++;
    if (a[0][col] == pat[1] && a[1][col] == pat[0]) ret++;
  }
  return ret;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  string s;
  cin >> s;
  n = (int)s.size();
  for (int i = 0; i < n; i++) {
    a[0][i] = s[i];
  }
  cin >> s;
  for (int i = 0; i < n; i++) {
    a[1][i] = s[i];
  }
  cin >> pat;
  m = (int)pat.size();
  if (m == 1) {
    cout << owo() << endl;
    exit(0);
  }
  if (m == 2) {
    cout << uwu() << endl;
    exit(0);
  }
  long long ans = compute();
  reverse(pat.begin(), pat.end());
  ans += compute();
  if (m > 2 && m % 2 == 0) {
    for (int row = 0; row < 2; row++) {
      for (int col = 0; col < n; col++) {
        if (fw[row][col][m >> 1]) ans--;
        if (bw[row][col][m >> 1]) ans--;
      }
    }
  }
  ans += mod;
  ans %= mod;
  cout << ans << '\n';
  return 0;
}