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 = 2e3 + 5;
const int md = 1e9 + 7;
string mat[2], pat;
long long n, m, dp[2][maxn][2], pr[2][maxn][2], re, is[2][maxn][maxn],
    ris[2][maxn][maxn];
long long sum(long long a, long long b) { return (a + b) % md; }
long long mul(long long a, long long b) { return (a * b) % md; }
void solve() {
  memset(dp, 0, sizeof dp);
  memset(is, 0, sizeof is);
  memset(ris, 0, sizeof ris);
  for (int r = 0; r < 2; ++r) {
    for (int j = 0; j < m; ++j) {
      is[r][0][j] = mat[r][0] == pat[j];
    }
    for (int i = 1; i < n; ++i) {
      is[r][i][0] = mat[r][i] == pat[0];
      for (int j = 1; j < m; ++j) {
        if (mat[r][i] == pat[j]) is[r][i][j] = is[r][i - 1][j - 1] + 1;
      }
    }
    for (int i = n - 1; i >= 0; i--) {
      ris[r][i][0] = mat[r][i] == pat[0];
      for (int j = 1; j < m; ++j) {
        if (mat[r][i] == pat[j]) ris[r][i][j] = ris[r][i + 1][j - 1] + 1;
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    memcpy(pr, dp, sizeof dp);
    memset(dp, 0, sizeof dp);
    dp[0][0][0] = (mat[0][i] == pat[0]);
    dp[1][0][0] = (mat[1][i] == pat[0]);
    for (int j = 1; j < m; ++j) {
      for (int r = 0; r < 2; ++r)
        if (mat[r][i] == pat[j]) {
          dp[r][j][0] = pr[r][j - 1][0];
          dp[r][j][0] = sum(dp[r][j][0], pr[r][j - 1][1]);
          int x = j + 1;
          if (x % 2 == 0 && x / 2 > 1 && i >= x / 2 - 1) {
            x /= 2;
            dp[r][j][1] =
                sum(dp[r][j][1],
                    (is[r][i][j] >= x) * (ris[r ^ 1][i - x + 1][j - x] >= x));
          }
          dp[r][j][1] += dp[r ^ 1][j - 1][0];
        }
    }
    for (int j = 0; j < m; ++j) {
      if (j == m - 1) {
        re = sum(re, dp[0][j][0] + dp[0][j][1] + dp[1][j][1] + dp[1][j][0]);
        continue;
      }
      for (int r = 0; r < 2; ++r) {
        int x = m - 1 - j;
        if (x % 2) continue;
        x /= 2;
        if (x == 1) continue;
        int y = i + x;
        if (y >= n) continue;
        re = sum(re, dp[r][j][0] * (is[r][y][j + x] >= x) *
                         (ris[r ^ 1][i + 1][m - 1] >= x));
        re = sum(re, dp[r][j][1] * (is[r][y][j + x] >= x) *
                         (ris[r ^ 1][i + 1][m - 1] >= x));
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  for (int i = 0; i < 2; ++i) {
    cin >> mat[i];
  }
  n = mat[0].size();
  cin >> pat;
  m = pat.size();
  if (m == 1) {
    for (auto u : mat[0]) {
      if (u == pat[0]) {
        re = re + 1;
      }
    }
    for (auto u : mat[1]) {
      if (u == pat[0]) {
        re = re + 1;
      }
    }
    cout << re << '\n';
    return 0;
  }
  if (m == 2) {
    for (int r = 0; r < 2; ++r) {
      for (int i = 0; i < n; ++i) {
        if (i > 0 && mat[r][i] == pat[1] && mat[r][i - 1] == pat[0]) {
          re = re + 1;
        }
        if (i < n - 1 && mat[r][i] == pat[1] && mat[r][i + 1] == pat[0]) {
          re = re + 1;
        }
        if (mat[r][i] == pat[1] && mat[r ^ 1][i] == pat[0]) {
          re = re + 1;
        }
      }
    }
    cout << re << '\n';
    return 0;
  }
  solve();
  for (int r = 0; r < 2; ++r) {
    reverse(mat[r].begin(), mat[r].end());
  }
  solve();
  cout << re << '\n';
  return 0;
}