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;
namespace zyt {
template <typename T>
inline bool read(T &x) {
  char c;
  bool f = false;
  x = 0;
  do c = getchar();
  while (c != EOF && c != '-' && !isdigit(c));
  if (c == EOF) return false;
  if (c == '-') f = true, c = getchar();
  do x = x * 10 + c - '0', c = getchar();
  while (isdigit(c));
  if (f) x = -x;
  return true;
}
template <typename T>
inline void write(T x) {
  static char buf[20];
  char *pos = buf;
  if (x < 0) putchar('-'), x = -x;
  do *pos++ = x % 10 + '0';
  while (x /= 10);
  while (pos > buf) putchar(*--pos);
}
const int N = 2010, P = 1e9 + 7;
int n, m;
char s[2][N], str[N];
namespace Hash {
const pair<int, int> seed = pair<int, int>(71, 853),
                     p = pair<int, int>(int(1e9 + 7), int(1e9 + 9));
pair<int, int> pow[N];
pair<int, int> operator+(const pair<int, int> &a, const pair<int, int> &b) {
  return pair<int, int>((a.first + b.first) % p.first,
                        (a.second + b.second) % p.second);
}
pair<int, int> operator-(const pair<int, int> &a, const pair<int, int> &b) {
  return pair<int, int>((a.first - b.first + p.first) % p.first,
                        (a.second - b.second + p.second) % p.second);
}
pair<int, int> operator*(const pair<int, int> &a, const pair<int, int> &b) {
  return pair<int, int>(int((long long)a.first * b.first % p.first),
                        int((long long)a.second * b.second % p.second));
}
void get_h(const char *const str, pair<int, int> *const h) {
  int n = strlen(str);
  h[0] = pair<int, int>(str[0], str[0]);
  for (int i = 1; i < n; i++)
    h[i] = h[i - 1] * seed + pair<int, int>(str[i], str[i]);
}
pair<int, int> extract(const pair<int, int> *const h, const int l,
                       const int r) {
  if (!l)
    return h[r];
  else
    return h[r] - h[l - 1] * pow[r - l + 1];
}
void init() {
  pow[0] = pair<int, int>(1, 1);
  for (int i = 1; i < N; i++) pow[i] = pow[i - 1] * seed;
}
}  // namespace Hash
using namespace Hash;
pair<int, int> h[2][N], h1[N], h2[N];
int f[2][N][N], g[2][N][N];
bool check1(const int i, const int j, int k) {
  if (!k)
    return true;
  else if (j < 0 || j >= n)
    return false;
  else if (k & 1)
    return k == 1 && s[i][j] == str[0];
  else {
    k /= 2;
    return j >= k - 1 &&
           extract(h[i ^ 1], j - k + 1, j) == extract(h2, m - k, m - 1) &&
           extract(h[i], j - k + 1, j) == extract(h1, k, k * 2 - 1);
  }
}
bool check2(const int i, const int j, int k) {
  if (!k)
    return true;
  else if (j < 0 || j >= n)
    return false;
  else if (k & 1)
    return k == 1 && s[i][j] == str[m - 1];
  else {
    k /= 2;
    return j <= n - k &&
           extract(h[i], j, j + k - 1) == extract(h1, m - k * 2, m - k - 1) &&
           extract(h[i ^ 1], j, j + k - 1) == extract(h2, 0, k - 1);
  }
}
int solve(const bool flag) {
  int ans = 0;
  for (int i = 0; i < 2; i++)
    for (int j = -1; j < n; j++)
      for (int k = flag && m > 2 ? 0 : 1; k <= (flag ? m : m - 1); k++)
        if (check1(i, j, k) && check2(i, j + 1, m - k)) ++ans;
  if (m > 2) {
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < n; j++)
        for (int k = 1; k < m - 1; k++)
          if (s[i][j] == str[k] && check1(i, j - 1, k)) f[i][j][k] = 1;
    for (int k = 1; k < m - 2; k++)
      for (int i = 0; i < 2; i++)
        for (int j = 0; j < n; j++) {
          if (s[i ^ 1][j] == str[k + 1])
            g[i ^ 1][j][k + 1] = (g[i ^ 1][j][k + 1] + f[i][j][k]) % P;
          if (j + 1 < n && s[i][j + 1] == str[k + 1]) {
            f[i][j + 1][k + 1] = (f[i][j + 1][k + 1] + f[i][j][k]) % P;
            f[i][j + 1][k + 1] = (f[i][j + 1][k + 1] + g[i][j][k]) % P;
          }
        }
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < n - 1; j++)
        for (int k = 1; k < m - 1; k++) {
          if (check2(i, j + 1, m - k - 1)) {
            ans = (ans + f[i][j][k]) % P;
            ans = (ans + g[i][j][k]) % P;
          }
        }
  }
  return ans;
}
int work() {
  init();
  scanf("%s%s%s", s[0], s[1], str);
  n = strlen(s[0]), m = strlen(str);
  int ans = 0;
  get_h(s[0], h[0]);
  get_h(s[1], h[1]);
  get_h(str, h1);
  reverse(str, str + m);
  get_h(str, h2);
  reverse(str, str + m);
  ans = (ans + solve(true)) % P;
  reverse(str, str + m);
  swap(h1, h2);
  ans = (ans + solve(false)) % P;
  write(ans);
  return 0;
}
}  // namespace zyt
int main() { return zyt::work(); }