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 M = 2e3 + 7;
const int Q = 1e9 + 7;
inline int pls(int x, int y) { return (x + y) % Q; }
inline int mns(int x, int y) { return pls(x, Q - y); }
inline int mul(int x, int y) { return 1LL * x * y % Q; }
int n, m;
char s[2][M], t[M];
int l[M][2][M], r[M][2][M];
bool bl[M][2][M], br[M][2][M];
struct Hsh {
  static const int W = 131;
  unsigned long long lf[M], rt[M], pw[M];
  unsigned long long lfhsh(int x, int len) {
    int y = x + len - 1;
    return lf[y] - lf[x - 1] * pw[len];
  }
  unsigned long long rthsh(int len, int y) {
    int x = y - len + 1;
    return rt[x] - rt[y + 1] * pw[len];
  }
  void init(char *s, int n) {
    int i;
    for (pw[0] = 1, i = 1; i <= n; ++i) pw[i] = pw[i - 1] * W;
    for (lf[0] = 0, i = 1; i <= n; ++i) lf[i] = lf[i - 1] * W + s[i] - 'a';
    for (rt[n + 1] = 0, i = n; i > 0; --i) rt[i] = rt[i + 1] * W + s[i] - 'a';
  }
} hs[2], ht;
void solve() {
  int i, j, k;
  for (i = n; i > 0; --i)
    for (j = 0; j < 2; ++j)
      for (k = 2; k <= m; k += 2)
        br[i][j][k] = (i + k / 2 - 1 <= n &&
                       hs[j].lfhsh(i, k / 2) == ht.lfhsh(m - k + 1, k / 2) &&
                       hs[j ^ 1].rthsh(k / 2, i + k / 2 - 1) ==
                           ht.lfhsh(m - k / 2 + 1, k / 2));
  for (i = 1; i <= n; ++i)
    for (j = 0; j < 2; ++j)
      for (k = 2; k <= m; k += 2)
        bl[i][j][k] = (i - k / 2 + 1 >= 1 &&
                       hs[j].rthsh(k / 2, i) == ht.lfhsh(m - k + 1, k / 2) &&
                       hs[j ^ 1].lfhsh(i - k / 2 + 1, k / 2) ==
                           ht.lfhsh(m - k / 2 + 1, k / 2));
  r[n + 1][0][0] = r[n + 1][1][0] = 1;
  for (i = n; i > 0; --i)
    for (j = 0; j < 2; ++j)
      for (r[i][j][0] = 1, k = 1; k <= m; ++k) {
        if (s[j][i] == t[m - k + 1])
          r[i][j][k] = pls(r[i][j][k], r[i + 1][j][k - 1]);
        if (k > 2 && s[j][i] == t[m - k + 1] && s[j ^ 1][i] == t[m - k + 2])
          r[i][j][k] = pls(r[i][j][k], r[i + 1][j ^ 1][k - 2]);
        if (br[i][j][k]) r[i][j][k] = pls(r[i][j][k], 1);
      }
  l[0][0][0] = l[0][1][0] = 1;
  for (i = 1; i <= n; ++i)
    for (j = 0; j < 2; ++j)
      for (l[i][j][0] = 1, k = 1; k <= m; ++k) {
        if (s[j][i] == t[m - k + 1])
          l[i][j][k] = pls(l[i][j][k], l[i - 1][j][k - 1]);
        if (k > 2 && s[j][i] == t[m - k + 1] && s[j ^ 1][i] == t[m - k + 2])
          l[i][j][k] = pls(l[i][j][k], l[i - 1][j ^ 1][k - 2]);
        if (bl[i][j][k]) l[i][j][k] = pls(l[i][j][k], 1);
      }
  for (i = n; i > 0; --i)
    for (j = 0; j < 2; ++j)
      for (k = 2; k <= m; k += 2)
        br[i][j][k] = (i + k / 2 - 1 <= n &&
                       hs[j].lfhsh(i, k / 2) == ht.lfhsh(1, k / 2) &&
                       hs[j ^ 1].rthsh(k / 2, i + k / 2 - 1) ==
                           ht.lfhsh(k / 2 + 1, k / 2));
  for (i = 1; i <= n; ++i)
    for (j = 0; j < 2; ++j)
      for (k = 2; k <= m; k += 2)
        bl[i][j][k] = (i - k / 2 + 1 >= 1 &&
                       hs[j].rthsh(k / 2, i) == ht.lfhsh(1, k / 2) &&
                       hs[j ^ 1].lfhsh(i - k / 2 + 1, k / 2) ==
                           ht.lfhsh(k / 2 + 1, k / 2));
  int ans = 0;
  for (i = 1; i <= n; ++i)
    for (j = 0; j < 2; ++j) {
      if (s[j][i] == t[1]) {
        ans = pls(ans, pls(l[i - 1][j][m - 1], r[i + 1][j][m - 1]));
        if (m == 1) ans = mns(ans, 1);
      }
      for (k = 2; k <= m; k += 2) {
        if (bl[i][j][k]) ans = pls(ans, r[i + 1][j ^ 1][m - k]);
        if (br[i][j][k]) ans = pls(ans, l[i - 1][j ^ 1][m - k]);
      }
      if (m == 2 && bl[i][j][2]) ans = mns(ans, 1);
    }
  printf("%d\n", ans);
}
int main() {
  int i;
  scanf("%s", s[0] + 1);
  scanf("%s", s[1] + 1);
  scanf("%s", t + 1);
  n = strlen(s[0] + 1);
  m = strlen(t + 1);
  hs[0].init(s[0], n);
  hs[1].init(s[1], n);
  ht.init(t, m);
  solve();
  return 0;
}