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:
import java.io.*;
import java.util.*;

/**
 * @auther chao
 */
public class CF2 {
    static int[][][] map;
    static int[][] tmap;
    static int n, m;
    static int[][] a;
    static int[] target;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
        int MOD = (int)1e9+7;

        String s = br.readLine();
        n = s.length();
        a = new int[2][n+2];
        for (int i = 1; i <= s.length(); i++) a[0][i] = s.charAt(i-1) - 'a' + 1;
        s = br.readLine();
        for (int i = 1; i <= s.length(); i++) a[1][i] = s.charAt(i-1) - 'a' + 1;
        br.readLine();

        s = br.readLine();
        m = s.length();
        target = new int[m+2];
        for (int i = 1; i <= s.length(); i++) target[i] = s.charAt(i-1) - 'a' + 1;


        map = new int[2][n+1][n+1];
        tmap = new int[m+1][m+1];

        // init
        for (int k = 0; k < 2; k++) initHash(a[k], map[k], n, MOD);
        initHash(target, tmap, m, MOD);

        // WA3 out of memory
        //dp[4][x][y][k] 已经匹配到target[k]且target[k]在snake部分
        long[][][][] dp = new long[4][2][n+2][2]; // dp[4][x][y][k]

        long ans = 0;
        int k2 = 1;
        int k1 = 0;
        if (m > 2) {
            // WA1: the priority of loop
            for (int k = 1; k <= m; k++) {
                k2 = 1^k2;
                k1 = 1^k1;
                for (int x = 0; x < 2; x++) {
                    for (int y = 1; y <= n; y++) {
                        // WA4 reset
                        for (int t = 0; t < 4; t++) dp[t][x][y][k2] = 0;
                        if (a[x][y] == target[k]) {
                            // WA2: the range of y
                            dp[0][x][y][k2] = (dp[0][x][y - 1][k1] + dp[1][x][y - 1][k1]) % MOD;
                            dp[1][x][y][k2] = dp[0][1 ^ x][y][k1];
                            dp[2][x][y][k2] = (dp[2][x][y + 1][k1] + dp[3][x][y + 1][k1]) % MOD;
                            dp[3][x][y][k2] = dp[2][1 ^ x][y][k1];
                            if (getMatchType(1 ^ x, y - 1, -1, 1, k - 1) >= 0) dp[0][x][y][k2]++;
                            if (getMatchType(1 ^ x, y + 1, 1, 1, k - 1) >= 0) dp[2][x][y][k2]++;

                            if (getMatchType(x, y + 1, 1, k + 1, m) >= 0)
                                ans = (ans + dp[0][x][y][k2] + dp[1][x][y][k2]) % MOD;
                            if (getMatchType(x, y - 1, -1, k + 1, m) >= 0)
                                ans = (ans + dp[2][x][y][k2] + dp[3][x][y][k2]) % MOD;
                        }
                    }
                }
            }
            for (int x = 0; x < 2; x++) {
                for (int y = 0; y <= n; y++) {
                    for (int k = 0; k <= m; k++) {
                        int l = getMatchType(x, y, -1, 1, k);
                        int r = getMatchType(1^x, y+1, 1, k+1, m);
                        if (l >=0 && r >= 0) ans++;
                        l = getMatchType(x, y+1, 1, 1, k);
                        r = getMatchType(1^x, y, -1, k+1, m);
                        if (l+r==2) ans++;
                    }
                }
            }
        }
        else {
            for (int x = 0; x < 2; x++) {
                for (int y = 1; y <= n; y++) {
                    ans = (ans+gao(x,y))%MOD;
                }
            }
        }
        System.out.println(ans%MOD);
    }
    private static int gao(int x, int y) {
        if (target[1] == a[x][y]) {
            if (m == 1) return 1;
            else {
                int cnt = 0;
                if (target[2] == a[x][y+1]) cnt++;
                if (target[2] == a[x][y-1]) cnt++;
                if (target[2] == a[1^x][y]) cnt++;
                return cnt;
            }
        }
        return 0;
    }
    private static int getMatchType(int x, int y, int d, int st, int ed) {
        if (ed-st+1 == 0) return 0;
        if (ed-st >= 3 && ((ed-st)&1) == 1) {
            int len = (ed - st + 1) / 2 - 1;
            int dlen = d*len;
            if (Math.min(y, y + dlen) >= 1 && Math.max(y, y + dlen) <= n && map[x][y][y + dlen] == tmap[st][st + len] && map[1 ^ x][y + dlen][y] == tmap[ed - len][ed]) {
                return 1;
            }
        }
        return -1;
        //(x,y)->(x,y+d*len)    (st -> st+len)
        //(1^x,y+d*len) ->(1^x, y)    (ed-len -> ed)
    }

    private static void initHash(int[] a, int[][] mp, int n, int MOD) {
        for (int i = 1; i <= n; i++) {
            long v = 0;
            for (int j = i; j <= n; j++) {
                v = (v*26+a[j])%MOD;
                mp[i][j] = (int)v;
            }
            v = 0;
            for (int j = i; j > 0; j--) {
                v = (v*26+a[j])%MOD;
                mp[i][j] = (int)v;
            }
        }
    }
}