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>
int n, m, f[2007][2007][2], g[2007][2007][2], wt, ss[19];
char fl[1 << 23], *A = fl;
char c, a[2007], b[2007], s[2007];
unsigned l1[2007], l2[2007], pw[2007], q[2007], w[2007], t[2007], e[2007];
void read(int& x) {
  char c;
  for (x = 0; '0' > (c = *A++) || c > '9';)
    ;
  while ('0' <= c && c <= '9') x = (x << 3) + (x << 1) + c - 48, (c = *A++);
}
void print(int x) {
  if (!x)
    putchar(48);
  else {
    for (wt = 0; x; ss[++wt] = x % 10, x /= 10)
      ;
    for (; wt; putchar(ss[wt--] + 48))
      ;
  }
}
int F(long long x) {
  if ((x %= 1000000007) < 0) x += 1000000007;
  return x;
}
int main() {
  int i, j, MAPLE = 0, tmp;
  for (*(fl + fread(fl, 1, 1 << 23, stdin)) = EOF; 'a' > (c = *A++) || c > 'z';)
    ;
  for (; 'a' <= c && c <= 'z'; a[++n] = c, (c = *A++))
    ;
  while ('a' > (c = *A++) || c > 'z')
    ;
  for (i = 1; i <= n; b[i] = c, (c = *A++), i++)
    ;
  while ('a' > (c = *A++) || c > 'z')
    ;
  for (; 'a' <= c && c <= 'z'; s[++m] = c, (c = *A++))
    ;
  if (m == 1) {
    for (i = 1; i <= n; MAPLE += (a[i] == s[1]) + (b[i] == s[1]), i++)
      ;
    return print(MAPLE), 0;
  }
  if (m == 2) {
    for (MAPLE =
             (a[n] == s[1] && b[n] == s[2]) + (a[n] == s[2] && b[n] == s[1]),
        i = 1;
         i < n; MAPLE += (a[i] == s[1] && a[i + 1] == s[2]) +
                         (b[i] == s[1] && b[i + 1] == s[2]) +
                         (a[i] == s[2] && a[i + 1] == s[1]) +
                         (b[i] == s[2] && b[i + 1] == s[1]) +
                         (a[i] == s[1] && b[i] == s[2]) +
                         (a[i] == s[2] && b[i] == s[1]),
        i++)
      ;
    return print(MAPLE), 0;
  }
  for (pw[0] = i = 1; i <= m || i <= n;
       pw[i] = (long long)pw[i - 1] * 147 % 1000000007, i++)
    ;
  for (i = 1; i <= n; l1[i] = ((long long)l1[i - 1] * 147 + a[i]) % 1000000007,
      l2[i] = ((long long)l2[i - 1] * 147 + b[i]) % 1000000007, i++)
    ;
  for (i = 1; i <= m; q[i] = ((long long)q[i - 1] * 147 + s[i]) % 1000000007,
      w[i] = ((long long)w[i - 1] * 147 + s[m - i + 1]) % 1000000007, i++)
    ;
  for (i = 1; i <= m; t[i] = F(w[m - i] - (long long)w[m - (i << 1)] * pw[i]),
      e[i] = F(q[m - i] - (long long)q[m - (i << 1)] * pw[i]), i++)
    ;
  for (i = 0; i <= n; i++) {
    for (j = m > (i << 1) ? i << 1 : m; j > 1; j--) {
      if (a[i] == s[j]) (f[i][j][0] += f[i][j - 1][1]) %= 1000000007;
      if (b[i] == s[j]) (f[i][j][1] += f[i][j - 1][0]) %= 1000000007;
    }
    for (j = (i << 1) <= m ? m - (i << 1) + 1 : 1; j < m; j++) {
      if (a[i] == s[j]) (g[i][j][0] += g[i][j + 1][1]) %= 1000000007;
      if (b[i] == s[j]) (g[i][j][1] += g[i][j + 1][0]) %= 1000000007;
    }
    if (a[i] == s[1]) {
      for (tmp = 2, j = i - 1; a[j] == s[tmp] && (tmp << 1) < m; tmp++, j--)
        if (F(l2[i] - (long long)l2[j - 1] * pw[tmp]) ==
                F(q[tmp << 1] - (long long)q[tmp] * pw[tmp]) &&
            b[i + 1] == s[tmp << 1 | 1])
          f[i + 1][tmp << 1 | 1][1]++;
      if ((tmp << 1) == m && a[j] == s[tmp] &&
          F(l2[i] - (long long)l2[j - 1] * pw[tmp]) ==
              F(q[tmp << 1] - (long long)q[tmp] * pw[tmp]))
        MAPLE++;
    }
    if (b[i] == s[1]) {
      for (tmp = 2, j = i - 1; b[j] == s[tmp] && (tmp << 1) < m; tmp++, j--)
        if (F(l1[i] - (long long)l1[j - 1] * pw[tmp]) ==
                F(q[tmp << 1] - (long long)q[tmp] * pw[tmp]) &&
            a[i + 1] == s[tmp << 1 | 1])
          f[i + 1][tmp << 1 | 1][0]++;
      if ((tmp << 1) == m && b[j] == s[tmp] &&
          F(l1[i] - (long long)l1[j - 1] * pw[tmp]) ==
              F(q[tmp << 1] - (long long)q[tmp] * pw[tmp]))
        MAPLE++;
    }
    if (a[i] == s[m])
      for (tmp = 2, j = i - 1; a[j] == s[m - tmp + 1] && (tmp << 1) < m;
           tmp++, j--)
        if (F(l2[i] - (long long)l2[j - 1] * pw[tmp]) ==
                F(w[tmp << 1] - (long long)w[tmp] * pw[tmp]) &&
            b[i + 1] == s[m - (tmp << 1)])
          g[i + 1][m - (tmp << 1)][1]++;
    if (b[i] == s[m])
      for (tmp = 2, j = i - 1; b[j] == s[m - tmp + 1] && (tmp << 1) < m;
           tmp++, j--)
        if (F(l1[i] - (long long)l1[j - 1] * pw[tmp]) ==
                F(w[tmp << 1] - (long long)w[tmp] * pw[tmp]) &&
            a[i + 1] == s[m - (tmp << 1)])
          g[i + 1][m - (tmp << 1)][0]++;
    if (a[i + 1] == s[1])
      for (tmp = 2, j = i + 2; a[j] == s[tmp] && (tmp << 1) <= m; tmp++, j++)
        if (F(l2[j] - (long long)l2[i] * pw[tmp]) == t[tmp])
          (MAPLE += g[i][tmp << 1 | 1][1] + g[i + 1][tmp << 1][1]) %=
              1000000007;
    if (b[i + 1] == s[1])
      for (tmp = 2, j = i + 2; b[j] == s[tmp] && (tmp << 1) <= m; tmp++, j++)
        if (F(l1[j] - (long long)l1[i] * pw[tmp]) == t[tmp])
          (MAPLE += g[i][tmp << 1 | 1][0] + g[i + 1][tmp << 1][0]) %=
              1000000007;
    if (f[i][0][0] = f[i][0][1] = g[i][m + 1][0] = g[i][m + 1][1] = 1,
        a[i + 1] == s[m])
      for (tmp = 2, j = i + 2; a[j] == s[m - tmp + 1] && (tmp << 1) <= m;
           tmp++, j++)
        if (F(l2[j] - (long long)l2[i] * pw[tmp]) == e[tmp])
          (MAPLE += f[i][m - (tmp << 1 | 1) + 1][1] +
                    f[i + 1][m - (tmp << 1) + 1][1]) %= 1000000007;
    if (b[i + 1] == s[m])
      for (tmp = 2, j = i + 2; b[j] == s[m - tmp + 1] && (tmp << 1) <= m;
           tmp++, j++)
        if (F(l1[j] - (long long)l1[i] * pw[tmp]) == e[tmp])
          (MAPLE += f[i][m - (tmp << 1 | 1) + 1][0] +
                    f[i + 1][m - (tmp << 1) + 1][0]) %= 1000000007;
    for (j = 0; j <= m + 1; j++) {
      if (f[i][j][0] && a[i + 1] == s[j + 1])
        (f[i + 1][j + 1][0] += f[i][j][0]) %= 1000000007;
      if (f[i][j][1] && b[i + 1] == s[j + 1])
        (f[i + 1][j + 1][1] += f[i][j][1]) %= 1000000007;
      if (g[i][j][0] && a[i + 1] == s[j - 1])
        (g[i + 1][j - 1][0] += g[i][j][0]) %= 1000000007;
      if (g[i][j][1] && b[i + 1] == s[j - 1])
        (g[i + 1][j - 1][1] += g[i][j][1]) %= 1000000007;
    }
    (MAPLE += ((long long)f[i][m][0] + f[i][m][1] + g[i][1][0] + g[i][1][1]) %
              1000000007) %= 1000000007;
  }
  print(MAPLE);
}