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 MAXN = 2e3 + 5;
const long long p = 1e9 + 7;
long long dpr[2][MAXN][MAXN], dpl[2][MAXN][MAXN];
int lcpr[2][MAXN][MAXN], lcpl[2][MAXN][MAXN];
string s[2], w;
int n, m;
void complcp() {
  for (int j = 0; j < n; ++j)
    for (int i = 0; i < m; ++i)
      for (int r = 0; r < 2; ++r) {
        if (j == 0)
          lcpl[r][j][i] = (s[r][j] == w[i]);
        else
          lcpl[r][j][i] = (s[r][j] == w[i])
                              ? ((i == m - 1) ? 1 : 1 + lcpl[r][j - 1][i + 1])
                              : 0;
      }
  for (int j = n - 1; j >= 0; --j)
    for (int i = 0; i < m; ++i)
      for (int r = 0; r < 2; ++r) {
        if (j == n - 1)
          lcpr[r][j][i] = (s[r][j] == w[i]);
        else
          lcpr[r][j][i] = (s[r][j] == w[i])
                              ? ((i == m - 1) ? 1 : 1 + lcpr[r][j + 1][i + 1])
                              : 0;
      }
}
void compdp() {
  for (int j = 0; j < n; ++j)
    for (int i = 0; i < m; ++i)
      for (int r = 0; r < 2; ++r) {
        if (j == 0) {
          if (i < m - 2) continue;
          if (i == m - 1)
            dpl[r][j][i] = (s[r][j] == w[i]);
          else if (i == m - 2)
            dpl[r][j][i] = ((s[r][j] == w[i]) && (s[1 - r][j] == w[i + 1]));
        } else {
          if ((s[r][j] != w[i])) {
            dpl[r][j][i] = 0;
            continue;
          }
          if (i == m - 1) {
            dpl[r][j][i] = 1;
            continue;
          }
          if (i == m - 2) {
            dpl[r][j][i] += (s[1 - r][j] == w[i + 1]);
            dpl[r][j][i] += (s[r][j - 1] == w[i + 1]);
            continue;
          }
          dpl[r][j][i] += dpl[r][j - 1][i + 1];
          if (s[1 - r][j] == w[i + 1]) dpl[r][j][i] += dpl[1 - r][j - 1][i + 2];
          if (((m - i) % 2 == 0) && ((m - i) <= 2 * j + 2)) {
            int x = (m - i) / 2;
            dpl[r][j][i] +=
                ((lcpl[r][j][i] >= x) && (lcpr[1 - r][j + 1 - x][i + x] >= x));
          }
          dpl[r][j][i] %= p;
        }
      }
  for (int j = n - 1; j >= 0; --j)
    for (int i = 0; i < m; ++i)
      for (int r = 0; r < 2; ++r) {
        if (j == n - 1) {
          if (i < m - 2) continue;
          if (i == m - 1)
            dpr[r][j][i] = (s[r][j] == w[i]);
          else if (i == m - 2)
            dpr[r][j][i] = ((s[r][j] == w[i]) && (s[1 - r][j] == w[i + 1]));
        } else {
          if (s[r][j] != w[i]) continue;
          if (i == m - 1) {
            dpr[r][j][i] = 1;
            continue;
          }
          if (i == m - 2) {
            dpr[r][j][i] += (s[r][j + 1] == w[i + 1]);
            dpr[r][j][i] += (s[1 - r][j] == w[i + 1]);
            continue;
          }
          dpr[r][j][i] += dpr[r][j + 1][i + 1];
          if (s[1 - r][j] == w[i + 1]) dpr[r][j][i] += dpr[1 - r][j + 1][i + 2];
          if (((m - i) % 2 == 0) && ((m - i) <= 2 * (n - j))) {
            int x = (m - i) / 2;
            dpr[r][j][i] +=
                ((lcpr[r][j][i] >= x) && (lcpl[1 - r][j + x - 1][i + x] >= x));
          }
          dpr[r][j][i] %= p;
        }
      }
}
long long finish() {
  long long tot = 0;
  if (m == 1) {
    for (int r = 0; r < 2; ++r)
      for (int j = 0; j < n; ++j) tot += (s[r][j] == w[0]);
    return tot;
  }
  for (int r = 0; r < 2; ++r)
    for (int j = 0; j < n; ++j)
      tot += (lcpl[r][j][0] >= m), tot += (lcpr[r][j][0] >= m);
  for (int r = 0; r < 2; ++r)
    for (int j = 0; j < n; ++j) {
      if ((s[r][j] != w[0]) || (s[1 - r][j] != w[1])) continue;
      if (m == 2) {
        tot++;
        continue;
      }
      if (j != 0) tot = (tot + dpl[1 - r][j - 1][2]) % p;
      if (j != n - 1) tot = (tot + dpr[1 - r][j + 1][2]) % p;
    }
  for (int r = 0; r < 2; ++r)
    for (int j = 0; j < n; ++j)
      for (int x = 1; x < n; ++x) {
        if (x >= m - 1) continue;
        if (j + x > n - 1) continue;
        if (j + x <= n - 1) {
          if ((lcpr[r][j][0] < x + 1) || (s[1 - r][j + x] != w[x + 1]))
            continue;
          if (x + 1 == m - 1) {
            tot = (tot + 1) % p;
            continue;
          }
          if (j + x < n - 1) tot = (tot + dpr[1 - r][j + x + 1][x + 2]) % p;
          if (m <= 2 * (x + 1)) tot += (lcpl[1 - r][j + x][x + 1] >= m - x - 1);
          if ((j > 0) && (lcpl[1 - r][j + x][x + 1] >= x + 1))
            tot = (tot + dpl[1 - r][j - 1][2 * x + 2]) % p;
        }
      }
  for (int r = 0; r < 2; ++r)
    for (int j = 0; j < n; ++j)
      for (int x = 1; x <= n; ++x) {
        if (x >= m - 1) continue;
        if (j - x >= 0) {
          if ((lcpl[r][j][0] < x + 1) || (s[1 - r][j - x] != w[x + 1]))
            continue;
          if (x + 1 == m - 1) {
            tot = (tot + 1) % p;
            continue;
          }
          if (j - x > 0) tot = (tot + dpl[1 - r][j - x - 1][x + 2]) % p;
          if (m <= 2 * (x + 1)) tot += (lcpr[1 - r][j - x][x + 1] >= m - x - 1);
          if ((j < n - 1) && (lcpr[1 - r][j - x][x + 1] >= x + 1))
            tot = (tot + dpr[1 - r][j + 1][2 * x + 2]) % p;
        }
      }
  return (tot % p);
}
int main() {
  cin >> s[0] >> s[1] >> w;
  n = s[0].length(), m = w.length();
  complcp();
  compdp();
  cout << finish() << endl;
}