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 = 2e3 + 10, mod = 1e9 + 7;
const int base1 = 37, base2 = 131;
inline int add(int x, int y) { return x + y >= mod ? x + y - mod : x + y; }
inline int dec(int x, int y) { return x - y < 0 ? x - y + mod : x - y; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
inline void Add(int &x, int y) { x = (x + y) % mod; }
int p1[maxn], p2[maxn];
int n, m, ans = 0, f[2][maxn][maxn];
struct str {
  int pre1[maxn], suf1[maxn];
  int pre2[maxn], suf2[maxn];
  char s[maxn];
  int len;
  inline void read() {
    scanf("%s", s + 1), len = strlen(s + 1);
    for (int i = 1; i <= len; ++i) {
      pre1[i] = add(s[i] - 'a' + 1, mul(pre1[i - 1], base1));
      pre2[i] = add(s[i] - 'a' + 1, mul(pre2[i - 1], base2));
    }
    for (int i = len; i >= 1; --i) {
      suf1[i] = add(s[i] - 'a' + 1, mul(base1, suf1[i + 1]));
      suf2[i] = add(s[i] - 'a' + 1, mul(base2, suf2[i + 1]));
    }
  }
  inline pair<int, int> Hash(int l, int r) {
    if (l <= r)
      return make_pair(dec(pre1[r], mul(pre1[l - 1], p1[r - l + 1])),
                       dec(pre2[r], mul(pre2[l - 1], p2[r - l + 1])));
    return make_pair(dec(suf1[r], mul(suf1[l + 1], p1[l - r + 1])),
                     dec(suf2[r], mul(suf2[l + 1], p2[l - r + 1])));
  }
} s1, s2, w;
inline void prework() {
  p1[0] = p2[0] = 1;
  for (int i = 1; i < maxn; ++i)
    p1[i] = mul(p1[i - 1], base1), p2[i] = mul(p2[i - 1], base2);
  s1.read(), s2.read(), w.read();
}
inline void solve(int M, int ret = 0) {
  if (M == 1) {
    for (int i = 1; i <= n; ++i) {
      if (s1.s[i] == w.s[1]) ++ret;
      if (s2.s[i] == w.s[1]) ++ret;
    }
  }
  if (M == 2) {
    for (int i = 1; i <= n; ++i) {
      if (s1.s[i] == w.s[1] && s2.s[i] == w.s[2]) ++ret;
      if (s2.s[i] == w.s[1] && s1.s[i] == w.s[2]) ++ret;
    }
    for (int i = 1; i < n; ++i) {
      if (s1.s[i] == w.s[1] && s1.s[i + 1] == w.s[2]) ++ret;
      if (s1.s[i + 1] == w.s[1] && s1.s[i] == w.s[2]) ++ret;
      if (s2.s[i] == w.s[1] && s2.s[i + 1] == w.s[2]) ++ret;
      if (s2.s[i + 1] == w.s[1] && s2.s[i] == w.s[2]) ++ret;
    }
  }
  printf("%d\n", ret);
}
inline bool operator==(const pair<int, int> &a, const pair<int, int> &b) {
  return a.first == b.first && a.second == b.second;
}
int main() {
  prework(), n = s1.len, m = w.len;
  if (m <= 2) return solve(m), 0;
  f[0][n + 1][0] = f[1][n + 1][0] = 1;
  for (int i = n; i >= 1; --i) {
    f[0][i][0] = f[1][i][0] = 1;
    for (int k = 2; (k + k <= m) && (i + k - 1 <= n); ++k) {
      pair<int, int> t1 = s1.Hash(i, i + k - 1), t2 = s2.Hash(i, i + k - 1),
                     t3 = w.Hash(m, m - k + 1),
                     t4 = w.Hash(m - k - k + 1, m - k);
      if (t1 == t3 && t2 == t4) f[1][i][k + k] = 1;
      if (t2 == t3 && t1 == t4) f[0][i][k + k] = 1;
    }
  }
  for (int i = n; i >= 1; --i) {
    for (int k = 1; k <= m; ++k) {
      if (s1.s[i] == w.s[m - k + 1]) Add(f[0][i][k], f[0][i + 1][k - 1]);
      if (s2.s[i] == w.s[m - k + 1]) Add(f[1][i][k], f[1][i + 1][k - 1]);
      if (k > 1 && s1.s[i] == w.s[m - k + 1] && s2.s[i] == w.s[m - k + 2])
        Add(f[0][i][k], f[1][i + 1][k - 2]);
      if (k > 1 && s2.s[i] == w.s[m - k + 1] && s1.s[i] == w.s[m - k + 2])
        Add(f[1][i][k], f[0][i + 1][k - 2]);
    }
  }
  for (int i = 1; i <= n + 1; ++i) {
    Add(ans, add(f[0][i][m], f[1][i][m]));
    for (int k = 2; (k + k <= m) && (k < i); ++k) {
      pair<int, int> t1 = s1.Hash(i - k, i - 1), t2 = s2.Hash(i - k, i - 1),
                     t3 = w.Hash(k, 1), t4 = w.Hash(k + 1, k + k);
      if (t1 == t3 && t2 == t4) Add(ans, f[1][i][m - k - k]);
      if (t2 == t3 && t1 == t4) Add(ans, f[0][i][m - k - k]);
    }
  }
  memset(f, 0, sizeof f), f[0][n + 1][0] = f[1][n + 1][0] = 1;
  for (int i = n; i >= 1; --i) {
    f[0][i][0] = f[1][i][0] = 1;
    for (int k = 2; (k + k < m) && (i + k - 1 <= n); ++k) {
      pair<int, int> t1 = s1.Hash(i, i + k - 1), t2 = s2.Hash(i, i + k - 1),
                     t3 = w.Hash(1, k), t4 = w.Hash(k + k, k + 1);
      if (t1 == t3 && t2 == t4) f[1][i][k + k] = 1;
      if (t1 == t4 && t2 == t3) f[0][i][k + k] = 1;
    }
  }
  for (int i = n; i >= 1; --i) {
    for (int k = 1; k <= m; ++k) {
      if (s1.s[i] == w.s[k]) Add(f[0][i][k], f[0][i + 1][k - 1]);
      if (s2.s[i] == w.s[k]) Add(f[1][i][k], f[1][i + 1][k - 1]);
      if (m > 2 && k > 1 && s1.s[i] == w.s[k] && s2.s[i] == w.s[k - 1])
        Add(f[0][i][k], f[1][i + 1][k - 2]);
      if (m > 2 && k > 1 && s2.s[i] == w.s[k] && s1.s[i] == w.s[k - 1])
        Add(f[1][i][k], f[0][i + 1][k - 2]);
    }
  }
  for (int i = 1; i <= n + 1; ++i) {
    Add(ans, add(f[0][i][m], f[1][i][m]));
    for (int k = 2; (k + k < m) && (k < i); ++k) {
      pair<int, int> t1 = s1.Hash(i - k, i - 1), t2 = s2.Hash(i - k, i - 1),
                     t3 = w.Hash(m - k + 1, m),
                     t4 = w.Hash(m - k, m - k - k + 1);
      if (t1 == t3 && t2 == t4) Add(ans, f[1][i][m - k - k]);
      if (t1 == t4 && t2 == t3) Add(ans, f[0][i][m - k - k]);
    }
  }
  printf("%d\n", ans);
}