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>
template <typename T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  bool flag = false;
  while (!isdigit(c)) {
    if (c == '-') flag = true;
    c = getchar();
  }
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  if (flag) x = -x;
}
using namespace std;
const int P = 1e9 + 7;
const int base = 13331;
const int PP = 998244853;
inline void ADD(int &a, int b) {
  a += b;
  if (a >= P) a -= P;
}
inline long long quickpow(long long x, int k, int P) {
  long long res = 1;
  while (k) {
    if (k & 1) res = res * x % P;
    x = x * x % P;
    k >>= 1;
  }
  return res;
}
int n, m;
char s[2][2011], t[2011];
long long ha_s[2][2011], ha_t[2011], ah_t[2011], mi[2011], invmi[2011];
inline bool check_0(int s_r, int s_c, int t_c, int len) {
  if (s_c < 1 || s_c + len - 1 > n || t_c < 1 || t_c + len - 1 > m)
    return false;
  long long s_ha = (ha_s[s_r][s_c + len - 1] - ha_s[s_r][s_c - 1] + PP) % PP *
                   invmi[s_c - 1] % PP;
  long long t_ha =
      (ha_t[t_c + len - 1] - ha_t[t_c - 1] + PP) % PP * invmi[t_c - 1] % PP;
  return (s_ha % PP + PP) % PP == (t_ha % PP + PP) % PP;
}
inline bool check_1(int s_r, int s_c, int t_c, int len) {
  if (s_c < 1 || s_c + len - 1 > n || t_c < 1 || t_c + len - 1 > m)
    return false;
  int t_l = t_c, t_r = t_c + len - 1;
  t_l = m - t_l + 1, t_r = m - t_r + 1;
  swap(t_l, t_r);
  t_c = t_l;
  long long s_ha = (ha_s[s_r][s_c + len - 1] - ha_s[s_r][s_c - 1] + PP) % PP *
                   invmi[s_c - 1] % PP;
  long long t_ha =
      (ah_t[t_c + len - 1] - ah_t[t_c - 1] + PP) % PP * invmi[t_c - 1] % PP;
  return (s_ha % PP + PP) % PP == (t_ha % PP + PP) % PP;
}
int f[2011][2011][2][2];
long long ans;
inline void DP() {
  memset(f, 0, sizeof(f));
  long long res = 0;
  for (int i = n; i; --i) {
    for (int j = m; j; --j) {
      for (int a = 0; a <= 1; ++a)
        if (s[a][i] == t[j]) {
          if (j == m) ADD(f[i][j][a][0], 1);
          ADD(f[i][j][a][0], f[i + 1][j + 1][a][0]);
          ADD(f[i][j][a][0], f[i + 1][j + 1][a][1]);
        }
      for (int a = 0; a <= 1; ++a)
        if (s[a][i] == t[j]) {
          int l = (m - j + 1) >> 1;
          if (!((m - j + 1) & 1) && l > 1 && check_0(a, i, j, l) &&
              check_1(a ^ 1, i, j + l, l))
            ADD(f[i][j][a][1], 1);
          ADD(f[i][j][a][1], f[i][j + 1][a ^ 1][0]);
        }
      for (int a = 0; a <= 1; ++a) {
        if (j == 1) res += f[i][j][a][0] + f[i][j][a][1];
        int l = (j - 1) >> 1;
        if (l > 1 && !((j - 1) & 1) && check_1(a ^ 1, i - l, 1, l) &&
            check_0(a, i - l, l + 1, l))
          res += f[i][j][a][0] + f[i][j][a][1];
      }
    }
  }
  ans = (ans + res) % P;
}
inline void work() {
  mi[0] = 1;
  const int up = max(n, m) + 1;
  invmi[0] = 1;
  for (int i = 1; i <= up; ++i)
    mi[i] = mi[i - 1] * base % PP, invmi[i] = quickpow(mi[i], PP - 2, PP);
  for (int i = 1; i <= n; ++i) {
    ha_s[0][i] = (ha_s[0][i - 1] + s[0][i] * mi[i]) % PP;
    ha_s[1][i] = (ha_s[1][i - 1] + s[1][i] * mi[i]) % PP;
  }
  for (int i = 1; i <= m; ++i) {
    ha_t[i] = (ha_t[i - 1] + t[i] * mi[i]) % PP;
    ah_t[i] = (ah_t[i - 1] + t[m - i + 1] * mi[i]) % PP;
  }
  DP();
}
inline void sol() {
  work();
  reverse(s[0] + 1, s[0] + 1 + n);
  reverse(s[1] + 1, s[1] + 1 + n);
  work();
  printf("%lld\n", (ans % P + P) % P);
}
int main() {
  scanf("%s", s[0] + 1);
  scanf("%s", s[1] + 1);
  scanf("%s", t + 1);
  n = strlen(s[0] + 1), m = strlen(t + 1);
  if (m <= 2) {
    if (m == 1) {
      int res = 0;
      for (int i = 0; i <= 1; ++i)
        for (int j = 1; j <= n; ++j)
          if (s[i][j] == t[1]) ++res;
      printf("%d\n", res);
    } else if (m == 2) {
      int res = 0;
      for (int j = 1; j <= n; ++j)
        if (s[0][j] == t[1]) {
          if (s[1][j] == t[2]) ++res;
          if (s[0][j + 1] == t[2]) ++res;
          if (s[0][j - 1] == t[2]) ++res;
        }
      for (int j = 1; j <= n; ++j)
        if (s[1][j] == t[1]) {
          if (s[0][j] == t[2]) ++res;
          if (s[1][j + 1] == t[2]) ++res;
          if (s[1][j - 1] == t[2]) ++res;
        }
      printf("%d\n", res);
    }
    return 0;
  }
  sol();
  return 0;
}