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 oo = 0x3f3f3f3f;
template <typename T>
inline bool chkmax(T &a, T b) {
  return a < b ? a = b, true : false;
}
template <typename T>
inline bool chkmin(T &a, T b) {
  return a > b ? a = b, true : false;
}
template <typename T>
T read(T &first) {
  int f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (first = 0; isdigit(ch); ch = getchar()) first = 10 * first + ch - '0';
  return first *= f;
}
const int MAXN = 2e3 + 5, MOD = 1e9 + 7;
const int HASH = 1000000321, BASE = 29;
int N, N0, K;
int A[MAXN][2], W[MAXN];
int ha[MAXN][2], ha0[MAXN][2], hw[MAXN], base[MAXN];
inline void update(int &first, int second) {
  first += second;
  if (first >= MOD) first -= MOD;
}
inline int hashw(int l, int r) {
  assert(l <= r);
  assert(1 <= l && r <= K);
  return (hw[r] - (long long)hw[l - 1] * base[r - l + 1] % HASH + HASH) % HASH;
}
inline int hasha(int l, int r, int j) {
  assert(l <= r);
  assert(1 <= l && r <= N);
  return (ha[r][j] - (long long)ha[l - 1][j] * base[r - l + 1] % HASH + HASH) %
         HASH;
}
inline int hashr(int l, int r, int j) {
  assert(l <= r);
  assert(1 <= l && r <= N);
  return (ha0[l][j] - (long long)ha0[r + 1][j] * base[r - l + 1] % HASH +
          HASH) %
         HASH;
}
void input() {
  static char inp[MAXN];
  scanf("%s", inp);
  N = strlen(inp);
  for (int i = 1; i <= N; ++i) {
    A[i][0] = inp[i - 1] - 'a' + 1;
  }
  scanf("%s", inp);
  for (int i = 1; i <= N; ++i) {
    A[i][1] = inp[i - 1] - 'a' + 1;
  }
  scanf("%s", inp);
  K = strlen(inp);
  for (int i = 1; i <= K; ++i) {
    W[i] = inp[i - 1] - 'a' + 1;
  }
}
void solve() {
  base[0] = 1;
  for (int i = 1; i <= K || i <= N; ++i) {
    base[i] = (long long)base[i - 1] * BASE % HASH;
  }
  for (int i = 1; i <= K; ++i) {
    hw[i] = ((long long)hw[i - 1] * BASE + W[i]) % HASH;
  }
  for (int i = 1; i <= N; ++i) {
    ha[i][0] = ((long long)ha[i - 1][0] * BASE + A[i][0]) % HASH;
    ha[i][1] = ((long long)ha[i - 1][1] * BASE + A[i][1]) % HASH;
  }
  for (int i = N; i >= 1; --i) {
    ha0[i][0] = ((long long)ha0[i + 1][0] * BASE + A[i][0]) % HASH;
    ha0[i][1] = ((long long)ha0[i + 1][1] * BASE + A[i][1]) % HASH;
  }
  static int left[MAXN][2][MAXN], right[MAXN][2][MAXN];
  left[0][0][0] = left[0][1][0] = 1;
  for (int i = 1; i <= N; ++i) {
    for (int j = 0; j < 2; ++j) {
      left[i][j][0] = 1;
      for (int k = 1; k <= K && k <= (i << 1); ++k) {
        if (A[i][j] == W[K - k + 1]) {
          int &cur = left[i][j][k];
          update(cur, left[i - 1][j][k - 1]);
          if (k > 1 && A[i][j ^ 1] == W[K - k + 2])
            update(cur, left[i - 1][j ^ 1][k - 2]);
          if (k > 2 && (k & 1) == 0) {
            int l = i - (k >> 1) + 1;
            if (hashr(l, i, j) == hashw(K - k + 1, K - (k >> 1)) &&
                hasha(l, i, j ^ 1) == hashw(K - (k >> 1) + 1, K))
              update(cur, 1);
          }
        }
      }
    }
  }
  right[N + 1][0][0] = right[N + 1][1][0] = 1;
  for (int i = N; i >= 1; --i) {
    for (int j = 0; j < 2; ++j) {
      right[i][j][0] = 1;
      for (int k = 1; k <= K && k <= ((N - i + 1) << 1); ++k) {
        if (A[i][j] == W[K - k + 1]) {
          int &cur = right[i][j][k];
          update(cur, right[i + 1][j][k - 1]);
          if (k > 1 && A[i][j ^ 1] == W[K - k + 2])
            update(cur, right[i + 1][j ^ 1][k - 2]);
          if (k > 2 && (k & 1) == 0) {
            int r = i + (k >> 1) - 1;
            if (hasha(i, r, j) == hashw(K - k + 1, K - (k >> 1)) &&
                hashr(i, r, j ^ 1) == hashw(K - (k >> 1) + 1, K))
              update(cur, 1);
          }
        }
      }
    }
  }
  int ans = 0;
  for (int i = 1; i <= N; ++i) {
    for (int j = 0; j < 2; ++j) {
      for (int l = 1; l < i; ++l) {
        int len = i - l + 1;
        if (len <= K && hashr(l, i, j) == hashw(1, len)) {
          if (len == K) {
            update(ans, 1);
          } else if (A[l][j ^ 1] == W[len + 1]) {
            update(ans, left[l - 1][j ^ 1][K - len - 1]);
            if (K - len - 1 > 0) {
              int k = std::min(K - len, len);
              if (hasha(l, l + k - 1, j ^ 1) == hashw(len + 1, len + k))
                update(ans, l + k - 1 == i ? right[i + 1][j ^ 1][K - (len << 1)]
                                           : 1);
            }
          }
        }
      }
      for (int r = i; r <= N; ++r) {
        int len = r - i + 1;
        if (len <= K && hasha(i, r, j) == hashw(1, len)) {
          if (len == K) {
            update(ans, 1);
          } else if (A[r][j ^ 1] == W[len + 1]) {
            update(ans, right[r + 1][j ^ 1][K - len - 1]);
            if (K - len - 1 > 0) {
              int k = std::min(K - len, len);
              if (hashr(r - k + 1, r, j ^ 1) == hashw(len + 1, len + k))
                update(ans,
                       r - k + 1 == i ? left[i - 1][j ^ 1][K - (len << 1)] : 1);
            }
          }
        }
      }
    }
  }
  printf("%d\n", ans);
}
int main() {
  input();
  solve();
  return 0;
}