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;
char x[2][2005], y[2005];
int n, m;
long long ans, M1 = 1000000007 - 7 + 9, M2 = 1000000007 - 7 + 21,
               dp[2005][2005][2];
pair<long long, long long> tim[2005], wq[2005], ta, tb;
void go(bool fst) {
  for (int a = 0; a <= n; a++) {
    for (int b = 0; b < 2; b++) dp[a][0][b] = 1;
    if (a) {
      for (int b = 0; b <= m - 2; b++)
        for (int c = 0; c < 2; c++)
          if (x[c][a - 1] == y[b] && x[c ^ 1][a - 1] == y[b + 1])
            dp[a][b + 2][c ^ 1] =
                (dp[a][b + 2][c ^ 1] + dp[a - 1][b][c]) % 1000000007;
      for (int b = 0; b <= m - 1; b++)
        for (int c = 0; c < 2; c++)
          if (x[c][a - 1] == y[b])
            dp[a][b + 1][c] = (dp[a][b + 1][c] + dp[a - 1][b][c]) % 1000000007;
      for (int c = 0; c < 2; c++) {
        ta = tb = make_pair(0LL, 0LL);
        for (int b = 1; b * 2 <= m && a - b >= 0; b++) {
          ta = make_pair((ta.first * 26 + x[c][a - b]) % M1,
                         (ta.second * 26 + x[c][a - b]) % M2);
          tb =
              make_pair((tb.first + x[c ^ 1][a - b] * tim[b - 1].first) % M1,
                        (tb.second + x[c ^ 1][a - b] * tim[b - 1].second) % M2);
          if (fst || b * 2 != m)
            if (b > 1)
              if (make_pair((ta.first * tim[b].first + tb.first) % M1,
                            (ta.second * tim[b].second + tb.second) % M2) ==
                  wq[b * 2])
                dp[a][b * 2][c ^ 1] = (dp[a][b * 2][c ^ 1] + 1) % 1000000007;
        }
      }
    }
    for (int c = 0; c < 2; c++) {
      ta = tb = make_pair(0LL, 0LL);
      for (int b = 1; b * 2 <= m && a - 1 + b < n; b++) {
        ta = make_pair((ta.first * 26 + x[c][a - 1 + b]) % M1,
                       (ta.second * 26 + x[c][a - 1 + b]) % M2);
        tb = make_pair(
            (tb.first + x[c ^ 1][a - 1 + b] * tim[b - 1].first) % M1,
            (tb.second + x[c ^ 1][a - 1 + b] * tim[b - 1].second) % M2);
        if (b > 1)
          if (make_pair((ta.first * tim[b].first + tb.first) % M1,
                        (ta.second * tim[b].second + tb.second) % M2) ==
                  make_pair(
                      (wq[m].first -
                       wq[m - b * 2].first * tim[b * 2].first % M1 + M1) %
                          M1,
                      (wq[m].second -
                       wq[m - b * 2].second * tim[b * 2].second % M2 + M2) %
                          M2) &&
              (fst || b * 2 != m))
            ans = (ans + dp[a][m - b * 2][c]) % 1000000007;
      }
    }
    ans = (ans + dp[a][m][0] + dp[a][m][1]) % 1000000007;
  }
}
int main() {
  scanf("%s%s%s", x[0], x[1], y);
  while (x[0][n]) n++;
  while (y[m]) m++;
  for (int a = 0; a < 2; a++)
    for (int b = 0; b < n; b++) x[a][b] -= 'a';
  for (int a = 0; a < m; a++) y[a] -= 'a';
  if (m == 1) {
    for (int a = 0; a < 2; a++)
      for (int b = 0; b < n; b++)
        if (x[a][b] == y[0]) ans++;
  } else if (m == 2) {
    for (int a = 0; a < 2; a++)
      for (int b = 1; b < n; b++)
        if (x[a][b] == y[0] && x[a][b - 1] == y[1]) ans++;
    for (int a = 0; a < 2; a++)
      for (int b = 1; b < n; b++)
        if (x[a][b] == y[1] && x[a][b - 1] == y[0]) ans++;
    for (int a = 0; a < n; a++)
      if (x[0][a] == y[0] && x[1][a] == y[1]) ans++;
    for (int a = 0; a < n; a++)
      if (x[0][a] == y[1] && x[1][a] == y[0]) ans++;
  } else {
    tim[0] = make_pair(1LL, 1LL);
    for (int a = 1; a <= m; a++)
      tim[a] =
          make_pair(tim[a - 1].first * 26 % M1, tim[a - 1].second * 26 % M2);
    wq[0] = make_pair(0LL, 0LL);
    for (int a = 0; a < m; a++)
      wq[a + 1] = make_pair((wq[a].first * 26 + y[a]) % M1,
                            (wq[a].second * 26 + y[a]) % M2);
    go(1);
    reverse(y, y + m);
    for (int a = 0; a < m; a++)
      wq[a + 1] = make_pair((wq[a].first * 26 + y[a]) % M1,
                            (wq[a].second * 26 + y[a]) % M2);
    memset(dp, 0, sizeof(dp));
    go(0);
  }
  printf("%I64d\n", ans);
  return 0;
}