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 NUM_CAND = 4;
const int MOD_LIST[] = {(int)1e9 + 7, (int)1e9 + 9, (int)1e9 + 21,
                        (int)1e9 + 33};
const int NUM_MOD = 2;
int MOD[NUM_MOD];
const int BASE = 31;
void Add(int &a, int b, int mod = MOD_LIST[0]) {
  a += b;
  if (a >= mod) a -= mod;
  if (a < 0) a += mod;
}
int Sum(int a, int b, int mod = MOD_LIST[0]) {
  Add(a, b, mod);
  return a;
}
int Mul(int a, int b, int mod = MOD_LIST[0]) { return (long long)a * b % mod; }
const int N = 2e3 + 2;
long long pw[NUM_MOD][N];
struct THash {
  int val[NUM_MOD] = {};
  int &operator[](int id) { return val[id]; }
  int operator[](int id) const { return val[id]; }
  THash() {}
  THash(char ch) { val[0] = val[1] = ch; }
};
inline bool operator==(const THash &a, const THash &b) {
  for (int i = 0; i < NUM_MOD; ++i)
    if (a[i] != b[i]) return false;
  return true;
}
inline THash operator+(const THash &a, const THash &b) {
  THash ret;
  for (int i = 0; i < NUM_MOD; ++i) ret[i] = Sum(a[i], b[i], MOD[i]);
  return ret;
}
inline THash operator-(const THash &a, const THash &b) {
  THash ret;
  for (int i = 0; i < NUM_MOD; ++i) ret[i] = Sum(a[i], -b[i], MOD[i]);
  return ret;
}
inline THash operator*(const THash &a, int factor) {
  THash ret;
  for (int i = 0; i < NUM_MOD; ++i) ret[i] = Mul(a[i], pw[i][factor], MOD[i]);
  return ret;
}
struct THashed {
  THash hashVal = {};
  int len = 0;
  THashed() {}
  THashed(THash hashVal_, int len_) : hashVal(hashVal_), len(len_) {}
  THashed(char ch) : hashVal(ch), len(1) {}
};
inline THashed operator+(const THashed &a, const THashed &b) {
  return {a.hashVal * b.len + b.hashVal, a.len + b.len};
}
inline THashed operator-(const THashed &a, const THashed &b) {
  return {a.hashVal - b.hashVal * (a.len - b.len), a.len - b.len};
}
inline bool operator==(const THashed &a, const THashed &b) {
  return a.len == b.len && a.hashVal == b.hashVal;
}
inline THashed Get(THashed _a[], int _l, int _r) { return _a[_r] - _a[_l - 1]; }
int n, m;
string text[2], pattern;
void Randomize() {
  auto seed = chrono::high_resolution_clock::now().time_since_epoch() /
              chrono::nanoseconds(1);
  mt19937 mt(seed);
  vector<int> perm(NUM_CAND);
  for (int i = 0; i < NUM_CAND; ++i) {
    perm[i] = i;
    if (i > 0) {
      int j = uniform_int_distribution<int>(0, i)(mt);
      swap(perm[i], perm[j]);
    }
  }
  for (int i = 0; i < NUM_MOD; ++i) {
    MOD[i] = MOD_LIST[perm[i]];
    pw[i][0] = 1;
    for (int j = 1; j < N; ++j) pw[i][j] = Mul(pw[i][j - 1], BASE, MOD[i]);
  }
}
THashed fw[2][N], bw[2][N], pat[N];
void BuildHash() {
  for (int i = 1; i <= n; ++i) {
    fw[0][i] = fw[0][i - 1] + THashed(text[0][i]);
    fw[1][i] = fw[1][i - 1] + THashed(text[1][i]);
  }
  for (int i = n; i >= 1; --i) {
    bw[0][i] = bw[0][i + 1] + THashed(text[0][i]);
    bw[1][i] = bw[1][i + 1] + THashed(text[1][i]);
  }
  for (int i = 1; i <= m; ++i) {
    pat[i] = pat[i - 1] + THashed(pattern[i]);
  }
}
int fpref[N][N][2], fsuff[N][N][2];
void CalcFunc() {
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j < m; ++j)
      for (int row = 0; row < 2; ++row)
        if (text[row][i] == pattern[m - j + 1]) {
          if (j == 1)
            fpref[i][j][row] = 1;
          else {
            fpref[i][j][row] = fpref[i - 1][j - 1][row];
            if (text[!row][i] == pattern[m - j + 2]) {
              Add(fpref[i][j][row], j > 2 ? fpref[i - 1][j - 2][!row] : 1);
            }
            if (j % 2 == 0 && j > 2 && i * 2 >= j) {
              int half = j / 2;
              THashed val = bw[row][i - half + 1] - bw[row][i + 1];
              val = val + (fw[!row][i] - fw[!row][i - half]);
              if (val == pat[m] - pat[m - j]) Add(fpref[i][j][row], 1);
            }
          }
        }
  for (int i = n; i >= 1; --i)
    for (int j = 1; j < m; ++j)
      for (int row = 0; row < 2; ++row)
        if (text[row][i] == pattern[m - j + 1]) {
          if (j == 1)
            fsuff[i][j][row] = 1;
          else {
            fsuff[i][j][row] = fsuff[i + 1][j - 1][row];
            if (text[!row][i] == pattern[m - j + 2]) {
              Add(fsuff[i][j][row], j > 2 ? fsuff[i + 1][j - 2][!row] : 1);
            }
            if (j % 2 == 0 && j > 2 && (n - i + 1) * 2 >= j) {
              int half = j / 2;
              THashed val = fw[row][i + half - 1] - fw[row][i - 1];
              val = val + (bw[!row][i] - bw[!row][i + half]);
              if (val == pat[m] - pat[m - j]) Add(fsuff[i][j][row], 1);
            }
          }
        }
}
void Solve() {
  int res = 0;
  for (int row = 0; row < 2; ++row)
    for (int i = 1; i <= n; ++i)
      for (int j = 1; i + j - 1 <= n && j <= m; ++j) {
        if (text[row][i + j - 1] != pattern[j]) break;
        if (j == m)
          Add(res, 1);
        else if (text[!row][i + j - 1] == pattern[j + 1]) {
          if (j + 1 == m)
            Add(res, 1);
          else {
            Add(res, fsuff[i + j][m - j - 1][!row]);
            if (j * 2 >= m)
              Add(res,
                  bw[!row][i + j * 2 - m] - bw[!row][i + j] == pat[m] - pat[j]);
            else
              Add(res,
                  fpref[i - 1][m - j * 2][!row] *
                      (bw[!row][i] - bw[!row][i + j] == pat[j * 2] - pat[j]));
          }
        }
      }
  for (int row = 0; row < 2; ++row)
    for (int i = n; i >= 1; --i)
      for (int j = 1; i - j + 1 >= 1 && j <= m; ++j) {
        if (text[row][i - j + 1] != pattern[j]) break;
        if (j == m && j > 1)
          Add(res, 1);
        else if (text[!row][i - j + 1] == pattern[j + 1] && j > 1) {
          if (j + 1 == m)
            Add(res, 1);
          else {
            Add(res, fpref[i - j][m - j - 1][!row]);
            if (j * 2 >= m)
              Add(res,
                  fw[!row][i + m - j * 2] - fw[!row][i - j] == pat[m] - pat[j]);
            else
              Add(res,
                  fsuff[i + 1][m - j * 2][!row] *
                      (fw[!row][i] - fw[!row][i - j] == pat[j * 2] - pat[j]));
          }
        }
      }
  cout << res;
}
int main() {
  Randomize();
  cin >> text[0] >> text[1] >> pattern;
  n = text[0].size();
  m = pattern.size();
  text[0] = '\0' + text[0];
  text[1] = '\0' + text[1];
  pattern = '\0' + pattern;
  BuildHash();
  CalcFunc();
  Solve();
  return 0;
}