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 = 1000000007;
const int N = 2010;
struct pr {
  static const int mod1 = 1000000007;
  static const int mod2 = 998244353;
  int x, y;
  pr(int x = 0, int y = 0) : x(x), y(y) {}
  pr operator+(const pr& a) const {
    return pr((x + a.x) % mod1, (y + a.y) % mod2);
  }
  pr operator-(const pr& a) const {
    return pr((x - a.x + mod1) % mod1, (y - a.y + mod2) % mod2);
  }
  pr operator*(const pr& a) const {
    return pr(1ll * x * a.x % mod1, 1ll * y * a.y % mod2);
  }
  bool operator==(const pr& a) const { return x == a.x && y == a.y; }
  long long hash() { return 1ll * x * mod2 + y; }
  pr print() {
    printf("%d %d\n", x, y);
    return *this;
  }
} X[N], A[2][N], B[2][N], Y[N], X0;
pr gh(int i, int j, pr* Y) {
  if (j < i) return pr(0, 0);
  return Y[j] - Y[i - 1] * X[j - i + 1];
}
int dp1[N][2][N], dp2[N][2][N], n, m, ans;
char s[2][N], s2[N];
int main() {
  srand(time(NULL));
  scanf("%s%s%s", s[0] + 1, s[1] + 1, s2 + 1);
  n = strlen(s[0] + 1);
  m = strlen(s2 + 1);
  if (m == 1) {
    for (int i = 1; i <= n; i++) {
      if (s[0][i] == s2[1]) ans++;
      if (s[1][i] == s2[1]) ans++;
    }
    printf("%d\n", ans);
    return 0;
  }
  if (m == 2) {
    for (int i = 1; i <= n; i++) {
      if (s[0][i] == s2[1]) {
        if (s[0][i + 1] == s2[2]) ans++;
        if (s[0][i - 1] == s2[2]) ans++;
        if (s[1][i] == s2[2]) ans++;
      }
      if (s[1][i] == s2[1]) {
        if (s[1][i + 1] == s2[2]) ans++;
        if (s[1][i - 1] == s2[2]) ans++;
        if (s[0][i] == s2[2]) ans++;
      }
    }
    printf("%d\n", ans);
    return 0;
  }
  X0 = pr(rand() % 233333 * 2 + 1, rand() % 2333 * 2 + 1);
  X[0] = pr(1, 1);
  for (int i = 1; i <= max(n, m); i++) X[i] = X[i - 1] * X0;
  for (int i = 1; i <= m; i++) Y[i] = Y[i - 1] * X0 + pr(s2[i], s2[i]);
  for (int i = 1; i <= n; i++) {
    A[0][i] = A[0][i - 1] * X0 + pr(s[0][i], s[0][i]);
    A[1][i] = A[1][i - 1] * X0 + pr(s[1][i], s[1][i]);
  }
  for (int i = 1; i <= n; i++) {
    B[0][i] = B[0][i - 1] * X0 + pr(s[0][n - i + 1], s[0][n - i + 1]);
    B[1][i] = B[1][i - 1] * X0 + pr(s[1][n - i + 1], s[1][n - i + 1]);
  }
  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= 1; j++)
      for (int k = 0; k <= i && 2 * k <= m; k++)
        if (k != 1 && gh(1, k, Y) == gh(n - i + 1, n - i + k, B[!j]) &&
            gh(k + 1, 2 * k, Y) == gh(i - k + 1, i, A[j]))
          dp1[i][j][2 * k] = 1;
  for (int j = 0; j <= 1; j++)
    for (int i = 0; i <= n; i++) dp2[i][j][0] = 1;
  for (int k = 1; k <= m; k++)
    for (int j = 0; j <= 1; j++)
      for (int i = 1; i <= n; i++)
        if (s2[k] == s[j][i]) {
          dp2[i][j][k] = (((k > 1 && s[!j][i] == s2[k - 1]
                                ? (dp2[i - 1][!j][k - 2] +
                                   (k > 2 ? dp1[i - 1][!j][k - 2] : 0)) %
                                      mod
                                : 0) +
                           dp2[i - 1][j][k - 1]) %
                              mod +
                          (k > 1 ? dp1[i - 1][j][k - 1] : 0)) %
                         mod;
        }
  for (int i = 1; i <= n + 1; i++)
    for (int j = 0; j <= 1; j++)
      for (int k = 0; k <= n - i + 1 && k * 2 <= m; k++) {
        if (k != 1 && gh(m - 2 * k + 1, m - k, Y) == gh(i, i + k - 1, A[j]) &&
            gh(m - k + 1, m, Y) == gh(n - i - k + 2, n - i + 1, B[!j])) {
          (ans += ((2 * k == m ? 0 : dp1[i - 1][j][m - 2 * k]) +
                   dp2[i - 1][j][m - 2 * k]) %
                  mod) %= mod;
        }
      }
  memset(dp1, 0, sizeof(dp1));
  for (int i = 1; i <= n + 1; i++)
    for (int j = 0; j <= 1; j++)
      for (int k = 2; k <= n - i + 1 && 2 * k < m; k++)
        if (gh(1, k, Y) == gh(i, i + k - 1, A[!j]) &&
            gh(k + 1, k * 2, Y) == gh(n - i - k + 2, n - i + 1, B[j]))
          dp1[i][j][2 * k] = 1;
  for (int j = 0; j <= 1; j++)
    for (int i = 1; i <= n + 1; i++) dp2[i][j][0] = 1;
  for (int k = 1; k <= m; k++)
    for (int j = 0; j <= 1; j++)
      for (int i = 1; i <= n; i++)
        if (s2[k] == s[j][i]) {
          dp2[i][j][k] =
              (((k > 1 && s[!j][i] == s2[k - 1]
                     ? (dp2[i + 1][!j][k - 2] + dp1[i + 1][!j][k - 2]) % mod
                     : 0) +
                dp2[i + 1][j][k - 1]) %
                   mod +
               dp1[i + 1][j][k - 1]) %
              mod;
        }
  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= 1; j++)
      for (int k = 0; k <= i && 2 * k < m; k++)
        if (k != 1 &&
            gh(m - 2 * k + 1, m - k, Y) == gh(n - i + 1, n - i + k, B[j]) &&
            gh(m - k + 1, m, Y) == gh(i - k + 1, i, A[!j]))
          (ans +=
           (dp1[i + 1][j][m - 2 * k] + dp2[i + 1][j][m - 2 * k]) % mod) %= mod;
  printf("%d\n", ans);
  return 0;
}