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 long long MAXN = 2e3 + 5;
const long long Mod = 1e9 + 7;
long long LenN, LenM, Ans1, Ans2, Ans, Limit;
long long Hash1[3][MAXN], Hash2[3][MAXN], Hash0[MAXN];
long long F[3][MAXN][MAXN], G[3][MAXN][MAXN];
long long B[MAXN];
char Str[3][MAXN];
long long QP(long long B, long long K, long long Mod) {
  long long Ans = 1;
  for (; K; K >>= 1, B = B * B % Mod)
    if (K & 1) Ans = Ans * B % Mod;
  return Ans % Mod;
}
template <class T>
void Read(T &X) {
  X = 0;
  int F = 0;
  char Ch = getchar();
  while (Ch < '0' || Ch > '9') {
    F |= (Ch == '-');
    Ch = getchar();
  }
  while (Ch >= '0' && Ch <= '9') {
    X = X * 10 + (Ch ^ 48);
    Ch = getchar();
  }
  X = F ? -X : X;
}
inline void Write(long long X) {
  if (X < 0) {
    putchar('-');
    X = -X;
  }
  if (X > 9) Write(X / 10);
  putchar((X % 10) ^ 48);
}
long long GCD(long long X, long long Y) { return Y == 0 ? X : GCD(Y, X % Y); }
long long Get1(long long Row, long long L, long long R) {
  return Hash1[Row][R] - Hash1[Row][L - 1] * B[R - L + 1];
}
long long Get2(long long Row, long long L, long long R) {
  return Hash2[Row][L] - Hash2[Row][R + 1] * B[R - L + 1];
}
long long Mix(long long H1, long long H2, long long Len) {
  return H1 * B[Len] + H2;
}
void Work() {
  memset(F, 0, sizeof(F));
  memset(G, 0, sizeof(G));
  for (long long i = 1; i <= LenM; i++)
    Hash0[i] = Hash0[i - 1] * B[1] + (Str[0][i] - 'a' + 1);
  for (long long i = 1; i <= 2; i++) {
    for (long long j = 1; j <= LenN; j++) {
      for (long long k = j; k >= 1; k--) {
        long long Len = 2 * (j - k + 1);
        if (Len > LenM) continue;
        long long HA = Get1(i, k, j);
        long long HB = Get2(3 - i, k, j);
        long long HH = Hash0[Len];
        if (Mix(HB, HA, j - k + 1) == HH) {
          if (Len == LenM)
            Ans1++;
          else
            G[i][j][Len] = 1;
        }
      }
    }
  }
  for (long long i = 1; i <= 2; i++) {
    for (long long j = 1; j <= LenN; j++)
      if (Str[i][j] == Str[0][1]) {
        G[i][j][1] = 1;
      }
  }
  for (long long k = 1; k <= LenM - 1; k++) {
    for (long long j = 1; j <= LenN; j++) {
      for (long long i = 1; i <= 2; i++) {
        if (G[i][j][k] && j < LenN && Str[i][j + 1] == Str[0][k + 1]) {
          F[i][j + 1][k + 1] += G[i][j][k];
          F[i][j + 1][k + 1] %= Mod;
        }
        if (F[i][j][k] && j < LenN && Str[i][j + 1] == Str[0][k + 1]) {
          F[i][j + 1][k + 1] += F[i][j][k];
          F[i][j + 1][k + 1] %= Mod;
        }
        if (F[i][j][k] && Str[3 - i][j] == Str[0][k + 1]) {
          G[3 - i][j][k + 1] += F[i][j][k];
          G[3 - i][j][k + 1] %= Mod;
        }
      }
    }
  }
  for (long long i = LenM; i >= 1; i--)
    Hash0[i] = Hash0[i + 1] * B[1] + (Str[0][i] - 'a' + 1);
  for (long long i = 1; i <= 2; i++) {
    for (long long j = 1; j <= LenN; j++) {
      if (Str[i][j] == Str[0][LenM]) {
        if (LenM == 1) Ans2++;
        Ans2 += F[i][j - 1][LenM - 1];
        Ans2 += G[i][j - 1][LenM - 1];
        Ans2 %= Mod;
      }
      for (long long k = j; k <= LenN; k++) {
        long long Len = 2 * (k - j + 1);
        if (Len > LenM) continue;
        long long HA = Get1(3 - i, j, k);
        long long HB = Get2(i, j, k);
        long long HH = Hash0[LenM - Len + 1];
        if (Mix(HA, HB, k - j + 1) == HH) {
          if (Len == LenM && LenM != 2)
            Ans1++;
          else {
            Ans2 += F[i][j - 1][LenM - Len];
            Ans2 += G[i][j - 1][LenM - Len];
            Ans2 %= Mod;
          }
        }
      }
    }
  }
}
int main() {
  scanf("%s", Str[1] + 1);
  scanf("%s", Str[2] + 1);
  scanf("%s", Str[0] + 1);
  LenN = strlen(Str[1] + 1);
  LenM = strlen(Str[0] + 1);
  Limit = max(LenN, LenM);
  B[0] = 1;
  B[1] = 131;
  for (long long i = 2; i <= Limit; i++) B[i] = B[i - 1] * 131;
  for (long long i = 1; i <= 2; i++)
    for (long long j = 1; j <= LenN; j++)
      Hash1[i][j] = Hash1[i][j - 1] * B[1] + (Str[i][j] - 'a' + 1);
  for (long long i = 1; i <= 2; i++)
    for (long long j = LenN; j >= 1; j--)
      Hash2[i][j] = Hash2[i][j + 1] * B[1] + (Str[i][j] - 'a' + 1);
  Work();
  for (long long i = 1; i <= LenM / 2; i++) {
    swap(Str[0][i], Str[0][LenM - i + 1]);
  }
  Work();
  Ans = (Ans1 / 2 + Ans2) % Mod;
  if (LenM == 1) Ans /= 2;
  printf("%lld\n", Ans % Mod);
  return 0;
}