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 long long MOD = 1000000007, HMOD = 1234321237, HBAS = 23333,
                HIBAS = 1116618209;
int N, K;
char a[2002], b[2002], c[2002];
long long POW[2002], IPOW[2002], HA[2002], HB[2002], HC[2002], HIA[2002],
    HIB[2002];
long long aemp[2002][2002], bemp[2002][2002], aful[2002][2002],
    bful[2002][2002];
inline void add(long long &a, long long b) { (a += b) >= MOD ? a -= MOD : a; }
inline bool AC(int L1, int L2, int LEN) {
  return (HA[L1 + LEN] - HA[L1] + HMOD) * IPOW[L1] % HMOD ==
         (HC[L2 + LEN] - HC[L2] + HMOD) * IPOW[L2] % HMOD;
}
inline bool BC(int L1, int L2, int LEN) {
  return (HB[L1 + LEN] - HB[L1] + HMOD) * IPOW[L1] % HMOD ==
         (HC[L2 + LEN] - HC[L2] + HMOD) * IPOW[L2] % HMOD;
}
inline bool IAC(int L1, int L2, int LEN) {
  return (HIA[L1 + LEN] - HIA[L1] + HMOD) * POW[L1 + LEN] % HMOD ==
         (HC[L2 + LEN] - HC[L2] + HMOD) * IPOW[L2 + 1] % HMOD;
}
inline bool IBC(int L1, int L2, int LEN) {
  return (HIB[L1 + LEN] - HIB[L1] + HMOD) * POW[L1 + LEN] % HMOD ==
         (HC[L2 + LEN] - HC[L2] + HMOD) * IPOW[L2 + 1] % HMOD;
}
long long DP() {
  long long ANS = 0;
  for (int i = 1; i <= N; i++) {
    HA[i] = (HA[i - 1] + a[i] * POW[i]) % HMOD;
    HB[i] = (HB[i - 1] + b[i] * POW[i]) % HMOD;
    HIA[i] = (HIA[i - 1] + a[i] * IPOW[i]) % HMOD;
    HIB[i] = (HIB[i - 1] + b[i] * IPOW[i]) % HMOD;
  }
  for (int i = 1; i <= K; i++) HC[i] = (HC[i - 1] + c[i] * POW[i]) % HMOD;
  for (int i = 0; i <= K; i++)
    for (int j = 0; j <= N; j++)
      aemp[i][j] = bemp[i][j] = aful[i][j] = bful[i][j] = 0;
  for (int i = 0; i + i <= K; i++)
    if (i != 1)
      for (int j = 0; j <= N - i; j++) {
        if (AC(j, i, i) && IBC(j, 0, i)) aful[i + i][j + i]++;
        if (BC(j, i, i) && IAC(j, 0, i)) bful[i + i][j + i]++;
      }
  for (int i = 0; i < K; i++)
    for (int j = 0; j <= N; j++) {
      if (!((K - i) & 1) && K - i != 2) {
        int D = (K - i) >> 1;
        if (j + D <= N) {
          if (AC(j, i, D) && IBC(j, i + D, D)) {
            add(ANS, aemp[i][j]);
            add(ANS, aful[i][j]);
          }
          if (BC(j, i, D) && IAC(j, i + D, D)) {
            add(ANS, bemp[i][j]);
            add(ANS, bful[i][j]);
          }
        }
      }
      if (c[i + 1] == b[j]) add(bful[i + 1][j], aemp[i][j]);
      if (c[i + 1] == a[j]) add(aful[i + 1][j], bemp[i][j]);
      if (c[i + 1] == a[j + 1]) {
        add(aemp[i + 1][j + 1], aemp[i][j]);
        add(aemp[i + 1][j + 1], aful[i][j]);
      }
      if (c[i + 1] == b[j + 1]) {
        add(bemp[i + 1][j + 1], bemp[i][j]);
        add(bemp[i + 1][j + 1], bful[i][j]);
      }
    }
  for (int j = 0; j <= N; j++) {
    add(ANS, aemp[K][j]);
    add(ANS, aful[K][j]);
    add(ANS, bemp[K][j]);
    add(ANS, bful[K][j]);
  }
  return ANS;
}
int main() {
  POW[0] = IPOW[0] = 1;
  for (int i = 1; i <= 2000; i++) {
    POW[i] = POW[i - 1] * HBAS % HMOD;
    IPOW[i] = IPOW[i - 1] * HIBAS % HMOD;
  }
  scanf("%s%s%s", a + 1, b + 1, c + 1);
  while (a[N + 1]) N++;
  while (c[K + 1]) K++;
  if (K == 1) {
    int O = 0;
    for (int i = 1; i <= N; i++) {
      if (a[i] == c[1]) O++;
      if (b[i] == c[1]) O++;
    }
    printf("%d\n", O);
    return 0;
  }
  long long Zen = DP();
  std::reverse(a + 1, a + N + 1);
  std::reverse(b + 1, b + N + 1);
  add(Zen, DP());
  if (!(K & 1)) {
    int D = K >> 1;
    for (int i = 0; i <= N - D; i++) {
      if (IBC(i, 0, D) && AC(i, D, D)) add(Zen, MOD - 1);
      if (IAC(i, 0, D) && BC(i, D, D)) add(Zen, MOD - 1);
      if (D > 1) {
        if (BC(i, 0, D) && IAC(i, D, D)) add(Zen, MOD - 1);
        if (AC(i, 0, D) && IBC(i, D, D)) add(Zen, MOD - 1);
      }
    }
  }
  printf("%lld\n", Zen);
  return 0;
}