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;
unsigned long long p[2002];
unsigned long long h[4][2002];
char aa[4][2002];
int dp[2][4][2002], n, l, xl;
int ans = 0;
const int mod = 1e9 + 7;
void gethashed(char* s, unsigned long long* h, int n) {
  for (int i = n; i >= 0; i--) {
    h[i] = h[i + 1] + s[i] * p[n - i];
  }
}
inline bool scmp(unsigned long long* a, int q, int r, unsigned long long* b,
                 int s, int t) {
  return q >= 0 && s >= 0 && r <= n && t <= l &&
         ((a[q] - a[r]) * p[q] == (b[s] - b[t]) * p[s]);
}
inline void cut(int& x) { x -= (x >= mod) * mod; }
inline void fill(int& x) { x += (x < 0) * mod; }
void work() {
  bool cur = 1;
  bool nxt = 0;
  for (int i = 0; i < 4; i++) {
    dp[0][i][0] = 1;
  }
  for (int i = 0; i <= n; i++) {
    cur = !cur;
    nxt = !nxt;
    for (int k = 0; k < 4; k++) {
      cut(ans += dp[cur][k][l]);
    }
    for (int j = 2; j <= xl; j++) {
      if (!scmp(h[1], i, i + j, h[3], 0, j)) {
        break;
      } else if (scmp(h[0], i, i + j, h[2], l - j - j, l - j)) {
        cut(ans += dp[cur][0][l - j - j]);
      }
    }
    for (int j = 2; j <= xl; j++) {
      if (!scmp(h[0], i, i + j, h[3], 0, j)) {
        break;
      } else if (scmp(h[1], i, i + j, h[2], l - j - j, l - j)) {
        cut(ans += dp[cur][1][l - j - j]);
      }
    }
    for (int j = 2; j <= xl; j++) {
      if (!scmp(h[1], i, i + j, h[2], 0, j)) {
        break;
      } else if (scmp(h[0], i, i + j, h[3], l - j - j, l - j)) {
        cut(ans += dp[cur][2][l - j - j]);
      }
    }
    for (int j = 2; j <= xl; j++) {
      if (!scmp(h[0], i, i + j, h[2], 0, j)) {
        break;
      } else if (scmp(h[1], i, i + j, h[3], l - j - j, l - j)) {
        cut(ans += dp[cur][3][l - j - j]);
      }
    }
    if (l % 2 == 0) {
      if (scmp(h[0], i - xl, i, h[2], xl, l) &&
          scmp(h[1], i - xl, i, h[3], xl, l)) {
        fill(--ans);
      }
      if (scmp(h[0], i - xl, i, h[3], xl, l) &&
          scmp(h[1], i - xl, i, h[2], xl, l)) {
        fill(--ans);
      }
      if (xl != 1 && scmp(h[0], i, i + xl, h[2], 0, xl) &&
          scmp(h[1], i, i + xl, h[3], 0, xl)) {
        fill(--ans);
      }
      if (xl != 1 && scmp(h[0], i, i + xl, h[3], 0, xl) &&
          scmp(h[1], i, i + xl, h[2], 0, xl)) {
        fill(--ans);
      }
    }
    if (i == n) {
      break;
    }
    for (int j = 0; j <= l; j++) {
      for (int k = 0; k < 4; k++) {
        dp[nxt][k][j] = 0;
      }
    }
    i++;
    for (int j = 0; j <= xl; j++) {
      if (j != 1) {
        if (!scmp(h[1], i - j, i, h[3], l - j, l)) {
          break;
        } else if (scmp(h[0], i - j, i, h[2], j, j << 1)) {
          cut(++dp[nxt][0][j << 1]);
        }
      }
    }
    for (int j = 0; j <= xl; j++) {
      if (j != 1) {
        if (!scmp(h[0], i - j, i, h[3], l - j, l)) {
          break;
        } else if (scmp(h[1], i - j, i, h[2], j, j << 1)) {
          cut(++dp[nxt][1][j << 1]);
        }
      }
    }
    for (int j = 0; j <= xl; j++) {
      if (j != 1) {
        if (!scmp(h[1], i - j, i, h[2], l - j, l)) {
          break;
        } else if (scmp(h[0], i - j, i, h[3], j, j << 1)) {
          cut(++dp[nxt][2][j << 1]);
        }
      }
    }
    for (int j = 0; j <= xl; j++) {
      if (j != 1) {
        if (!scmp(h[0], i - j, i, h[2], l - j, l)) {
          break;
        } else if (scmp(h[1], i - j, i, h[3], j, j << 1)) {
          cut(++dp[nxt][3][j << 1]);
        }
      }
    }
    i--;
    for (int j = 0; j < l; j++) {
      if (dp[cur][0][j]) {
        if (aa[0][i] == aa[2][j]) {
          cut(dp[nxt][0][j + 1] += dp[cur][0][j]);
          if (aa[1][i] == aa[2][j + 1]) {
            cut(dp[nxt][1][j + 2] += dp[cur][0][j]);
          }
        }
      }
    }
    for (int j = 0; j < l; j++) {
      if (dp[cur][1][j]) {
        if (aa[1][i] == aa[2][j]) {
          cut(dp[nxt][1][j + 1] += dp[cur][1][j]);
          if (aa[0][i] == aa[2][j + 1]) {
            cut(dp[nxt][0][j + 2] += dp[cur][1][j]);
          }
        }
      }
    }
    for (int j = 0; j < l; j++) {
      if (dp[cur][2][j]) {
        if (aa[0][i] == aa[3][j]) {
          cut(dp[nxt][2][j + 1] += dp[cur][2][j]);
          if (aa[1][i] == aa[3][j + 1]) {
            cut(dp[nxt][3][j + 2] += dp[cur][2][j]);
          }
        }
      }
    }
    for (int j = 0; j < l; j++) {
      if (dp[cur][3][j]) {
        if (aa[1][i] == aa[3][j]) {
          cut(dp[nxt][3][j + 1] += dp[cur][3][j]);
          if (aa[0][i] == aa[3][j + 1]) {
            cut(dp[nxt][2][j + 2] += dp[cur][3][j]);
          }
        }
      }
    }
  }
}
int main() {
  scanf("%s%s%s", aa[0], aa[1], aa[2]);
  n = strlen(aa[0]);
  l = strlen(aa[2]);
  xl = l >> 1;
  p[max(n, l)] = 1;
  for (int i = max(n, l) - 1; i >= 0; i--) {
    p[i] = p[i + 1] * 233;
  }
  strcpy(aa[3], aa[2]);
  std::reverse(aa[3], aa[3] + l);
  for (int i = 0; i < 4; i++) {
    gethashed(aa[i], h[i], max(n, l));
  }
  work();
  if (l == 1) {
    ans >>= 1;
  }
  if (ans == 0) {
    putchar('0');
  } else {
    if (ans < 0) {
      putchar('-');
      ans = -ans;
    }
    static int s[21];
    static int top = 0;
    while (ans) {
      s[top++] = ans % 10;
      ans /= 10;
    }
    while (top--) {
      putchar(s[top] + '0');
    }
  }
  return 0;
}