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 <class T>
inline T read() {
  register T data = 0, w = 1;
  register char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (isdigit(ch)) data = data * 10 + ch - '0', ch = getchar();
  return data * w;
}
template <class T>
inline T read(register T& x) {
  return x = read<T>();
}
const int N = 2020, P1 = 1e9 + 7, P2 = 1e9 + 9;
int n, m, ans;
int tm1[N], tm2[N], tm1_[N], tm2_[N];
int f[2][N][N];
struct dd {
  int x, y;
  bool operator==(const dd& n) const { return x == n.x && y == n.y; }
} t1, t2, t3, t4;
struct cc {
  char s[N];
  int len, pre1[N], pre2[N], suf1[N], suf2[N];
  void read() {
    scanf("%s", s + 1), len = strlen(s + 1);
    for (int i = 1; i <= len; ++i) {
      pre1[i] = ((long long)tm1[i - 1] * s[i] + pre1[i - 1]) % P1;
      pre2[i] = ((long long)tm2[i - 1] * s[i] + pre2[i - 1]) % P2;
    }
    for (int i = len; i; --i) {
      suf1[i] = ((long long)tm1[len - i] * s[i] + suf1[i + 1]) % P1;
      suf2[i] = ((long long)tm2[len - i] * s[i] + suf2[i + 1]) % P2;
    }
  }
  dd get_hash(int l, int r) {
    dd t;
    if (l <= r) {
      t.x = (long long)tm1_[l - 1] * (pre1[r] + P1 - pre1[l - 1]) % P1;
      t.y = (long long)tm2_[l - 1] * (pre2[r] + P2 - pre2[l - 1]) % P2;
    } else {
      t.x = (long long)tm1_[len - l] * (suf1[r] + P1 - suf1[l + 1]) % P1;
      t.y = (long long)tm2_[len - l] * (suf2[r] + P2 - suf2[l + 1]) % P2;
    }
    return t;
  }
} s1, s2, w;
int ksm(int x, int y, int P) {
  int z = 1;
  for (; y; y >>= 1, x = (long long)x * x % P)
    if (y & 1) z = (long long)z * x % P;
  return z;
}
void init() {
  int n = 2000;
  tm1[0] = tm2[0] = tm1_[0] = tm2_[0] = 1;
  for (int i = 1; i <= n; ++i)
    tm1[i] = 31LL * tm1[i - 1] % P1, tm2[i] = 31LL * tm2[i - 1] % P2;
  tm1_[n] = ksm(tm1[n], P1 - 2, P1), tm2_[n] = ksm(tm2[n], P2 - 2, P2);
  for (int i = n - 1; i; --i)
    tm1_[i] = 31LL * tm1_[i + 1] % P1, tm2_[i] = 31LL * tm2_[i + 1] % P2;
  s1.read(), s2.read(), w.read();
}
int main() {
  init();
  n = s1.len, m = w.len;
  f[0][n + 1][0] = f[1][n + 1][0] = 1;
  for (int i = n; i; --i) {
    f[0][i][0] = f[1][i][0] = 1;
    for (int k = 2; k + k <= m && i + k - 1 <= n; ++k) {
      t1 = s1.get_hash(i, i + k - 1), t2 = s2.get_hash(i, i + k - 1);
      t3 = w.get_hash(m, m - k + 1), t4 = w.get_hash(m - k - k + 1, m - k);
      if (t1 == t3 && t2 == t4) f[1][i][k + k] = 1;
      if (t2 == t3 && t1 == t4) f[0][i][k + k] = 1;
    }
  }
  for (int i = n; i; --i)
    for (int k = 1; k <= m; ++k) {
      if (s1.s[i] == w.s[m - k + 1]) (f[0][i][k] += f[0][i + 1][k - 1]) %= P1;
      if (s2.s[i] == w.s[m - k + 1]) (f[1][i][k] += f[1][i + 1][k - 1]) %= P1;
      if (k > 1 && s1.s[i] == w.s[m - k + 1] && s2.s[i] == w.s[m - k + 2])
        (f[0][i][k] += f[1][i + 1][k - 2]) %= P1;
      if (k > 1 && s2.s[i] == w.s[m - k + 1] && s1.s[i] == w.s[m - k + 2])
        (f[1][i][k] += f[0][i + 1][k - 2]) %= P1;
    }
  for (int i = 1; i <= n + 1; ++i) {
    (ans += f[0][i][m]) %= P1;
    (ans += f[1][i][m]) %= P1;
    for (int k = 2; k + k <= m && k < i; ++k) {
      t1 = s1.get_hash(i - k, i - 1), t2 = s2.get_hash(i - k, i - 1);
      t3 = w.get_hash(k, 1), t4 = w.get_hash(k + 1, k + k);
      if (t1 == t3 && t2 == t4) (ans += f[1][i][m - k - k]) %= P1;
      if (t2 == t3 && t1 == t4) (ans += f[0][i][m - k - k]) %= P1;
    }
  }
  if (m == 1) return printf("%d\n", ans), 0;
  memset(f, 0, sizeof f);
  f[0][n + 1][0] = f[1][n + 1][0] = 1;
  for (int i = n; i; --i) {
    f[0][i][0] = f[1][i][0] = 1;
    for (int k = 2; k + k < m && i + k - 1 <= n; ++k) {
      t1 = s1.get_hash(i, i + k - 1), t2 = s2.get_hash(i, i + k - 1);
      t3 = w.get_hash(1, k), t4 = w.get_hash(k + k, k + 1);
      if (t1 == t3 && t2 == t4) f[1][i][k + k] = 1;
      if (t2 == t3 && t1 == t4) f[0][i][k + k] = 1;
    }
  }
  for (int i = n; i; --i)
    for (int k = 1; k <= m; ++k) {
      if (s1.s[i] == w.s[k]) (f[0][i][k] += f[0][i + 1][k - 1]) %= P1;
      if (s2.s[i] == w.s[k]) (f[1][i][k] += f[1][i + 1][k - 1]) %= P1;
      if (m > 2 && k > 1 && s1.s[i] == w.s[k] && s2.s[i] == w.s[k - 1])
        (f[0][i][k] += f[1][i + 1][k - 2]) %= P1;
      if (m > 2 && k > 1 && s2.s[i] == w.s[k] && s1.s[i] == w.s[k - 1])
        (f[1][i][k] += f[0][i + 1][k - 2]) %= P1;
    }
  for (int i = 1; i <= n + 1; ++i) {
    (ans += f[0][i][m]) %= P1;
    (ans += f[1][i][m]) %= P1;
    for (int k = 2; k + k < m && k < i; ++k) {
      t1 = s1.get_hash(i - k, i - 1), t2 = s2.get_hash(i - k, i - 1);
      t3 = w.get_hash(m - k + 1, m), t4 = w.get_hash(m - k, m - k - k + 1);
      if (t1 == t3 && t2 == t4) (ans += f[1][i][m - k - k]) %= P1;
      if (t2 == t3 && t1 == t4) (ans += f[0][i][m - k - k]) %= P1;
    }
  }
  return printf("%d\n", ans), 0;
}