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 L = 2005;
const long long mod = 1000000007ll;
int n, m, lcp1[L][L][2], lcp2[L][L][2];
char str[2][L], s[L];
long long ans = 0ll;
void init() {
  for (int i = n - 1; i >= 0; i--) {
    for (int j = m - 1; j >= 0; j--) {
      if (str[0][i] != s[j])
        lcp1[i][j][0] = 0;
      else if (i < n - 1 && j < m - 1)
        lcp1[i][j][0] = lcp1[i + 1][j + 1][0] + 1;
      else
        lcp1[i][j][0] = 1;
      if (str[1][i] != s[j])
        lcp1[i][j][1] = 0;
      else if (i < n - 1 && j < m - 1)
        lcp1[i][j][1] = lcp1[i + 1][j + 1][1] + 1;
      else
        lcp1[i][j][1] = 1;
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = m - 1; j >= 0; j--) {
      if (str[0][i] != s[j])
        lcp2[i][j][0] = 0;
      else if (i && j < m - 1)
        lcp2[i][j][0] = lcp2[i - 1][j + 1][0] + 1;
      else
        lcp2[i][j][0] = 1;
      if (str[1][i] != s[j])
        lcp2[i][j][1] = 0;
      else if (i && j < m - 1)
        lcp2[i][j][1] = lcp2[i - 1][j + 1][1] + 1;
      else
        lcp2[i][j][1] = 1;
    }
  }
}
long long f[L][L][2];
void solve() {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      f[i][j][0] = f[i][j][1] = 0ll;
      if (i && j == 1 && str[0][i] == s[j] && str[0][i - 1] == s[j - 1])
        f[i][j][0] = (f[i][j][0] + 1ll) % mod;
      if (i && j == 1 && str[1][i] == s[j] && str[1][i - 1] == s[j - 1])
        f[i][j][1] = (f[i][j][1] + 1ll) % mod;
      if (j >= 2 && j % 2 == 0 && i) {
        if (str[1][i] == s[j] && lcp2[i - 1][0][0] >= (j >> 1) &&
            lcp1[i - (j >> 1)][j >> 1][1] >= (j >> 1))
          f[i][j][1] = (f[i][j][1] + 1ll) % mod;
        if (str[0][i] == s[j] && lcp2[i - 1][0][1] >= (j >> 1) &&
            lcp1[i - (j >> 1)][j >> 1][0] >= (j >> 1))
          f[i][j][0] = (f[i][j][0] + 1ll) % mod;
      }
      if (i && j) {
        if (str[0][i] == s[j])
          f[i][j][0] = (f[i][j][0] + f[i - 1][j - 1][0]) % mod;
        if (str[1][i] == s[j])
          f[i][j][1] = (f[i][j][1] + f[i - 1][j - 1][1]) % mod;
      }
      if (i && j >= 2) {
        if (str[0][i - 1] == s[j - 1] && str[0][i] == s[j])
          f[i][j][0] = (f[i][j][0] + f[i - 1][j - 2][1]) % mod;
        if (str[1][i - 1] == s[j - 1] && str[1][i] == s[j])
          f[i][j][1] = (f[i][j][1] + f[i - 1][j - 2][0]) % mod;
      }
      if (j == m - 1) ans = (ans + f[i][j][0] + f[i][j][1]) % mod;
      if ((m - j) % 2 == 0) {
        if (lcp1[i][j][0] >= (m - j >> 1) &&
            lcp2[i + (m - j >> 1) - 1][m + j >> 1][1] >= (m - j >> 1))
          ans = (ans + f[i][j][0]) % mod;
        if (lcp1[i][j][1] >= (m - j >> 1) &&
            lcp2[i + (m - j >> 1) - 1][m + j >> 1][0] >= (m - j >> 1))
          ans = (ans + f[i][j][1]) % mod;
      }
    }
  }
}
int main() {
  scanf("%s%s%s", str[0], str[1], s);
  n = strlen(str[0]), m = strlen(s);
  init();
  for (int i = 0; i <= n - (m >> 1); i++) {
    if (m % 2 == 0 && lcp1[i][0][0] >= (m >> 1) &&
        lcp2[i + (m >> 1) - 1][m >> 1][1] >= (m >> 1))
      ans = (ans + 1ll) % mod;
    if (m % 2 == 0 && lcp1[i][0][1] >= (m >> 1) &&
        lcp2[i + (m >> 1) - 1][m >> 1][0] >= (m >> 1))
      ans = (ans + 1ll) % mod;
  }
  for (int i = (m >> 1) - 1; i < n; i++) {
    if (m > 2 && m % 2 == 0 && lcp2[i][0][0] >= (m >> 1) &&
        lcp1[i - (m >> 1) + 1][m >> 1][1] >= (m >> 1))
      ans = (ans + 1ll) % mod;
    if (m > 2 && m % 2 == 0 && lcp2[i][0][1] >= (m >> 1) &&
        lcp1[i - (m >> 1) + 1][m >> 1][0] >= (m >> 1))
      ans = (ans + 1ll) % mod;
  }
  for (int i = 0; i < n; i++) {
    if (m == 1 && str[0][i] == s[0]) ans = (ans + 1ll) % mod;
    if (m == 1 && str[1][i] == s[0]) ans = (ans + 1ll) % mod;
  }
  solve();
  reverse(s, s + m);
  init(), solve();
  printf("%lld\n", ans);
  return 0;
}