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 MOD(1000000000 + 7);
const int Max_N(2050);
const int Max_M(2050);
int N, M, Ans;
char A[2][Max_N], B[2][Max_N], S[Max_M];
constexpr int Mult(int a, int b) { return a * 1LL * b % MOD; }
constexpr int Add(int a, int b) { return a + b >= MOD ? a + b - MOD : a + b; }
inline void update(int &a, int b) { a = Add(a, b); }
void init() {
  scanf("%s", A[0] + 1);
  scanf("%s", A[1] + 1);
  N = strlen(A[0] + 1);
  scanf("%s", S + 1);
  M = strlen(S + 1);
}
void work_1() {
  for (int i = 0; i <= 1; ++i)
    for (int j = 1; j <= N; ++j) update(Ans, S[1] == A[i][j]);
}
void work_2() {
  for (int i = 0; i <= 1; ++i)
    for (int j = 1; j <= N; ++j)
      if (S[1] == A[i][j]) {
        if (i - 1 >= 0) update(Ans, S[2] == A[i - 1][j]);
        if (i + 1 <= 1) update(Ans, S[2] == A[i + 1][j]);
        if (j - 1 >= 1) update(Ans, S[2] == A[i][j - 1]);
        if (j + 1 <= N) update(Ans, S[2] == A[i][j + 1]);
      }
}
int Ren[2][Max_N][Max_M], R[2][Max_N][Max_M], L[2][Max_N][Max_M],
    F[2][Max_N][Max_M][2];
void work(int rev) {
  for (int i = 0; i <= 1; ++i)
    for (int j = 1; j <= N; ++j) B[i][j] = A[i][rev ? (N - j + 1) : j];
  for (int i = 0; i <= 1; ++i)
    for (int j = N; j >= 1; --j)
      for (int k = 1; k <= M; ++k)
        if (B[i][j] == S[k]) {
          L[i][j][k] = 1 + L[i][j + 1][k - 1];
          R[i][j][k] = 1 + R[i][j + 1][k + 1];
        } else
          L[i][j][k] = R[i][j][k] = 0;
  for (int i = 0; i <= 1; ++i)
    for (int j = N; j >= 1; --j)
      for (int k = 1, l; k <= M; ++k) {
        Ren[i][j][k] = 0;
        if (B[i][j] != S[k]) continue;
        Ren[i][j][k] = Ren[i][j + 1][k + 1];
        if (((M - k + 1) & 1) == 0) {
          l = ((M - k + 1) >> 1);
          if (l >= 2 && R[i][j][k] >= l && L[1 - i][j][M] >= l)
            update(Ren[i][j][k], 1);
        }
      }
  memset(F, 0, sizeof(F));
  for (int i = 0; i <= 1; ++i)
    for (int j = 1; j <= N; ++j)
      if (S[1] == B[i][j]) {
        if (i - 1 >= 0) update(F[i - 1][j][2][1], S[2] == B[i - 1][j]);
        if (i + 1 <= 1) update(F[i + 1][j][2][1], S[2] == B[i + 1][j]);
        if (j + 1 <= N) update(F[i][j + 1][2][0], S[2] == B[i][j + 1]);
      }
  for (int k = 3, l; k <= M; ++k) {
    for (int i = 0; i <= 1; ++i)
      for (int j = 1; j <= N; ++j) {
        if ((k & 1) == 0) {
          l = (k >> 1);
          if (j - l + 1 >= 1 && L[1 - i][j - l + 1][l] >= l &&
              R[i][j - l + 1][l + 1] >= l)
            update(F[i][j][k][1], 1);
        }
        for (int fa = 0; fa <= 1; ++fa)
          if (F[i][j][k - 1][fa]) {
            if (B[i][j + 1] == S[k])
              update(F[i][j + 1][k][0], F[i][j][k - 1][fa]);
            if (fa == 0 && B[1 - i][j] == S[k])
              update(F[1 - i][j][k][1], F[i][j][k - 1][fa]);
          }
      }
  }
  for (int i = 0; i <= 1; ++i)
    for (int j = 1; j <= N; ++j)
      for (int fa = 0; fa <= 1; ++fa) update(Ans, F[i][j][M][fa]);
  for (int k = 2; k <= M; ++k)
    for (int i = 0; i <= 1; ++i)
      for (int j = 1; j <= N; ++j)
        if (F[i][j][k][1] && Ren[i][j + 1][k + 1])
          update(Ans, Mult(F[i][j][k][1], Ren[i][j + 1][k + 1]));
  for (int i = 0; i <= 1; ++i)
    for (int j = 1; j <= N; ++j)
      for (int l = M - 2; M - l < l; --l)
        if (L[i][j][l] >= l && R[1 - i][j][l + 1] >= M - l) update(Ans, 1);
}
int main() {
  init();
  if (M == 1)
    work_1();
  else if (M == 2)
    work_2();
  else
    work(0), work(1);
  printf("%d", Ans);
  return 0;
}