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>
char s[2][2010], p[2010];
int f[2][2010][2010], ans, n, k;
int HL[2][2010], HR[2][2010], _pow[2010], H[2010];
int hashL(int hash[], int l, int r) {
  return ((hash[r] - (long long)hash[l - 1] * _pow[r - l + 1] % 1000000007) +
          1000000007) %
         1000000007;
}
int hashR(int hash[], int l, int r) {
  return ((hash[l] - (long long)hash[r + 1] * _pow[r - l + 1] % 1000000007) +
          1000000007) %
         1000000007;
}
void solve() {
  memset(HL, 0, sizeof(HL));
  memset(HR, 0, sizeof(HR));
  memset(H, 0, sizeof(H));
  for (int d = 0; d <= 1; d++) {
    for (int i = 1; i <= n; i++)
      HL[d][i] = ((long long)HL[d][i - 1] * 29 + s[d][i] - 96) % 1000000007;
    for (int i = n; i >= 1; i--)
      HR[d][i] = ((long long)HR[d][i + 1] * 29 + s[d][i] - 96) % 1000000007;
  }
  for (int i = 1; i <= k; i++)
    H[i] = ((long long)H[i - 1] * 29 + p[i] - 96) % 1000000007;
  memset(f, 0, sizeof(f));
  f[0][0][0] = f[1][0][0] = 1;
  if ((!(k & 1)) && (k ^ 2)) {
    for (int d = 0; d <= 1; d++) {
      int h = k >> 1;
      if (hashR(HR[d], 1, h) == hashL(H, h + 1, k) &&
          hashL(HL[!d], 1, h) == hashL(H, 1, h))
        ans++;
    }
  }
  for (int i = 1; i <= n; i++) {
    f[0][i][0] = f[1][i][0] = 1;
    for (int d = 0; d <= 1; d++) {
      for (int j = 2; i - j + 1 > 0; j++) {
        if (hashR(HR[d], i - j + 1, i) == hashL(H, 1, j) &&
            hashL(HL[!d], i - j + 1, i) == hashL(H, j + 1, j << 1))
          f[!d][i][j << 1] = (f[!d][i][j << 1] + 1) % 1000000007;
      }
      for (int j = 1; j <= k; j++) {
        if (s[d][i] != p[j]) continue;
        f[d][i][j] = (f[d][i][j] + f[d][i - 1][j - 1]) % 1000000007;
        if (j < k && s[!d][i] == p[j + 1])
          f[!d][i][j + 1] = (f[!d][i][j + 1] + f[d][i - 1][j - 1]) % 1000000007;
      }
    }
    ans = (ans + f[0][i][k]) % 1000000007;
    ans = (ans + f[1][i][k]) % 1000000007;
    for (int d = 0; d <= 1; d++) {
      for (int b = 2; (b << 1) <= k && i + b <= n; b++) {
        if (hashR(HR[d], i + 1, i + b) == hashL(H, k - b + 1, k) &&
            hashL(HL[!d], i + 1, i + b) == hashL(H, k - (b << 1) + 1, k - b))
          ans = (ans + f[!d][i][k - (b << 1)]) % 1000000007;
      }
    }
  }
}
int main() {
  _pow[0] = 1;
  for (int i = 1; i < 2010; i++)
    _pow[i] = (long long)_pow[i - 1] * 29 % 1000000007;
  scanf("%s%s%s", s[0] + 1, s[1] + 1, p + 1);
  n = strlen(s[0] + 1);
  k = strlen(p + 1);
  if (k == 1) {
    int shabi = 0;
    for (int i = 0; i <= 1; i++)
      for (int j = 1; j <= n; j++)
        if (s[i][j] == p[1]) shabi++;
    printf("%d\n", shabi);
    return 0;
  }
  solve();
  std::reverse(s[0] + 1, s[0] + n + 1);
  std::reverse(s[1] + 1, s[1] + n + 1);
  solve();
  std::reverse(s[0] + 1, s[0] + n + 1);
  std::reverse(s[1] + 1, s[1] + n + 1);
  memset(HL, 0, sizeof(HL));
  memset(HR, 0, sizeof(HR));
  memset(H, 0, sizeof(H));
  for (int d = 0; d <= 1; d++) {
    for (int i = 1; i <= n; i++)
      HL[d][i] = ((long long)HL[d][i - 1] * 29 + s[d][i] - 96) % 1000000007;
    for (int i = n; i >= 1; i--)
      HR[d][i] = ((long long)HR[d][i + 1] * 29 + s[d][i] - 96) % 1000000007;
  }
  for (int i = 1; i <= k; i++)
    H[i] = ((long long)H[i - 1] * 29 + p[i] - 96) % 1000000007;
  int cnt = 0;
  if (!(k & 1)) {
    for (int i = 1; i <= n; i++)
      for (int j = 0; j <= 1; j++) {
        if (i - (k >> 1) + 1 > 0 &&
            hashR(HR[j], i - (k >> 1) + 1, i) == hashL(H, 1, k >> 1) &&
            hashL(HL[!j], i - (k >> 1) + 1, i) == hashL(H, (k >> 1) + 1, k))
          cnt++;
        if (k ^ 2 && hashL(HL[j], i, i + (k >> 1) - 1) == hashL(H, 1, k >> 1) &&
            hashR(HR[!j], i, i + (k >> 1) - 1) == hashL(H, (k >> 1) + 1, k))
          cnt++;
      }
  }
  printf("%d\n", (ans - cnt + 1000000007) % 1000000007);
  return 0;
}