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;
int f[2010][2][2010], n, m, p[2][2010], q[2][2010], pw[2010], w[2010], ans;
char s[2][2010], t[2010];
void MAKE() {
  memset(f, 0, sizeof f);
  for (int i = 1; i <= m; ++i)
    w[i] = (w[i - 1] + 1ll * (t[i] - 96) * pw[i]) % 1000000009;
  for (int i = 0; i <= n; ++i)
    for (int j = 0; j <= i && j + j <= m; ++j)
      if (j ^ 1) {
        if (1ll * (q[1][i - j + 1] - q[1][i + 1] + 1000000009) * pw[1] %
                1000000009 ==
            1ll * w[j] * pw[n - i] % 1000000009)
          if (1ll * (p[0][i] - p[0][i - j] + 1000000009) * pw[j + 1] %
                  1000000009 ==
              1ll * (w[j + j] - w[j] + 1000000009) * pw[i - j + 1] % 1000000009)
            ++f[j + j][0][i];
        if (1ll * (q[0][i - j + 1] - q[0][i + 1] + 1000000009) * pw[1] %
                1000000009 ==
            1ll * w[j] * pw[n - i] % 1000000009)
          if (1ll * (p[1][i] - p[1][i - j] + 1000000009) * pw[j + 1] %
                  1000000009 ==
              1ll * (w[j + j] - w[j] + 1000000009) * pw[i - j + 1] % 1000000009)
            ++f[j + j][1][i];
      }
  for (int T = 0; T < m; ++T)
    for (int S = 0; S < 2; ++S)
      for (int i = 0; i < n; ++i)
        if (f[T][S][i] && s[S][i + 1] == t[T + 1]) {
          f[T + 1][S][i + 1] = (f[T + 1][S][i + 1] + f[T][S][i]) % 1000000007;
          if (T + 1 < m && s[S ^ 1][i + 1] == t[T + 2])
            f[T + 2][S ^ 1][i + 1] =
                (f[T + 2][S ^ 1][i + 1] + f[T][S][i]) % 1000000007;
        }
  for (int i = 0; i <= n; ++i)
    for (int j = 0; j + i <= n && j + j <= m; ++j)
      if (j ^ 1) {
        if (1ll * (p[0][i + j] - p[0][i] + 1000000009) * pw[m - j - j + 1] %
                1000000009 ==
            1ll * (w[m - j] - w[m - j - j] + 1000000009) * pw[i + 1] %
                1000000009)
          if (1ll * (q[1][i + 1] - q[1][i + j + 1] + 1000000009) *
                  pw[m - j + 1] % 1000000009 ==
              1ll * (w[m] - w[m - j] + 1000000009) * pw[n - i - j] % 1000000009)
            ans = (ans + f[m - j - j][0][i]) % 1000000007;
        if (1ll * (p[1][i + j] - p[1][i] + 1000000009) * pw[m - j - j + 1] %
                1000000009 ==
            1ll * (w[m - j] - w[m - j - j] + 1000000009) * pw[i + 1] %
                1000000009)
          if (1ll * (q[0][i + 1] - q[0][i + j + 1] + 1000000009) *
                  pw[m - j + 1] % 1000000009 ==
              1ll * (w[m] - w[m - j] + 1000000009) * pw[n - i - j] % 1000000009)
            ans = (ans + f[m - j - j][1][i]) % 1000000007;
      }
}
int main() {
  pw[0] = 1;
  for (int i = 1; i < 2010; ++i) pw[i] = 37ll * pw[i - 1] % 1000000009;
  scanf("%s\n", s[0] + 1);
  scanf("%s\n", s[1] + 1);
  n = strlen(s[0] + 1);
  scanf("\n");
  scanf("%s", t + 1);
  m = strlen(t + 1);
  for (int i = 1; i <= n; ++i) {
    p[0][i] = (p[0][i - 1] + 1ll * (s[0][i] - 96) * pw[i]) % 1000000009;
    p[1][i] = (p[1][i - 1] + 1ll * (s[1][i] - 96) * pw[i]) % 1000000009;
  }
  for (int i = n; i; --i) {
    q[0][i] = (q[0][i + 1] + 1ll * (s[0][i] - 96) * pw[n - i]) % 1000000009;
    q[1][i] = (q[1][i + 1] + 1ll * (s[1][i] - 96) * pw[n - i]) % 1000000009;
  }
  MAKE();
  for (int i = 1; i <= m >> 1; ++i) swap(t[i], t[m + 1 - i]);
  MAKE();
  if (m == 1)
    for (int i = 1; i <= n; ++i) {
      if (s[0][i] == t[1]) --ans;
      if (s[1][i] == t[1]) --ans;
    }
  if (m % 2 == 0) {
    for (int i = 0; i <= n; ++i) {
      int j = m / 2;
      if (j > i) continue;
      if (1ll * (q[1][i - j + 1] - q[1][i + 1] + 1000000009) * pw[1] %
              1000000009 ==
          1ll * w[j] * pw[n - i] % 1000000009)
        if (1ll * (p[0][i] - p[0][i - j] + 1000000009) * pw[j + 1] %
                1000000009 ==
            1ll * (w[j + j] - w[j] + 1000000009) * pw[i - j + 1] % 1000000009)
          --ans;
      if (1ll * (q[0][i - j + 1] - q[0][i + 1] + 1000000009) * pw[1] %
              1000000009 ==
          1ll * w[j] * pw[n - i] % 1000000009)
        if (1ll * (p[1][i] - p[1][i - j] + 1000000009) * pw[j + 1] %
                1000000009 ==
            1ll * (w[j + j] - w[j] + 1000000009) * pw[i - j + 1] % 1000000009)
          --ans;
    }
    if (m > 2)
      for (int i = 0; i <= n; ++i) {
        int j = m / 2;
        if (i + j > n) continue;
        if (1ll * (p[0][i + j] - p[0][i] + 1000000009) * pw[m - j - j + 1] %
                1000000009 ==
            1ll * (w[m - j] - w[m - j - j] + 1000000009) * pw[i + 1] %
                1000000009)
          if (1ll * (q[1][i + 1] - q[1][i + j + 1] + 1000000009) *
                  pw[m - j + 1] % 1000000009 ==
              1ll * (w[m] - w[m - j] + 1000000009) * pw[n - i - j] % 1000000009)
            --ans;
        if (1ll * (p[1][i + j] - p[1][i] + 1000000009) * pw[m - j - j + 1] %
                1000000009 ==
            1ll * (w[m - j] - w[m - j - j] + 1000000009) * pw[i + 1] %
                1000000009)
          if (1ll * (q[0][i + 1] - q[0][i + j + 1] + 1000000009) *
                  pw[m - j + 1] % 1000000009 ==
              1ll * (w[m] - w[m - j] + 1000000009) * pw[n - i - j] % 1000000009)
            --ans;
      }
  }
  ans = (ans + 1000000007) % 1000000007;
  printf("%d", ans);
}