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>
inline long long rd() {
  long long _x = 0;
  int _ch = getchar(), _f = 1;
  for (; !isdigit(_ch) && (_ch != '-') && (_ch != EOF); _ch = getchar())
    ;
  if (_ch == '-') {
    _f = 0;
    _ch = getchar();
  }
  for (; isdigit(_ch); _ch = getchar()) _x = _x * 10 + _ch - '0';
  return _f ? _x : -_x;
}
void write(long long _x) {
  if (_x >= 10)
    write(_x / 10), putchar(_x % 10 + '0');
  else
    putchar(_x + '0');
}
inline void wrt(long long _x, char _p) {
  if (_x < 0) putchar('-'), _x = -_x;
  write(_x);
  if (_p) putchar(_p);
}
int f[2005][2][2005], g[2005][2][2005];
int n, len;
char s[2][2005], t[2005];
struct HASH {
  int len;
  int h1, h2;
  HASH operator+(const char c) const {
    HASH ans;
    ans.h1 = (1ll * h1 * 37 + c) % 1222827239ll;
    ans.h2 = (1ll * h2 * 29 + c) % 1610612741ll;
    ans.len = len + 1;
    return ans;
  }
} w[2005], T[2005], S[2][2005], rS[2][2005];
HASH operator+(const HASH A, const HASH B) {
  HASH ans;
  ans.h1 = (1ll * A.h1 * w[B.len].h1 + B.h1) % 1222827239ll;
  ans.h2 = (1ll * A.h2 * w[B.len].h2 + B.h2) % 1610612741ll;
  ans.len = A.len + B.len;
  return ans;
}
HASH get(HASH* h, int l, int r) {
  HASH ans;
  ans.len = r - l + 1;
  ans.h1 = (1222827239ll + h[r].h1 -
            1ll * h[l - 1].h1 * w[ans.len].h1 % 1222827239ll) %
           1222827239ll;
  ans.h2 = (1610612741ll + h[r].h2 -
            1ll * h[l - 1].h2 * w[ans.len].h2 % 1610612741ll) %
           1610612741ll;
  return ans;
}
HASH getr(HASH* h, int l, int r) {
  HASH ans;
  ans.len = r - l + 1;
  ans.h1 = (1222827239ll + h[l].h1 -
            1ll * h[r + 1].h1 * w[ans.len].h1 % 1222827239ll) %
           1222827239ll;
  ans.h2 = (1610612741ll + h[l].h2 -
            1ll * h[r + 1].h2 * w[ans.len].h2 % 1610612741ll) %
           1610612741ll;
  return ans;
}
bool operator!=(const HASH A, const HASH B) {
  return A.h1 != B.h1 || A.h2 != B.h2;
}
bool operator==(const HASH A, const HASH B) {
  return A.h1 == B.h1 && A.h2 == B.h2;
}
void init() {
  w[0].h1 = 1, w[0].h2 = 1;
  for (int i = 1; i <= n; i++) {
    w[i].h1 = 1ll * w[i - 1].h1 * 37 % 1222827239ll;
    w[i].h2 = 1ll * w[i - 1].h2 * 29 % 1610612741ll;
  }
  for (int i = 1; i <= n; i++) {
    S[0][i] = S[0][i - 1] + (s[0][i] - 'a');
    S[1][i] = S[1][i - 1] + (s[1][i] - 'a');
  }
  for (int i = n; i >= 1; i--) {
    rS[0][i] = rS[0][i + 1] + (s[0][i] - 'a');
    rS[1][i] = rS[1][i + 1] + (s[1][i] - 'a');
  }
  for (int i = 1; i <= len; i++) {
    T[i] = T[i - 1] + (t[i] - 'a');
  }
}
int solveA() {
  memset(g, 0, sizeof g);
  memset(f, 0, sizeof f);
  int res = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < 2; j++) {
      if (s[j][i] == t[len]) res = (res + g[i - 1][j][len - 1]) % 1000000007;
      for (int k = i; k <= n && (k - i + 1) * 2 <= len; k++) {
        if (get(S[j ^ 1], i, k) + getr(rS[j], i, k) ==
            get(T, len - (k - i + 1) * 2 + 1, len))
          res = (res + g[i - 1][j ^ 1][len - (k - i + 1) * 2]) % 1000000007;
      }
    }
    for (int k = 1; k <= len; k++) {
      if (s[0][i] == t[k]) f[i][0][k] = g[i - 1][0][k - 1];
      if (s[1][i] == t[k]) f[i][1][k] = g[i - 1][1][k - 1];
    }
    for (int k = 1; k <= len; k++) {
      if (s[0][i] == t[k])
        g[i][0][k] = (f[i][1][k - 1] + g[i - 1][0][k - 1]) % 1000000007;
      if (s[1][i] == t[k])
        g[i][1][k] = (f[i][0][k - 1] + g[i - 1][1][k - 1]) % 1000000007;
    }
    for (int j = 0; j < 2; j++) {
      if (s[j][i] == t[1]) g[i][j][1]++;
      for (int k = i; (i - k + 1) * 2 <= len && k >= 1; k--) {
        if (getr(rS[j], k, i) + get(S[j ^ 1], k, i) == T[(i - k + 1) * 2])
          g[i][j ^ 1][(i - k + 1) * 2]++;
      }
    }
  }
  return res;
}
int solveC() {
  if (len % 2 != 0) return 0;
  int res = 0;
  for (int i = len / 2; i <= n; i++) {
    if (getr(rS[0], i - len / 2 + 1, i) + get(S[1], i - len / 2 + 1, i) ==
        T[len])
      res++;
    if (getr(rS[1], i - len / 2 + 1, i) + get(S[0], i - len / 2 + 1, i) ==
        T[len])
      res++;
  }
  return res;
}
int main() {
  scanf("%s", s[0] + 1);
  scanf("%s", s[1] + 1);
  scanf("%s", t + 1);
  n = strlen(s[0] + 1);
  len = strlen(t + 1);
  if (len == 1) {
    int ans = 0;
    for (int i = 0; i < 2; i++) {
      for (int j = 1; j <= n; j++) {
        if (s[i][j] == t[1]) ans++;
      }
    }
    wrt(ans, '\n');
    return 0;
  }
  init();
  int ans = 0;
  ans = (ans + solveC()) % 1000000007;
  ans = (ans + solveA()) % 1000000007;
  std::reverse(s[0] + 1, s[0] + 1 + n);
  std::reverse(s[1] + 1, s[1] + 1 + n);
  init();
  if (len > 2) ans = (ans + solveC()) % 1000000007;
  ans = (ans + solveA()) % 1000000007;
  wrt(ans, '\n');
}