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 int base = 233;
unsigned long long pw[2010];
unsigned long long extend(unsigned long long a, char c) { return a * base + c; }
int n, k;
struct S {
  char st[2010];
  unsigned long long f[2010], g[2010];
  int len;
  void init() {
    scanf("%s", st + 1);
    len = strlen(st + 1);
    f[0] = 0;
    for (int i = 1; i <= len; i++) f[i] = extend(f[i - 1], st[i]);
    g[len + 1] = 0;
    for (int i = len; i >= 1; i--) g[i] = extend(g[i + 1], st[i]);
    return;
  }
  unsigned long long getval(int l, int r) {
    return f[r] - f[l - 1] * pw[r - l + 1];
  }
  unsigned long long rgetval(int l, int r) {
    return g[l] - g[r + 1] * pw[r - l + 1];
  }
} a[2], b;
int check_lefts(int o, int pos, int len) {
  if (len % 2 != 0 || len / 2 > pos || len == 2) return 0;
  len /= 2;
  if (a[o ^ 1].rgetval(pos - len + 1, pos) != b.getval(1, len)) return 0;
  if (a[o].getval(pos - len + 1, pos) != b.getval(len + 1, len * 2)) return 0;
  return 1;
}
int check_lefte(int o, int pos, int len) {
  if (len % 2 != 0 || len / 2 > pos || len == 2) return 0;
  len /= 2;
  if (a[o].rgetval(pos - len + 1, pos) != b.getval(k - len * 2 + 1, k - len))
    return 0;
  if (a[o ^ 1].getval(pos - len + 1, pos) != b.getval(k - len + 1, k)) return 0;
  return 1;
}
int check_rights(int o, int pos, int len) {
  if (len % 2 != 0 || len / 2 > n - pos + 1 || len == 2) return 0;
  len /= 2;
  if (a[o ^ 1].getval(pos, pos + len - 1) != b.getval(1, len)) return 0;
  if (a[o].rgetval(pos, pos + len - 1) != b.getval(len + 1, len * 2)) return 0;
  return 1;
}
int check_righte(int o, int pos, int len) {
  if (len % 2 != 0 || len / 2 > n - pos + 1 || len == 2) return 0;
  len /= 2;
  if (a[o].getval(pos, pos + len - 1) != b.getval(k - len * 2 + 1, k - len))
    return 0;
  if (a[o ^ 1].rgetval(pos, pos + len - 1) != b.getval(k - len + 1, k))
    return 0;
  return 1;
}
int dp[2][2][2010][2];
void add(int& x, int y) {
  x += y;
  if (x >= 1000000007) x -= 1000000007;
  return;
}
int main() {
  a[0].init();
  a[1].init();
  b.init();
  n = a[0].len;
  k = b.len;
  pw[0] = 1;
  for (int i = 1; i <= max(n, k); i++) pw[i] = pw[i - 1] * base;
  int ans = 0;
  for (int i = 1; i <= k; i++) {
    int now = i & 1;
    for (int o = 0; o < 2; o++)
      for (int pos = 1; pos <= n; pos++)
        for (int x = 0; x < 2; x++) dp[now][o][pos][x] = 0;
    for (int o = 0; o < 2; o++)
      for (int pos = 1; pos <= n; pos++)
        for (int x = 0; x < 2; x++) {
          if (!x && a[o ^ 1].st[pos] == b.st[i])
            add(dp[now][o ^ 1][pos][1], dp[now ^ 1][o][pos][x]);
          if (pos < n && a[o].st[pos + 1] == b.st[i])
            add(dp[now][o][pos + 1][0], dp[now ^ 1][o][pos][x]);
        }
    for (int o = 0; o < 2; o++)
      for (int pos = 1; pos <= n; pos++) {
        if (check_lefts(o, pos - 1, i - 1)) {
          if (check_righte(o, pos, k - i + 1)) add(ans, 1);
          if (a[o].st[pos] == b.st[i]) add(dp[now][o][pos][0], 1);
        }
      }
    for (int o = 0; o < 2; o++)
      for (int pos = 1; pos <= n; pos++)
        if (check_righte(o, pos + 1, k - i)) {
          add(ans, dp[now][o][pos][0]);
          add(ans, dp[now][o][pos][1]);
        }
  }
  memset(dp, 0, sizeof(dp));
  for (int i = 1; i <= k; i++) {
    int now = i & 1;
    for (int o = 0; o < 2; o++)
      for (int pos = 1; pos <= n; pos++)
        for (int x = 0; x < 2; x++) dp[now][o][pos][x] = 0;
    for (int o = 0; o < 2; o++)
      for (int pos = 1; pos <= n; pos++)
        for (int x = 0; x < 2; x++) {
          if (!x && a[o ^ 1].st[pos] == b.st[i])
            add(dp[now][o ^ 1][pos][1], dp[now ^ 1][o][pos][x]);
          if (pos > 1 && a[o].st[pos - 1] == b.st[i])
            add(dp[now][o][pos - 1][0], dp[now ^ 1][o][pos][x]);
        }
    for (int o = 0; o < 2; o++)
      for (int pos = 1; pos <= n; pos++) {
        if (check_rights(o, pos + 1, i - 1)) {
          if (check_lefte(o, pos, k - i + 1)) {
            add(ans, 1);
          }
          if (a[o].st[pos] == b.st[i]) add(dp[now][o][pos][0], 1);
        }
      }
    for (int o = 0; o < 2; o++)
      for (int pos = 1; pos <= n; pos++)
        if (check_lefte(o, pos - 1, k - i)) {
          if (k > 1) add(ans, dp[now][o][pos][0]);
          if (k > 2) add(ans, dp[now][o][pos][1]);
        }
  }
  printf("%d\n", ans);
  return 0;
}