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 = 2010, mo = 1e9 + 7;
char s[2][maxn], t[maxn];
long long ha[2][maxn], hv[2][maxn], ht[maxn];
int f[2][maxn][maxn];
long long p131[maxn], pv131[maxn];
long long ans;
int n, m;
long long getTSub(int l, int r) {
  return (ht[r] - ht[l - 1] + mo) % mo * pv131[l - 1] % mo;
}
long long getHaSub(int pos, int len, int o) {
  return (ha[o][pos + len - 1] - ha[o][pos - 1] + mo) % mo * pv131[pos - 1] %
         mo;
}
long long getHvSub(int pos, int len, int o) {
  return (hv[o][pos - len + 1] - hv[o][pos + 1] + mo) % mo * pv131[n - pos] %
         mo;
}
long long getManoeuvreHash(int pos, int len, int o, int dir) {
  if (dir == -1)
    return (getHaSub(pos - len + 1, len, o) * p131[len] % mo +
            getHvSub(pos, len, o ^ 1)) %
           mo;
  else
    return (getHaSub(pos, len, o) +
            getHvSub(pos + len - 1, len, o ^ 1) * p131[len] % mo) %
           mo;
}
void Solve() {
  for (int i = 1; i <= m; i++) ht[i] = (ht[i - 1] + t[i] * p131[i - 1]) % mo;
  for (int i = 0; i <= n; i++) f[0][i][0] = f[1][i][0] = 1;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) f[0][i][j] = f[1][i][j] = 0;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      for (int o = 0; o <= 1; o++)
        if (s[o][i] == t[j]) {
          (f[o][i][j] += f[o][i - 1][j - 1]) %= mo;
          if ((j & 1) && (j - 1) / 2 >= 2 && (i - (j - 1) / 2) >= 1 &&
              getManoeuvreHash(i - 1, (j - 1) / 2, o, -1) == getTSub(1, j - 1))
            (f[o][i][j] += 1) %= mo;
          if (s[o ^ 1][i] == t[j - 1]) {
            (f[o][i][j] += f[o ^ 1][i - 1][j - 2]) %= mo;
            if (!(j & 1) && (j - 2) / 2 >= 2 && (i - (j - 2) / 2) >= 1 &&
                getManoeuvreHash(i - 1, (j - 2) / 2, o ^ 1, -1) ==
                    getTSub(1, j - 2))
              (f[o][i][j] += 1) %= mo;
          }
          if (!((m - j) & 1) && (m - j) / 2 >= 2 && (i + (m - j) / 2) <= n &&
              getManoeuvreHash(i + 1, (m - j) / 2, o, 1) == getTSub(j + 1, m))
            (ans += f[o][i][j]) %= mo;
        }
  for (int i = 1; i <= n; i++) (ans += (f[0][i][m] + f[1][i][m]) % mo) %= mo;
  if (m & 1) return;
  for (int i = 1; i <= n; i++)
    for (int j = 2; j <= m / 2 - 2; j++)
      if (i - j + 1 >= 1 && i + m / 2 - j <= n)
        for (int o = 0; o <= 1; o++)
          if ((getManoeuvreHash(i, j, o, -1) +
               getManoeuvreHash(i + 1, m / 2 - j, o, 1) * p131[j * 2] % mo) %
                  mo ==
              getTSub(1, m))
            ans++;
}
void SolveManoeuvreHash() {
  if (m == 2) {
    for (int i = 1; i <= n; i++) {
      if (s[0][i] == t[1] && s[1][i] == t[2]) ans--;
      if (s[1][i] == t[1] && s[0][i] == t[2]) ans--;
    }
  }
  if (m == 1) {
    for (int i = 1; i <= n; i++) {
      if (s[0][i] == t[1]) ans--;
      if (s[1][i] == t[1]) ans--;
    }
  }
  ans = (ans + mo) % mo;
  if ((m & 1) || m <= 2) return;
  for (int i = m / 2; i <= n; i++)
    for (int o = 0; o <= 1; o++)
      if (getManoeuvreHash(i, m / 2, o, -1) == getTSub(1, m)) ans++;
  for (int i = 1; i <= n - m / 2 + 1; i++)
    for (int o = 0; o <= 1; o++)
      if (getManoeuvreHash(i, m / 2, o, 1) == getTSub(1, m)) ans++;
  ans %= mo;
}
int main() {
  p131[0] = pv131[0] = 1;
  for (int i = 1; i <= 2000; i++)
    p131[i] = p131[i - 1] * 131 % mo, pv131[i] = pv131[i - 1] * 190839696 % mo;
  scanf("%s%s%s%s", s[0] + 1, s[1] + 1, t + 1, t + 1);
  n = strlen(s[0] + 1);
  m = strlen(t + 1);
  for (int i = 1; i <= n; i++)
    ha[0][i] = (ha[0][i - 1] + s[0][i] * p131[i - 1]) % mo,
    ha[1][i] = (ha[1][i - 1] + s[1][i] * p131[i - 1]) % mo;
  for (int i = n; i >= 1; i--)
    hv[0][i] = (hv[0][i + 1] + s[0][i] * p131[n - i]) % mo,
    hv[1][i] = (hv[1][i + 1] + s[1][i] * p131[n - i]) % mo;
  Solve();
  SolveManoeuvreHash();
  reverse(t + 1, t + 1 + m);
  Solve();
  printf("%lld\n", ans);
  return 0;
}