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>
const int N = 2003, M = 1000000007;
using namespace std;
int n, m, f1[N], f2[N], g1[N], g2[N];
long long ans;
struct str {
  char s[N];
  int a[N];
  void cal();
} m1, m2, S, T;
namespace hs {
const int B = 10007, M = 1000020221;
int b[N];
inline void ini() {
  b[0] = 1;
  for (int i = 1; i <= max(n, m); i++) b[i] = b[i - 1] * 1ll * B % M;
}
inline void cal(char* s, int* a) {
  int ln = strlen(s);
  for (int i = 0; i < ln; i++) a[i + 1] = (a[i] * 1ll * B + s[i] - 'a') % M;
}
inline int get(int* a, int l, int ln) {
  return (M + (a[l + ln] - a[l] * 1ll * b[ln]) % M) % M;
}
}  // namespace hs
inline bool eq(str& a, int l1, str& b, int l2, int ln) {
  return hs::get(a.a, l1, ln) == hs::get(b.a, l2, ln);
}
inline void sol(bool d = 0) {
  for (int i = 1; i <= m; i++) f1[i] = f2[i] = 0;
  for (int i = 0;; i++) {
    f1[0] = f2[0] = 1;
    for (int j = 0; i + j <= n && j << 1 <= m; j++)
      if (j << 1 < m || d && m > 2) {
        if (eq(m1, i, S, m - j * 2, j) && eq(m2, i, T, 0, j))
          ans += f1[m - (j << 1)];
        if (eq(m2, i, S, m - j * 2, j) && eq(m1, i, T, 0, j))
          ans += f2[m - (j << 1)];
      }
    if (i == n) break;
    for (int j = 0; j <= m; j++)
      g1[j] = f1[j], g2[j] = f2[j], f1[j] = f2[j] = 0;
    for (int j = 0; j < m; j++) {
      if (m1.s[i] == S.s[j]) {
        (f1[j + 1] += (g1[j])) >= M ? f1[j + 1] -= M : 0;
        if (j < m - 2 && j && m2.s[i] == S.s[j + 1])
          (f2[j + 2] += (g1[j])) >= M ? f2[j + 2] -= M : 0;
      }
      if (m2.s[i] == S.s[j]) {
        (f2[j + 1] += (g2[j])) >= M ? f2[j + 1] -= M : 0;
        if (j < m - 2 && j && m1.s[i] == S.s[j + 1])
          (f1[j + 2] += (g2[j])) >= M ? f1[j + 2] -= M : 0;
      }
    }
    for (int j = 1; j <= i + 1 && j << 1 <= m; j++)
      if (j << 1 < m || d) {
        (f1[j << 1] +=
         (eq(m2, i - j + 1, T, m - j, j) && eq(m1, i - j + 1, S, j, j))) >= M
            ? f1[j << 1] -= M
            : 0;
        (f2[j << 1] +=
         (eq(m1, i - j + 1, T, m - j, j) && eq(m2, i - j + 1, S, j, j))) >= M
            ? f2[j << 1] -= M
            : 0;
      }
  }
}
int main() {
  scanf("%s%s%s", m1.s, m2.s, S.s);
  n = strlen(m1.s), m = strlen(S.s);
  hs::ini();
  for (int i = 0; i < m; i++) T.s[i] = S.s[m - i - 1];
  hs::cal(m1.s, m1.a);
  hs::cal(m2.s, m2.a);
  hs::cal(S.s, S.a);
  hs::cal(T.s, T.a);
  sol();
  if (m > 1) swap(S, T), sol(1);
  printf("%d", (ans % M + M) % M);
  cerr << clock() << endl;
}