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 maxn = 2010;
const long long Mod = 1e9 + 7;
const long long seed = 107;
long long f[3][maxn][maxn], pre[3][maxn], suf[3][maxn], n, m;
long long p[maxn], inv[maxn], g[maxn], ans;
char s[3][maxn], t[maxn];
inline long long power(long long a, long long b) {
  long long r = 1;
  while (b) {
    if (b & 1) r = r * a % Mod;
    a = a * a % Mod;
    b >>= 1;
  }
  return r;
}
inline long long Get(long long op, long long l, long long r, bool dic) {
  long long ret;
  if (dic == 0) {
    ret = (pre[op][r] - pre[op][l - 1]) % Mod;
    ret = ret * inv[l - 1] % Mod;
  } else {
    ret = (suf[op][l] - suf[op][r + 1]) % Mod;
    ret = ret * inv[n - r] % Mod;
  }
  return (ret + Mod) % Mod;
}
inline void Solve() {
  for (long long i = (0), _end_ = (2); i <= _end_; ++i) {
    long long N = i == 0 ? m : n;
    for (long long j = (1), _end_ = (N); j <= _end_; ++j)
      pre[i][j] = (pre[i][j - 1] + p[j] * (s[i][j] - 'a' + 1)) % Mod;
    for (long long j = N; j >= 1; --j)
      suf[i][j] = (suf[i][j + 1] + p[N - j + 1] * (s[i][j] - 'a' + 1)) % Mod;
  }
  memset((f), 0, sizeof(f));
  for (long long i = (1), _end_ = (n); i <= _end_; ++i)
    for (long long op = (1), _end_ = (2); op <= _end_; ++op) {
      if (s[0][1] == s[op][i]) ++f[op][i][1];
      for (long long len = (1), _end_ = (min(m / 2, i)); len <= _end_; ++len) {
        long long l = i - len + 1;
        if (Get(0, 1, len, 0) != Get(op, l, i, 1)) continue;
        if (Get(0, len + 1, len + len, 0) != Get(3 - op, l, i, 0)) continue;
        ++f[3 - op][i][len * 2];
      }
    }
  for (long long i = (1), _end_ = (n - 1); i <= _end_; ++i)
    for (long long op = (1), _end_ = (2); op <= _end_; ++op)
      for (long long j = (1), _end_ = (m); j <= _end_; ++j) {
        if (s[op][i + 1] == s[0][j + 1])
          f[op][i + 1][j + 1] = (f[op][i + 1][j + 1] + f[op][i][j]) % Mod;
        if (s[op][i + 1] == s[0][j + 1] && s[3 - op][i + 1] == s[0][j + 2])
          f[3 - op][i + 1][j + 2] =
              (f[3 - op][i + 1][j + 2] + f[op][i][j]) % Mod;
      }
  for (long long i = (1), _end_ = (n); i <= _end_; ++i)
    for (long long op = (1), _end_ = (2); op <= _end_; ++op) {
      ans = (ans + f[op][i][m]) % Mod;
      for (long long j = (1), _end_ = (m - 3); j <= _end_; ++j) {
        long long len = (m - j) / 2;
        if ((m - j) % 2 != 0 || i + len > n) continue;
        long long l = i + 1, r = i + len;
        long long L = m - len - len;
        if (Get(0, L + 1, L + len, 0) != Get(op, l, r, 0)) continue;
        if (Get(0, L + len + 1, L + len + len, 0) != Get(3 - op, l, r, 1))
          continue;
        ans = (ans + f[op][i][j]) % Mod;
      }
    }
}
signed main() {
  scanf("%s", s[1] + 1);
  scanf("%s", s[2] + 1);
  n = strlen(s[1] + 1);
  scanf("%s", s[0] + 1);
  m = strlen(s[0] + 1);
  p[0] = inv[0] = 1;
  for (long long i = (1), _end_ = (maxn - 10); i <= _end_; ++i) {
    p[i] = p[i - 1] * seed % Mod;
    inv[i] = inv[i - 1] * power(seed, Mod - 2) % Mod;
  }
  Solve();
  reverse(s[1] + 1, s[1] + n + 1);
  reverse(s[2] + 1, s[2] + n + 1);
  if (m != 1) Solve();
  if (m == 2) {
    for (long long i = (1), _end_ = (n); i <= _end_; ++i) {
      if (s[1][i] == s[0][1] && s[2][i] == s[0][2]) --ans;
      if (s[2][i] == s[0][1] && s[1][i] == s[0][2]) --ans;
    }
  }
  printf("%lld\n", (ans + Mod) % Mod);
  return 0;
}