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 = 1e9 + 7;
const int NMAX = 2005;
int dp[2][NMAX][NMAX];
bool d[2][NMAX][NMAX];
string reverse(string S) {
  reverse(S.begin(), S.end());
  return S;
}
vector<vector<int>> getLcp(const string& S1, const string& S2) {
  int n = ((int)(S1).size()), m = ((int)(S2).size());
  vector<vector<int>> lcp(n + 1, vector<int>(m + 1, 0));
  for (int i = n - 1; i >= 0; --i) {
    for (int j = m - 1; j >= 0; --j) {
      if (S1[i] == S2[j]) {
        lcp[i][j] = lcp[i + 1][j + 1] + 1;
      }
    }
  }
  return lcp;
}
int solve(vector<string> A, string P, bool ok = true) {
  int n = ((int)(A[0]).size()), k = ((int)(P).size());
  memset(dp, 0, sizeof dp);
  memset(d, 0, sizeof d);
  int ans = 0;
  for (int u = 0; u < 2; ++u) {
    vector<vector<int>> lcp = getLcp(A[u ^ 1], P);
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
      for (int l = 1; l <= k && i - l >= 0 && A[u][i - l] == P[l - 1]; ++l) {
        int p = lcp[i - l][l];
        if (p == 0 || l == 1) continue;
        if (p > l) {
          dp[u ^ 1][i + 1][2 * l + 1]++;
        } else if (p + l == k && p == l && ok) {
          ans++;
          cnt++;
        }
        if (p >= l) {
          d[u ^ 1][i][2 * l] = true;
        }
      }
    }
    ans %= MOD;
  }
  for (int j = 0; j < 2; ++j) {
    for (int i = 0; i <= n; ++i) {
      dp[j][i][0] = 1;
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < 2; ++j) {
      for (int l = 1; l <= k; ++l) {
        if (A[j][i - 1] == P[l - 1]) {
          dp[j][i][l] = (dp[j][i][l] + dp[j][i - 1][l - 1]) % MOD;
        }
      }
    }
    for (int l = k; l > 1; --l) {
      for (int j = 0; j < 2; ++j) {
        if (k == 2 && j == 1) continue;
        if (A[j][i - 1] == P[l - 1]) {
          dp[j][i][l] = (dp[j][i][l] + dp[j ^ 1][i][l - 1]) % MOD;
        }
      }
    }
  }
  for (int j = 0; j < 2; ++j) {
    for (int i = 1; i <= n; ++i) {
      ans = (ans + dp[j][i][k]) % MOD;
    }
  }
  for (int u = 0; u < 2; ++u) {
    vector<vector<int>> lcp = getLcp(reverse(A[u ^ 1]), reverse(P));
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
      for (int l = 1; l <= k && i + l - 2 < n && A[u][i + l - 2] == P[k - l];
           ++l) {
        int p = lcp[n - (i + l - 2) - 1][l];
        if (l == 1) continue;
        if (p > l) {
          ans = (ans + dp[u ^ 1][i - 1][k - 2 * l]) % MOD;
        } else if (p + l == k && p == l && ok) {
          ans = (ans + 1) % MOD;
          cnt++;
        }
        if (p >= l) {
          ans = (ans + d[u ^ 1][i - 1][k - 2 * l]) % MOD;
        }
      }
    }
  }
  return ans;
}
int main() {
  ios::sync_with_stdio(false);
  string S1, S2;
  cin >> S1 >> S2;
  string P;
  cin >> P;
  int ans = solve({S1, S2}, P);
  if (((int)(P).size()) > 1) {
    ans = (ans + solve({S1, S2}, reverse(P), false)) % MOD;
  }
  ans %= MOD;
  if (ans < 0) ans += MOD;
  cout << ans << '\n';
}