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>
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
using namespace ::std;
const int maxn = 2100;
const int mod = 1e9 + 7;
const int base = 373;
void jam(int &a, int b) {
  a += b;
  if (a >= mod) a -= mod;
}
int jamO(int a, int b) {
  a += b;
  if (a >= mod) a -= mod;
  return a;
}
int ok(int a) {
  if (a < 0) a += mod;
  if (a >= mod) a -= mod;
  return a;
}
int zarb(long long a, long long b) { return (a * b) % mod; }
string s[2];
int tav[maxn];
int hw[maxn];
int hs[2][maxn];
int hsr[2][maxn];
string w;
int n, m;
int findHashs(bool x, int l, int r) {
  if (l <= r) {
    if (l == 0) return hs[x][r];
    return ok(hs[x][r] - zarb(hs[x][l - 1], tav[r - l + 1]));
  } else {
    if (l == n - 1) return hsr[x][r];
    return ok(hsr[x][r] - zarb(hsr[x][l + 1], tav[l - r + 1]));
  }
}
int findHashw(int l, int r) {
  if (l == 0) return hw[r];
  return ok(hw[r] - zarb(hw[l - 1], tav[r - l + 1]));
}
bool equal(bool j, int second, int t, int l, int r) {
  if (r - l != abs(t - second) || l < 0 || r >= m || second < 0 || t < 0 ||
      second >= n || t >= n)
    return 0;
  return (findHashw(l, r) == findHashs(j, second, t));
}
void bildhashS() {
  for (int j = 0; j < 2; j++) {
    hs[j][0] = s[j][0];
    for (int i = 1; i < n; i++) {
      hs[j][i] = jamO(zarb(hs[j][i - 1], base), s[j][i]);
    }
    hsr[j][n - 1] = s[j][n - 1];
    for (int i = n - 2; i >= 0; i--) {
      hsr[j][i] = jamO(zarb(hsr[j][i + 1], base), s[j][i]);
    }
  }
}
void bildhashw() {
  tav[0] = 1;
  for (int i = 1; i < maxn; i++) {
    tav[i] = zarb(tav[i - 1], base);
  }
  hw[0] = w[0];
  for (int i = 1; i < m; i++) {
    hw[i] = jamO(zarb(hw[i - 1], base), w[i]);
  }
}
int dp[2][maxn][2][maxn];
void bilddp(bool b) {
  for (int i = n - 1; i >= 0; i--) {
    for (int k = m - 1; k >= 0; k--) {
      for (int j = 0; j < 2; j++) {
        if (s[j][i] == w[k]) {
          if (k == m - 1) {
            dp[b][i][j][k]++;
          } else {
            if (w[k + 1] == s[!j][i]) {
              if (k != m - 2) {
                jam(dp[b][i][j][k], dp[b][i + 1][!j][k + 2]);
              }
            }
            jam(dp[b][i][j][k], dp[b][i + 1][j][k + 1]);
            if ((m & 1) == (k & 1)) {
              int tol = m - k;
              if (equal(j, i, i + tol / 2 - 1, k, k + tol / 2 - 1) &&
                  equal(!j, i + tol / 2 - 1, i, k + tol / 2, m - 1)) {
                dp[b][i][j][k]++;
              }
            }
          }
        }
      }
    }
  }
}
int getAns() {
  int ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 2; j++) {
      for (int k = 0; k < n; k++) {
        int tol = abs(k - i) + 1;
        if (equal(j, i, k, 0, tol - 1)) {
          if (tol < m) {
            if (w[tol] == s[!j][k]) {
              if (tol < m - 1) {
                if (i <= k) {
                  jam(ans, dp[0][k + 1][!j][tol + 1]);
                } else {
                  if (k) jam(ans, dp[1][k - 1][!j][tol + 1]);
                }
                if (2 * tol < m) {
                  if (equal(!j, k, i, tol, 2 * tol - 1)) {
                    if (i <= k) {
                      if (i) jam(ans, dp[1][i - 1][!j][2 * tol]);
                    } else {
                      jam(ans, dp[0][i + 1][!j][2 * tol]);
                    }
                  }
                } else {
                  int res = -m + 1 + tol;
                  if (k < i) res *= -1;
                  ans += equal(!j, k, k + res, tol, m - 1);
                }
              } else {
                ans++;
              }
            }
          } else {
            ans++;
          }
        }
      }
    }
  }
  ans %= mod;
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> s[0] >> s[1] >> w;
  n = s[0].size();
  m = w.size();
  bildhashw();
  bildhashS();
  bilddp(0);
  reverse(s[0].begin(), s[0].end());
  reverse(s[1].begin(), s[1].end());
  bildhashS();
  bilddp(1);
  reverse(s[0].begin(), s[0].end());
  reverse(s[1].begin(), s[1].end());
  bildhashS();
  {
    bool b = 1;
    for (int u = 0; u < n - u - 1; u++) {
      for (int j = 0; j < 2; j++) {
        for (int i = 0; i < m; i++) {
          swap(dp[b][u][j][i], dp[b][n - u - 1][j][i]);
        }
      }
    }
  }
  cout << getAns();
}