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 add(int& a, int b) {
  a += b;
  if (a >= 1000000007) a -= 1000000007;
  return 0;
}
int n, m, res, dp[2][2007][2007], pw1[2007], pw2[2007];
struct String {
  char s[2007];
  int pre1[2007], pre2[2007], suf1[2007], suf2[2007];
  int len;
  char operator[](int o) { return s[o]; }
  void read() {
    scanf("%s", s + 1);
    len = strlen(s + 1);
    for (int i = 1; i <= len; i++) {
      pre1[i] = (29LL * pre1[i - 1] % 1000000007 + s[i]) % 1000000007;
      pre2[i] = (31LL * pre2[i - 1] % 1000000007 + s[i]) % 1000000007;
    }
    for (int i = len; i > 0; i--) {
      suf1[i] = (29LL * suf1[i + 1] % 1000000007 + s[i]) % 1000000007;
      suf2[i] = (31LL * suf2[i + 1] % 1000000007 + s[i]) % 1000000007;
    }
  }
  pair<int, int> get(int l, int r) {
    if (l <= r)
      return make_pair(
          (pre1[r] - 1LL * pre1[l - 1] * pw1[r - l + 1] % 1000000007 +
           1000000007) %
              1000000007,
          (pre2[r] - 1LL * pre2[l - 1] * pw2[r - l + 1] % 1000000007 +
           1000000007) %
              1000000007);
    else
      return make_pair(
          (suf1[r] - 1LL * suf1[l + 1] * pw1[l - r + 1] % 1000000007 +
           1000000007) %
              1000000007,
          (suf2[r] - 1LL * suf2[l + 1] * pw2[l - r + 1] % 1000000007 +
           1000000007) %
              1000000007);
  }
} a, b, c;
int main() {
  pw1[0] = pw2[0] = 1;
  for (int i = 1; i <= 2000; i++) {
    pw1[i] = 1LL * pw1[i - 1] * 29 % 1000000007;
    pw2[i] = 1LL * pw2[i - 1] * 31 % 1000000007;
  }
  a.read();
  b.read();
  c.read();
  n = a.len, m = c.len;
  dp[0][n + 1][0] = dp[1][n + 1][0] = 1;
  for (int i = n; i > 0; i--) {
    dp[0][i][0] = dp[1][i][0] = 1;
    for (int k = 2; k * 2 <= m && i + k - 1 <= n; k++) {
      pair<int, int> t1 = a.get(i, i + k - 1), t2 = b.get(i, i + k - 1);
      pair<int, int> t3 = c.get(m, m - k + 1), t4 = c.get(m - k * 2 + 1, m - k);
      if (t1 == t3 && t2 == t4) dp[1][i][k * 2] = 1;
      if (t2 == t3 && t1 == t4) dp[0][i][k * 2] = 1;
    }
  }
  for (int i = n; i > 0; i--)
    for (int k = 1; k <= m; k++) {
      if (a[i] == c[m - k + 1]) add(dp[0][i][k], dp[0][i + 1][k - 1]);
      if (b[i] == c[m - k + 1]) add(dp[1][i][k], dp[1][i + 1][k - 1]);
      if (k > 1 && a[i] == c[m - k + 1] && b[i] == c[m - k + 2])
        add(dp[0][i][k], dp[1][i + 1][k - 2]);
      if (k > 1 && b[i] == c[m - k + 1] && a[i] == c[m - k + 2])
        add(dp[1][i][k], dp[0][i + 1][k - 2]);
    }
  for (int i = 1; i <= n + 1; i++) {
    add(res, dp[0][i][m]);
    add(res, dp[1][i][m]);
    for (int k = 2; k * 2 <= m && k < i; k++) {
      pair<int, int> t1 = a.get(i - k, i - 1), t2 = b.get(i - k, i - 1);
      pair<int, int> t3 = c.get(k, 1), t4 = c.get(k + 1, k * 2);
      if (t1 == t3 && t2 == t4) add(res, dp[1][i][m - 2 * k]);
      if (t2 == t3 && t1 == t4) add(res, dp[0][i][m - 2 * k]);
    }
  }
  if (m == 1) {
    cout << res << endl;
    return 0;
  }
  memset(dp, 0, sizeof dp);
  dp[0][n + 1][0] = dp[1][n + 1][0] = 1;
  for (int i = n; i > 0; i--) {
    dp[0][i][0] = dp[1][i][0] = 1;
    for (int k = 2; k * 2 < m && i + k - 1 <= n; k++) {
      pair<int, int> t1 = a.get(i, i + k - 1), t2 = b.get(i, i + k - 1);
      pair<int, int> t3 = c.get(1, k), t4 = c.get(k * 2, k + 1);
      if (t1 == t3 && t2 == t4) dp[1][i][k * 2] = 1;
      if (t2 == t3 && t1 == t4) dp[0][i][k * 2] = 1;
    }
  }
  for (int i = n; i > 0; i--)
    for (int k = 1; k <= m; k++) {
      if (a[i] == c[k]) add(dp[0][i][k], dp[0][i + 1][k - 1]);
      if (b[i] == c[k]) add(dp[1][i][k], dp[1][i + 1][k - 1]);
      if (m > 2 && k > 1 && a[i] == c[k] && b[i] == c[k - 1])
        add(dp[0][i][k], dp[1][i + 1][k - 2]);
      if (m > 2 && k > 1 && b[i] == c[k] && a[i] == c[k - 1])
        add(dp[1][i][k], dp[0][i + 1][k - 2]);
    }
  for (int i = 1; i <= n + 1; i++) {
    add(res, dp[0][i][m]);
    add(res, dp[1][i][m]);
    for (int k = 2; k + k < m && k < i; k++) {
      pair<int, int> t1 = a.get(i - k, i - 1), t2 = b.get(i - k, i - 1);
      pair<int, int> t3 = c.get(m - k + 1, m), t4 = c.get(m - k, m - k * 2 + 1);
      if (t1 == t3 && t2 == t4) add(res, dp[1][i][m - k * 2]);
      if (t2 == t3 && t1 == t4) add(res, dp[0][i][m - k * 2]);
    }
  }
  cout << res << endl;
  return 0;
}