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 long long N = 2e3 + 5;
const long long p = 1e9 + 7;
long long read() {
  long long s = 0;
  char c = getchar(), lc = '+';
  while (c < '0' || '9' < c) lc = c, c = getchar();
  while ('0' <= c && c <= '9') s = s * 10 + c - '0', c = getchar();
  return lc == '-' ? -s : s;
}
void write(long long x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  if (x < 10)
    putchar(x + '0');
  else {
    write(x / 10);
    putchar(x % 10 + '0');
  }
}
void print(long long x, char c = '\n') {
  write(x);
  putchar(c);
}
inline void add(long long &x, long long y) {
  x += y;
  if (x < 0) x += p;
  if (x >= p) x -= p;
}
char a[N], b[N], c[N];
long long dp[N][N][2], n, m, ans = 0;
const long long ADD = 1145141ll;
const long long MOD = 998244353ll;
long long a1[N], a2[N], b1[N], b2[N], c1[N], Pow[N];
long long get1(long long *a, long long l, long long r) {
  return (a[r] - a[l - 1] * Pow[r - l + 1] % MOD + MOD) % MOD;
}
long long get2(long long *a, long long l, long long r) {
  return (a[l] - a[r + 1] * Pow[r - l + 1] % MOD + MOD) % MOD;
}
void solve(bool flag) {
  memset(dp, 0, sizeof(dp));
  Pow[0] = 1;
  for (long long i = 1; i <= max(n, m); i++) Pow[i] = Pow[i - 1] * 27 % MOD;
  for (long long i = 1; i <= n; i++)
    a1[i] = (a1[i - 1] * 27 + a[i] - 'a' + 1 + ADD) % MOD;
  for (long long i = n; i >= 1; i--)
    a2[i] = (a2[i + 1] * 27 + a[i] - 'a' + 1 + ADD) % MOD;
  for (long long i = 1; i <= n; i++)
    b1[i] = (b1[i - 1] * 27 + b[i] - 'a' + 1 + ADD) % MOD;
  for (long long i = n; i >= 1; i--)
    b2[i] = (b2[i + 1] * 27 + b[i] - 'a' + 1 + ADD) % MOD;
  for (long long i = 1; i <= m; i++)
    c1[i] = (c1[i - 1] * 27 + c[i] - 'a' + 1 + ADD) % MOD;
  for (long long i = 1; i <= n; i++)
    for (long long j = 1; j < i; j++) {
      if ((i - j + 1) * 2 > m) continue;
      long long hash =
          (get2(a2, j, i) * Pow[i - j + 1] % MOD + get1(b1, j, i)) % MOD;
      if (hash == get1(c1, 1, (i - j + 1) * 2)) dp[i][(i - j + 1) * 2][1] = 1;
      hash = (get2(b2, j, i) * Pow[i - j + 1] % MOD + get1(a1, j, i)) % MOD;
      if (hash == get1(c1, 1, (i - j + 1) * 2)) dp[i][(i - j + 1) * 2][0] = 1;
    }
  for (long long i = 0; i <= n; i++)
    for (long long j = 0; j <= 1; j++) dp[i][0][j] = 1;
  for (long long i = 1; i <= n; i++)
    for (long long j = 1; j <= m; j++) {
      if (a[i] == c[j]) add(dp[i][j][0], dp[i - 1][j - 1][0]);
      if (j >= 2 && a[i] == c[j] && b[i] == c[j - 1])
        add(dp[i][j][0], dp[i - 1][j - 2][1]);
      if (b[i] == c[j]) add(dp[i][j][1], dp[i - 1][j - 1][1]);
      if (j >= 2 && b[i] == c[j] && a[i] == c[j - 1])
        add(dp[i][j][1], dp[i - 1][j - 2][0]);
      if (j == m) add(ans, dp[i][j][0]);
      if (j == m) add(ans, dp[i][j][1]);
    }
  for (long long i = 1; i <= n; i++)
    for (long long j = i + 1; j <= n; j++) {
      if ((j - i + 1) * 2 > m) continue;
      long long hash =
          (get1(a1, i, j) * Pow[j - i + 1] % MOD + get2(b2, i, j)) % MOD;
      if (hash == get1(c1, m - (j - i + 1) * 2 + 1, m))
        add(ans, dp[i - 1][m - (j - i + 1) * 2][0]);
      hash = (get1(b1, i, j) * Pow[j - i + 1] % MOD + get2(a2, i, j)) % MOD;
      if (hash == get1(c1, m - (j - i + 1) * 2 + 1, m))
        add(ans, dp[i - 1][m - (j - i + 1) * 2][1]);
    }
  if (flag) {
    for (long long i = 1; i <= n; i++)
      for (long long j = 1; j <= i; j++) {
        if ((i - j + 1) * 2 != m) continue;
        long long hash =
            (get2(a2, j, i) * Pow[i - j + 1] % MOD + get1(b1, j, i)) % MOD;
        if (hash == get1(c1, 1, (i - j + 1) * 2)) add(ans, -1);
        hash = (get2(b2, j, i) * Pow[i - j + 1] % MOD + get1(a1, j, i)) % MOD;
        if (hash == get1(c1, 1, (i - j + 1) * 2)) add(ans, -1);
      }
    for (long long i = 1; i <= n; i++)
      for (long long j = i + 1; j <= n; j++) {
        if ((j - i + 1) * 2 != m) continue;
        long long hash =
            (get1(a1, i, j) * Pow[j - i + 1] % MOD + get2(b2, i, j)) % MOD;
        if (hash == get1(c1, m - (j - i + 1) * 2 + 1, m)) add(ans, -1);
        hash = (get1(b1, i, j) * Pow[j - i + 1] % MOD + get2(a2, i, j)) % MOD;
        if (hash == get1(c1, m - (j - i + 1) * 2 + 1, m)) add(ans, -1);
      }
  }
}
signed main() {
  scanf("%s%s%s", a + 1, b + 1, c + 1);
  n = strlen(a + 1);
  m = strlen(c + 1);
  solve(0);
  for (long long i = 1; i <= n / 2; i++) {
    swap(a[i], a[n - i + 1]);
    swap(b[i], b[n - i + 1]);
  }
  solve(1);
  if (n == 1 || m == 1)
    print((ans + 1) / 2);
  else
    print(ans);
  return 0;
}