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;
long long mod = 1000000007;
long long dp[2][2][2001][2001];
int sm[2][2][2001][2001];
long long cs[2001];
int main() {
  string bd[2][2], t;
  int n, k;
  cin >> bd[0][0] >> bd[0][1] >> t;
  n = bd[0][0].size();
  k = t.size();
  for (int c = 0; c < 2; c++) {
    bd[1][c] = bd[0][c];
    reverse(bd[1][c].begin(), bd[1][c].end());
  }
  long long res = 0;
  for (int c = 0; c < 4; c++)
    for (int i = n - 1; i >= 0; i--)
      for (int j = k - 1; j >= 0; j--) {
        sm[0][c][i][j] = bd[0][c][i] == t[j] ? sm[0][c][i + 1][j + 1] + 1 : 0;
        if (sm[0][c][i][j] == k && (k > 1 || c < 2)) res++;
      }
  for (int d = 0; d < 2; d++)
    for (int r = 0; r < 2; r++)
      for (int i = 0; i < n; i++)
        for (int j = 0; i + j < n && j + 1 < k; j++)
          if (j < sm[d][r][i][0] && d + j != 0) {
            if (sm[d][!r][i + j][j + 1]) dp[d][!r][i + j + 1][j + 2]++;
            if (j < sm[!d][!r][n - 1 - i - j][j + 1])
              dp[!d][!r][n - i][2 * j + 2]++;
            if (j + 1 + min(j + 1, sm[!d][!r][n - 1 - i - j][j + 1]) == k)
              res++;
          }
  for (int off = -2000; off <= 2000; off++)
    for (int c = 0; c < 4; c++) {
      fill(cs, cs + 2001, 0);
      for (int i = max(0, -off); i < n && i + off < k; i++)
        cs[i + 1] = (cs[i] + dp[0][c][i][i + off]) % mod;
      for (int i = max(0, -off); i < n && i + off < k; i++) {
        int j = i + off;
        for (int d = 0; d < sm[0][c][i][j]; d++) {
          if (sm[0][c ^ 1][i + d][j + d + 1]) {
            long long tem = (cs[i + d + 1] - cs[i]) % mod;
            dp[0][c ^ 1][i + d + 1][j + d + 2] += tem;
          }
          if (k - j <= 2 * (d + 1) &&
              j + d + 1 + sm[0][c ^ 3][n - 1 - i - d][j + d + 1] == k) {
            res =
                (res + cs[min(i + 2 * d + 3 + j - k, i + d + 1)] - cs[i]) % mod;
          }
        }
        i += sm[0][c][i][j];
      }
    }
  if (res < 0) res += mod;
  cout << res << endl;
  return 0;
}