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 = 1e9 + 7;
inline int read(int x = 0, char ch = getchar()) {
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
  return x;
}
char s[3005], a[4][3005];
long long f[2005][2005][3][2], ans;
int len;
unsigned long long ha[4][3005], fz[4][3005], S[3005], mi[3005];
bool v[5][3005];
inline unsigned long long get(unsigned long long *x, int l, int r) {
  return x[r] - x[l - 1] * mi[r - l + 1];
}
inline unsigned long long get2(unsigned long long *x, int l, int r) {
  return x[r] - x[l + 1] * mi[l - r + 1];
}
int main() {
  scanf("%s%s%s", a[1] + 1, a[2] + 1, s + 1);
  int n = strlen(a[1] + 1);
  len = strlen(s + 1);
  if (len == 1) {
    for (int i = 1; i <= 2; ++i)
      for (int j = 1; j <= n; ++j) ans += a[i][j] == s[1];
    cout << ans << endl;
    return 0;
  }
  for (int i = 1; i <= len; ++i) S[i] = S[i - 1] * 13331 + s[i];
  for (int i = 1; i <= 2; ++i)
    for (int j = 1; j <= n; ++j) ha[i][j] = ha[i][j - 1] * 13331 + a[i][j];
  for (int i = 1; i <= 2; ++i)
    for (int j = n; j; --j) fz[i][j] = fz[i][j + 1] * 13331 + a[i][j];
  for (int i = mi[0] = 1; i <= n; ++i) mi[i] = mi[i - 1] * 13331;
  for (int k = 1; k <= 2; ++k) {
    for (int i = 1; i <= n; ++i) {
      for (int j = 2; j < len && i - j + 1 > 0; ++j) {
        int p = min(i + 1, i - j + 1 + len - j), l = min(j + j, len);
        if (get2(fz[k], i, i - j + 1) == get(S, 1, j) &&
            get(ha[3 - k], i - j + 1, p - 1) == get(S, j + 1, l)) {
          if (j + j == len)
            ans++;
          else if (l == len)
            ;
          else if (s[l + 1] == a[3 - k][p])
            f[l + 1][p][3 - k][1]++;
        }
      }
    }
  }
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= 2; ++j) f[1][i][j][1] += (a[j][i] == s[1]);
  for (int i = 2; i <= len; ++i) {
    for (int j = 1; j <= n; ++j) {
      for (int k = 1; k <= 2; ++k) {
        if (a[k][j] == s[i])
          f[i][j][k][1] =
              (f[i][j][k][1] + f[i - 1][j - 1][k][1] + f[i - 1][j - 1][k][0]) %
              mod;
        if (a[k][j] == s[i])
          f[i][j][k][0] = (f[i][j][k][0] + f[i - 1][j][3 - k][1]) % mod;
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int k = 1; k <= 2; ++k) {
      for (int j = 2; j <= (len >> 1); ++j) {
        int p = i + j - 1, l = len - j - j;
        if (get(ha[k], i, p) == get(S, l + 1, l + j) &&
            get2(fz[3 - k], p, i) == get(S, l + j + 1, len)) {
          if (l) ans = (ans + f[l + 1][i][k][1]) % mod;
        }
      }
    }
  }
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= 2; ++j)
      ans = (ans + f[len][i][j][0] + f[len][i][j][1]) % mod;
  reverse(a[1] + 1, a[1] + n + 1);
  reverse(a[2] + 1, a[2] + n + 1);
  memset(f, 0, sizeof(f));
  for (int i = 1; i <= len; ++i) S[i] = S[i - 1] * 13331 + s[i];
  for (int i = 1; i <= 2; ++i)
    for (int j = 1; j <= n; ++j) ha[i][j] = ha[i][j - 1] * 13331 + a[i][j];
  for (int i = 1; i <= 2; ++i)
    for (int j = n; j; --j) fz[i][j] = fz[i][j + 1] * 13331 + a[i][j];
  for (int i = mi[0] = 1; i <= n; ++i) mi[i] = mi[i - 1] * 13331;
  for (int k = 1; k <= 2; ++k) {
    for (int i = 1; i <= n; ++i) {
      for (int j = 2; j < len && i - j + 1 > 0; ++j) {
        int p = min(i + 1, i - j + 1 + len - j), l = min(j + j, len);
        if (get2(fz[k], i, i - j + 1) == get(S, 1, j) &&
            get(ha[3 - k], i - j + 1, p - 1) == get(S, j + 1, l)) {
          if (j + j == len)
            ans++;
          else if (l == len)
            ;
          else if (s[l + 1] == a[3 - k][p])
            f[l + 1][p][3 - k][1]++;
        }
      }
    }
  }
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= 2; ++j) f[1][i][j][1] += (a[j][i] == s[1]);
  for (int i = 2; i <= len; ++i) {
    for (int j = 1; j <= n; ++j) {
      for (int k = 1; k <= 2; ++k) {
        if (a[k][j] == s[i])
          f[i][j][k][1] =
              (f[i][j][k][1] + f[i - 1][j - 1][k][1] + f[i - 1][j - 1][k][0]) %
              mod;
        if (a[k][j] == s[i])
          f[i][j][k][0] = (f[i][j][k][0] + f[i - 1][j][3 - k][1]) % mod;
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int k = 1; k <= 2; ++k) {
      for (int j = 2; j <= (len >> 1); ++j) {
        int p = i + j - 1, l = len - j - j;
        if (get(ha[k], i, p) == get(S, l + 1, l + j) &&
            get2(fz[3 - k], p, i) == get(S, l + j + 1, len)) {
          if (l) ans = (ans + f[l + 1][i][k][1]) % mod;
        }
      }
    }
  }
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= 2; ++j)
      ans = (ans + f[len][i][j][0] + f[len][i][j][1]) % mod;
  if (len == 2) {
    for (int i = 1; i <= n; ++i) {
      if (a[1][i] == s[1] && a[2][i] == s[2]) ans--;
      if (a[1][i] == s[2] && a[2][i] == s[1]) ans--;
    }
  }
  cout << (ans + mod) % mod << endl;
  return 0;
}