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 unsigned long long B = 503;
const int mod = 1e9 + 7;
unsigned long long h[3][2005][2005], p[2005];
int L[2][2005][2005], R[2][2005][2005];
char s[3][2005];
int main() {
  p[0] = 1;
  for (int i = 1; i < 2005; i++) p[i] = p[i - 1] * B;
  for (int i = 0; i < 3; i++) scanf("%s", s[i] + 1);
  int n = strlen(s[0] + 1), k = strlen(s[2] + 1);
  for (int i = 0; i < 3; i++) {
    int nn = (i == 2 ? k : n);
    for (int x = 1; x <= nn; x++) {
      h[i][x][x] = s[i][x];
      for (int y = x + 1; y <= nn; y++)
        h[i][x][y] = h[i][x][y - 1] * B + s[i][y];
      for (int y = x - 1; y; y--) h[i][x][y] = h[i][x][y + 1] * B + s[i][y];
    }
  }
  for (int i = 1; i <= n; i++)
    for (int j = k; j; j--)
      for (int x = 0; x < 2; x++) {
        if (s[x][i] != s[2][j]) continue;
        if (j == k) {
          L[x][i][j] = 1;
          continue;
        }
        L[x][i][j] = L[x][i - 1][j + 1];
        if (k - j & 1) {
          int len = k - j + 1 >> 1;
          if (len <= i &&
              h[x][i][i - len + 1] * p[len] + h[x ^ 1][i - len + 1][i] ==
                  h[2][j][k])
            L[x][i][j]++;
        }
        if (s[x][i] == s[2][j] && s[x ^ 1][i] == s[2][j + 1])
          L[x][i][j] += L[x ^ 1][i - 1][j + 2];
        L[x][i][j] %= mod;
      }
  for (int i = n; i; i--)
    for (int j = k; j; j--)
      for (int x = 0; x < 2; x++) {
        if (s[x][i] != s[2][j]) continue;
        if (j == k) {
          R[x][i][j] = 1;
          continue;
        }
        R[x][i][j] = R[x][i + 1][j + 1];
        if (k - j & 1) {
          int len = k - j + 1 >> 1;
          if (len <= n - i + 1 &&
              h[x][i][i + len - 1] * p[len] + h[x ^ 1][i + len - 1][i] ==
                  h[2][j][k])
            R[x][i][j]++;
        }
        if (s[x][i] == s[2][j] && s[x ^ 1][i] == s[2][j + 1])
          R[x][i][j] += R[x ^ 1][i + 1][j + 2];
        R[x][i][j] %= mod;
      }
  long long ans = 0;
  for (int x = 0; x < 2; x++)
    for (int i = 1; i <= n; i++) {
      if (s[x][i] != s[2][1]) continue;
      if (k == 1) {
        ans++;
        continue;
      }
      for (int j = i + 1; j <= n; j++) {
        int len = j - i + 1;
        if (s[x][j] != s[2][len]) break;
        if (k == len)
          ans++;
        else {
          if (s[x ^ 1][j] == s[2][len + 1]) ans += R[x ^ 1][j + 1][len + 2];
          if (k <= 2 * len &&
              (h[x][i][j] * p[k - len] + h[x ^ 1][j][j - k + len + 1] ==
               h[2][1][k]))
            ans++;
          if (k > 2 * len &&
              (h[x][i][j] * p[len] + h[x ^ 1][j][i] == h[2][1][2 * len]))
            ans += L[x ^ 1][i - 1][2 * len + 1];
        }
      }
      if (s[x ^ 1][i] == s[2][2]) {
        if (k == 2)
          ans++;
        else
          ans += L[x ^ 1][i - 1][3] + R[x ^ 1][i + 1][3];
      }
      for (int j = i - 1; j; j--) {
        int len = i - j + 1;
        if (s[x][j] != s[2][len]) break;
        if (k == len)
          ans++;
        else {
          if (s[x ^ 1][j] == s[2][len + 1]) ans += L[x ^ 1][j - 1][len + 2];
          if (k <= 2 * len &&
              (h[x][i][j] * p[k - len] + h[x ^ 1][j][j + k - len - 1] ==
               h[2][1][k]))
            ans++;
          if (k > 2 * len &&
              (h[x][i][j] * p[len] + h[x ^ 1][j][i] == h[2][1][2 * len]))
            ans += R[x ^ 1][i + 1][2 * len + 1];
        }
      }
    }
  ans %= mod;
  printf("%I64d\n", ans);
}