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 MOD = 1e9 + 7, bas = 1e6 + 7, N = 2005;
char s[2][N], t[N];
int n, m, ans, h1[2][N], h2[2][N], h3[N], mi[N], f[2][N][N], g[2][N][N];
int main() {
  scanf("%s%s%s", s[0] + 1, s[1] + 1, t + 1);
  n = strlen(s[0] + 1);
  m = strlen(t + 1);
  if (m == 1) {
    for (int i = 1; i <= n; i++) ans += (s[0][i] == t[1]) + (s[1][i] == t[1]);
    printf("%d", ans);
    return 0;
  }
  if (m == 2) {
    for (int i = 1; i <= n; i++) {
      if (s[0][i] == t[1])
        ans +=
            (s[1][i] == t[2]) + (s[0][i + 1] == t[2]) + (s[0][i - 1] == t[2]);
      if (s[1][i] == t[1])
        ans +=
            (s[0][i] == t[2]) + (s[1][i + 1] == t[2]) + (s[1][i - 1] == t[2]);
    }
    printf("%d", ans);
    return 0;
  }
  mi[0] = 1;
  for (int i = 1; i <= max(n, m); i++) mi[i] = 1ll * mi[i - 1] * bas % MOD;
  for (int i = 1; i <= n; i++) {
    h1[0][i] = (0ll + 1ll * h1[0][i - 1] * bas + s[0][i] - 'a' + 1) % MOD;
    h1[1][i] = (0ll + 1ll * h1[1][i - 1] * bas + s[1][i] - 'a' + 1) % MOD;
  }
  for (int i = n; i >= 1; i--) {
    h2[0][i] = (0ll + 1ll * h2[0][i + 1] * bas + s[0][i] - 'a' + 1) % MOD;
    h2[1][i] = (0ll + 1ll * h2[1][i + 1] * bas + s[1][i] - 'a' + 1) % MOD;
  }
  for (int i = 1; i <= m; i++)
    h3[i] = (0ll + 1ll * h3[i - 1] * bas + t[i] - 'a' + 1) % MOD;
  for (int i = 1; i <= n; i++) {
    for (int j = 2; j <= m / 2; j++) {
      int k = i - j + 1;
      if (k < 1) break;
      int op1 = (0ll + h2[0][k] - 1ll * h2[0][i + 1] * mi[j] % MOD + MOD) % MOD;
      int op2 = (0ll + h1[1][i] - 1ll * h1[1][k - 1] * mi[j] % MOD + MOD) % MOD;
      int sum1 = (0ll + 1ll * op1 * mi[j] + op2) % MOD;
      if (sum1 == h3[j * 2] && j * 2 != m) f[1][i][j * 2] = 1;
      int op3 = (0ll + h1[0][i] - 1ll * h1[0][k - 1] * mi[j] % MOD + MOD) % MOD;
      int op4 = (0ll + h2[1][k] - 1ll * h2[1][i + 1] * mi[j] % MOD + MOD) % MOD;
      int sum2 = (0ll + 1ll * op4 * mi[j] + op3) % MOD;
      if (sum2 == h3[j * 2] && j * 2 != m) f[0][i][j * 2] = 1;
    }
  }
  for (int i = n; i >= 1; i--) {
    for (int j = 2; j <= m / 2; j++) {
      int k = i + j - 1;
      if (k > n) break;
      int sum =
          (0ll + h3[m] - 1ll * h3[m - j * 2] * mi[j * 2] % MOD + MOD) % MOD;
      int op1 = (0ll + h1[0][k] - 1ll * h1[0][i - 1] * mi[j] % MOD + MOD) % MOD;
      int op2 = (0ll + h2[1][i] - 1ll * h2[1][k + 1] * mi[j] % MOD + MOD) % MOD;
      int sum1 = (0ll + 1ll * op1 * mi[j] + op2) % MOD;
      if (sum1 == sum && j * 2 != m) g[0][i][m - j * 2 + 1] = 1;
      int op3 = (0ll + h1[1][k] - 1ll * h1[1][i - 1] * mi[j] % MOD + MOD) % MOD;
      int op4 = (0ll + h2[0][i] - 1ll * h2[0][k + 1] * mi[j] % MOD + MOD) % MOD;
      int sum2 = (0ll + 1ll * op3 * mi[j] + op4) % MOD;
      if (sum2 == sum && j * 2 != m) g[1][i][m - j * 2 + 1] = 1;
    }
  }
  for (int i = 0; i <= n + 1; i++) f[0][i][0] = f[1][i][0] = 1;
  for (int i = 0; i <= n + 1; i++) g[0][i][m + 1] = g[1][i][m + 1] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (s[0][i] == t[j]) {
        f[0][i][j] = (0ll + f[0][i][j] + f[0][i - 1][j - 1]) % MOD;
        if (j >= 2 && s[1][i] == t[j - 1])
          f[0][i][j] = (0ll + f[0][i][j] + f[1][i - 1][j - 2]) % MOD;
      }
      if (s[1][i] == t[j]) {
        f[1][i][j] = (0ll + f[1][i][j] + f[1][i - 1][j - 1]) % MOD;
        if (j >= 2 && s[0][i] == t[j - 1])
          f[1][i][j] = (0ll + f[1][i][j] + f[0][i - 1][j - 2]) % MOD;
      }
    }
    for (int j = 0; j <= m; j++)
      ans = (0ll + ans + 1ll * f[0][i][j] * g[0][i + 1][j + 1] +
             1ll * f[1][i][j] * g[1][i + 1][j + 1]) %
            MOD;
  }
  for (int i = 1; i <= m; i++)
    if (i <= (m - i + 1)) swap(t[i], t[m - i + 1]);
  memset(f, 0, sizeof(f));
  memset(g, 0, sizeof(g));
  for (int i = 1; i <= m; i++)
    h3[i] = (0ll + 1ll * h3[i - 1] * bas + t[i] - 'a' + 1) % MOD;
  for (int i = 1; i <= n; i++) {
    for (int j = 2; j <= m / 2; j++) {
      int k = i - j + 1;
      if (k < 1) break;
      int op1 = (0ll + h2[0][k] - 1ll * h2[0][i + 1] * mi[j] % MOD + MOD) % MOD;
      int op2 = (0ll + h1[1][i] - 1ll * h1[1][k - 1] * mi[j] % MOD + MOD) % MOD;
      int sum1 = (0ll + 1ll * op1 * mi[j] + op2) % MOD;
      if (sum1 == h3[j * 2])
        if (j * 2 != m)
          f[1][i][j * 2] = 1;
        else
          ans = (++ans) % MOD;
      int op3 = (0ll + h1[0][i] - 1ll * h1[0][k - 1] * mi[j] % MOD + MOD) % MOD;
      int op4 = (0ll + h2[1][k] - 1ll * h2[1][i + 1] * mi[j] % MOD + MOD) % MOD;
      int sum2 = (0ll + 1ll * op4 * mi[j] + op3) % MOD;
      if (sum2 == h3[j * 2])
        if (j * 2 != m)
          f[0][i][j * 2] = 1;
        else
          ans = (++ans) % MOD;
    }
  }
  for (int i = n; i >= 1; i--) {
    for (int j = 2; j <= m / 2; j++) {
      int k = i + j - 1;
      if (k > n) break;
      int sum =
          (0ll + h3[m] - 1ll * h3[m - j * 2] * mi[j * 2] % MOD + MOD) % MOD;
      int op1 = (0ll + h1[0][k] - 1ll * h1[0][i - 1] * mi[j] % MOD + MOD) % MOD;
      int op2 = (0ll + h2[1][i] - 1ll * h2[1][k + 1] * mi[j] % MOD + MOD) % MOD;
      int sum1 = (0ll + 1ll * op1 * mi[j] + op2) % MOD;
      if (sum1 == sum)
        if (j * 2 != m)
          g[0][i][m - j * 2 + 1] = 1;
        else
          ans = (++ans) % MOD;
      int op3 = (0ll + h1[1][k] - 1ll * h1[1][i - 1] * mi[j] % MOD + MOD) % MOD;
      int op4 = (0ll + h2[0][i] - 1ll * h2[0][k + 1] * mi[j] % MOD + MOD) % MOD;
      int sum2 = (0ll + 1ll * op3 * mi[j] + op4) % MOD;
      if (sum2 == sum)
        if (j * 2 != m)
          g[1][i][m - j * 2 + 1] = 1;
        else
          ans = (++ans) % MOD;
    }
  }
  for (int i = 0; i <= n + 1; i++) f[0][i][0] = f[1][i][0] = 1;
  for (int i = 0; i <= n + 1; i++) g[0][i][m + 1] = g[1][i][m + 1] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (s[0][i] == t[j]) {
        f[0][i][j] = (0ll + f[0][i][j] + f[0][i - 1][j - 1]) % MOD;
        if (j >= 2 && s[1][i] == t[j - 1])
          f[0][i][j] = (0ll + f[0][i][j] + f[1][i - 1][j - 2]) % MOD;
      }
      if (s[1][i] == t[j]) {
        f[1][i][j] = (0ll + f[1][i][j] + f[1][i - 1][j - 1]) % MOD;
        if (j >= 2 && s[0][i] == t[j - 1])
          f[1][i][j] = (0ll + f[1][i][j] + f[0][i - 1][j - 2]) % MOD;
      }
    }
    for (int j = 0; j <= m; j++)
      ans = (0ll + ans + 1ll * f[0][i][j] * g[0][i + 1][j + 1] +
             1ll * f[1][i][j] * g[1][i + 1][j + 1]) %
            MOD;
  }
  printf("%d", ans);
  return 0;
}