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 v[2][2020];
char str[2020];
int dp[2][2][2020][2020];
int n, m;
int get(int p, int ord, int a, int b) {
  if (a < 0 || a == n || b < 0 || b == m) return 0;
  if (dp[p][ord][a][b] + 1) return dp[p][ord][a][b];
  if (v[p][a] != str[b]) return 0;
  dp[p][ord][a][b] = 1 + get(p, ord, a + (ord ? 1 : -1), b + 1);
  return dp[p][ord][a][b];
}
int dp2[2][2][2020][2020];
int get2(int lado, int p, int pos, int match) {
  if (match == m) return 1;
  if (pos == -1 || pos == n) return 0;
  if (dp2[lado][p][pos][match] + 1) return dp2[lado][p][pos][match];
  if (match == m - 1) {
    if (v[p][pos] == str[match]) return 1;
    return 0;
  }
  if (v[p][pos] != str[match]) return 0;
  int ret = 0;
  if (v[p ^ 1][pos] == str[match + 1])
    ret += get2(lado, p ^ 1, pos + (lado ? 1 : -1), match + 2);
  ret += get2(lado, p, pos + (lado ? 1 : -1), match + 1);
  ret %= 1000000007;
  if (match % 2 == m % 2) {
    int u = (m - match) / 2;
    if (u != 1 && get(p, lado, pos, match) >= u &&
        get(p ^ 1, lado ^ 1, pos + (u - 1) * (lado ? 1 : -1), match + u) >= u)
      ret++;
    ret %= 1000000007;
  };
  return dp2[lado][p][pos][match] = ret;
}
int main() {
  scanf(" %s %s %s", v[0], v[1], str);
  n = strlen(v[0]);
  m = strlen(str);
  memset(dp, -1, sizeof(dp));
  memset(dp2, -1, sizeof(dp2));
  int ans = 0;
  for (int a = 0; a <= 1; a++)
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) {
        ;
        int sz = max(i, j) - min(i, j) + 1;
        if (i <= j) {
          if (get(a, 1, i, 0) < sz) continue;
          if (v[a ^ 1][j] != str[sz]) continue;
          if (sz + 1 == m) {
            ans++;
            continue;
          }
          ans += get2(1, a ^ 1, j + 1, sz + 1);
          ans %= 1000000007;
          int falta = m - sz;
          if (falta <= sz) {
            if (get(a ^ 1, 0, j, sz) == falta) ans++;
            continue;
          }
          if (get(a ^ 1, 0, j, sz) >= sz) ans += get2(0, a ^ 1, i - 1, 2 * sz);
          ans %= 1000000007;
        } else {
          if (get(a, 0, i, 0) < sz) continue;
          if (v[a ^ 1][j] != str[sz]) continue;
          if (sz + 1 == m) {
            ans++;
            continue;
          }
          ans += get2(0, a ^ 1, j - 1, sz + 1);
          ans %= 1000000007;
          int falta = m - sz;
          if (falta <= sz) {
            if (get(a ^ 1, 1, j, sz) == falta) ans++;
            continue;
          }
          if (get(a ^ 1, 1, j, sz) >= sz) ans += get2(1, a ^ 1, i + 1, 2 * sz);
          ans %= 1000000007;
        }
      };
  for (int a = 0; a <= 1; a++)
    for (int d = 0; d <= 1; d++)
      for (int i = 0; i < n; i++) {
        if (m == 1 && d == 1) continue;
        if (get(a, d, i, 0) == m) ans++;
      }
  printf("%d\n", ans % 1000000007);
}