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>
#pragma comment(linker, "/STACK:100000000")
using namespace std;
char m[2][2100], s[2100];
int h[2][2100][2100], w[2100][2100];
int d[2][2][2100][2100], l, n;
inline void add(int &x, int y) {
  x += y;
  if (x >= 1000000007) x -= 1000000007;
}
int ch(int i, bool di, int j, int k, bool dj) {
  int t;
  if (di)
    t = i + 1;
  else
    t = l - i;
  if (t % 2 || t < 4) return 0;
  t /= 2;
  int i1, i2, i3;
  if (di) {
    i1 = i - t + 1;
    i2 = i1 - 1;
    i3 = 0;
  } else {
    i1 = i + t - 1;
    i2 = i1 + 1, i3 = l - 1;
  }
  int j1;
  if (dj)
    j1 = j - t + 1;
  else
    j1 = j + t - 1;
  if (j1 >= n || j1 < 0) return 0;
  return w[i][i1] == h[k][j][j1] && w[i2][i3] == h[k ^ 1][j1][j];
}
int main() {
  int i, j, k;
  scanf("%s%s%s", m[0], m[1], s);
  n = strlen(m[0]);
  l = strlen(s);
  if (l == 1) {
    k = 0;
    for (i = 0; i < 2; i++)
      for (j = 0; j < n; k += s[0] == m[i][j], j++)
        ;
    printf("%d\n", k);
    return 0;
  }
  if (l == 2) {
    k = 0;
    for (i = 0; i < 2; i++)
      for (j = 0; j + 1 < n; k += s[0] == m[i][j] && s[1] == m[i][j + 1],
          k += s[1] == m[i][j] && s[0] == m[i][j + 1], j++)
        ;
    for (j = 0; j < n; k += s[0] == m[0][j] && s[1] == m[1][j],
        k += s[1] == m[0][j] && s[0] == m[1][j], j++)
      ;
    printf("%d\n", k);
    return 0;
  }
  for (k = 0; k < 2; k++)
    for (i = 0; i < n; i++) {
      h[k][i][i] = m[k][i];
      for (j = i + 1; j < n;
           h[k][i][j] =
               ((long long)h[k][i][j - 1] * 257 + m[k][j]) % 1000000007,
          j++)
        ;
      for (j = i - 1; j >= 0;
           h[k][i][j] =
               ((long long)h[k][i][j + 1] * 257 + m[k][j]) % 1000000007,
          j--)
        ;
    }
  for (i = 0; i < l; i++) {
    w[i][i] = s[i];
    for (j = i + 1; j < l;
         w[i][j] = ((long long)w[i][j - 1] * 257 + s[j]) % 1000000007, j++)
      ;
    for (j = i - 1; j >= 0;
         w[i][j] = ((long long)w[i][j + 1] * 257 + s[j]) % 1000000007, j--)
      ;
  }
  for (k = 0; k < 2; k++)
    for (j = 0; j < n; j++)
      if (s[l - 1] == m[k][j]) {
        d[0][k][l - 1][j] = 1;
        d[1][k][l - 1][j] = 1;
      }
  for (i = l - 2; i >= 0; i--)
    for (j = 0; j < n; j++)
      for (k = 0; k < 2; k++)
        if (s[i] == m[k][j]) {
          add(d[0][k][i][j], ch(i, 0, j, k, 0));
          add(d[1][k][i][j], ch(i, 0, j, k, 1));
          if (j + 1 < n) add(d[0][k][i][j], d[0][k][i + 1][j + 1]);
          if (j > 0) add(d[1][k][i][j], d[1][k][i + 1][j - 1]);
          if (s[i + 1] == m[k ^ 1][j]) {
            if (i + 1 == l - 1) {
              add(d[0][k][i][j], 1);
              add(d[1][k][i][j], 1);
            } else {
              if (j + 1 < n) add(d[0][k][i][j], d[0][k ^ 1][i + 2][j + 1]);
              if (j > 0) add(d[1][k][i][j], d[1][k ^ 1][i + 2][j - 1]);
            }
          }
        }
  int z = 0;
  for (k = 0; k < 2; k++)
    for (j = 0; j < n; j++)
      for (add(z, d[0][k][0][j]), add(z, d[1][k][0][j]), i = 4; i < l; i += 2) {
        if (ch(i - 1, 1, j, k, 0) && j > 0) add(z, d[1][k][i][j - 1]);
        if (ch(i - 1, 1, j, k, 1) && j + 1 < n) add(z, d[0][k][i][j + 1]);
      }
  printf("%d\n", z);
  return 0;
}