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 JAVA):

Solution:
//package codeforces.cfr339div1;

import java.util.Scanner;

/**
 * Created by raggzy on 4/21/2016.
 */
public class E {
    private static final int MOD = 1000000000 + 7;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        char[][] words = new char[2][];
        words[0] = in.nextLine().toCharArray();
        words[1] = in.nextLine().toCharArray();
        int n = words[0].length;
        in.nextLine();
        char[] target = in.nextLine().toCharArray();
        int m = target.length;
        //
        int[][][] lMatch = new int[2][n][m];
        int[][][] rMatch = new int[2][n][m];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < n; j++) {
                for (int c = m - 1; c >= 0; c--) {
                    if (words[i][j] == target[c]) {
                        lMatch[i][j][c] = 1 + (j - 1 >= 0 && c + 1 < m ? lMatch[i][j - 1][c + 1] : 0);
                    }
                }
            }
        }
        for (int i = 0; i < 2; i++) {
            for (int j = n - 1; j >= 0; j--) {
                for (int c = m - 1; c >= 0; c--) {
                    if (words[i][j] == target[c]) {
                        rMatch[i][j][c] = 1 + (j + 1 < n && c + 1 < m ? rMatch[i][j + 1][c + 1] : 0);
                    }
                }
            }
        }
        //
        int[][][] l = new int[2][n][m];
        int[][][] r = new int[2][n][m];
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < 2; i++) {
                for (int c = m - 1; c >= 0; c--) {
                    int left = m - c;
                    // corner case the end
                    if (left == 1 && words[i][j] == target[c]) {
                        l[i][j][c]++;
                        l[i][j][c] %= MOD;
                    }
                    // corner case exact left arc
                    if (left % 2 == 0 && lMatch[i][j][c] >= left / 2 && j - left / 2 + 1 >= 0 && rMatch[1 - i][j - left / 2 + 1][c + left / 2] == left / 2) {
                        l[i][j][c]++;
                        l[i][j][c] %= MOD;
                    }
                    // going left or switch
                    if (words[i][j] == target[c] && j - 1 >= 0 && c + 1 < m) {
                        l[i][j][c] += l[i][j - 1][c + 1];
                        l[i][j][c] %= MOD;
                        if (words[1 - i][j] == target[c + 1] && c + 2 < m) {
                            l[i][j][c] += l[1 - i][j - 1][c + 2];
                            l[i][j][c] %= MOD;
                        }
                    }
                }
            }
        }
        for (int j = n - 1; j >= 0; j--) {
            for (int i = 0; i < 2; i++) {
                for (int c = m - 1; c >= 0; c--) {
                    int left = m - c;
                    // corner case the end
                    if (left == 1 && words[i][j] == target[c]) {
                        r[i][j][c]++;
                        r[i][j][c] %= MOD;
                    }
                    // corner case exact right arc
                    if (left % 2 == 0 && rMatch[i][j][c] >= left / 2 && j + left / 2 - 1 < n && lMatch[1 - i][j + left / 2 - 1][c + left / 2] == left / 2) {
                        r[i][j][c]++;
                        r[i][j][c] %= MOD;
                    }
                    // going right or switch
                    if (words[i][j] == target[c] && j + 1 < n && c + 1 < m) {
                        r[i][j][c] += r[i][j + 1][c + 1];
                        r[i][j][c] %= MOD;
                        if (words[1 - i][j] == target[c + 1] && c + 2 < m) {
                            r[i][j][c] += r[1 - i][j + 1][c + 2];
                            r[i][j][c] %= MOD;
                        }
                    }
                }
            }
        }
        //
        int[][] f = new int[2][n];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < n; j++) {
                // checking right-left only
                if (words[i][j] == target[0]) {
                    if (j + 1 < n && 1 < m) {
                        f[i][j] += r[i][j + 1][1];
                        f[i][j] %= MOD;
                    }
                    if (j - 1 >= 0 && 1 < m) {
                        f[i][j] += l[i][j - 1][1];
                        f[i][j] %= MOD;
                    }
                    // left arc + right continuation
                    for (int e = 1; e <= lMatch[i][j][0]; e++) {
                        if (2 * e < m && rMatch[1 - i][j - e + 1][e] >= e && j + 1 < n) {
                            f[i][j] += r[1 - i][j + 1][2 * e];
                            f[i][j] %= MOD;
                        }
                    }
                    // right arc + left continuation
                    for (int e = 1; e <= rMatch[i][j][0]; e++) {
                        if (2 * e < m && lMatch[1 - i][j + e - 1][e] >= e && j - 1 >= 0) {
                            f[i][j] += l[1 - i][j - 1][2 * e];
                            f[i][j] %= MOD;
                        }
                    }
                    // corner cases - exact left arc, but not switch
                    if (m > 2 && m % 2 == 0 && j - m / 2 + 1 >= 0 && lMatch[i][j][0] >= m / 2 && rMatch[1 - i][j - m / 2 + 1][m / 2] == m / 2) {
                        f[i][j]++;
                    }
                    // corner cases - exact right arc, but not switch
                    if (m > 2 && m % 2 == 0 && j + m / 2 - 1 < n && rMatch[i][j][0] >= m / 2 && lMatch[1 - i][j + m / 2 - 1][m / 2] == m / 2) {
                        f[i][j]++;
                    }
                    // switch
                    if (m == 2 && words[1 - i][j] == target[1]) {
                        f[i][j]++;
                    }
                    // single symbol
                    if (m == 1) {
                        f[i][j]++;
                    }
                    f[i][j] %= MOD;
                }
            }
        }
        //
        int res = 0;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < n; j++) {
                res += f[i][j];
                res %= MOD;
            }
        }

        System.out.println(res);
    }
}