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;
        int MOD2 = MOD*2;

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

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


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

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

        // WA3 out of memory
        long[][][][] dp = new long[4][2][n][2]; // dp[4][x][y][k]
        //dp[x][y][k] 已经匹配到target[k]且target[k]在snake部分
        //dp[x][y][k] = dp[x][y-1][k-1] + dp[1^x][y][k-1] + (x, y-1) is head
        // if (remaining part is tail) ans+= dp[x][y][k]
        // if (remaining part is tail and pre-part is head) ans++

        long ans = 0;
        int k2 = 1;
        int k1 = 0;
        if (m > 2) {
            // WA1: the priority of loop
            for (int k = 0; k < m; k++) {
                k2 = 1^k2;
                k1 = 1^k1;
                for (int x = 0; x < 2; x++) {
                    for (int y = 0; y < n; y++) {
                        dp[0][x][y][k2] = 0;
                        dp[1][x][y][k2] = 0;
                        dp[2][x][y][k2] = 0;
                        dp[3][x][y][k2] = 0;
                        if (a[x][y] == target[k]) {
                            // 0 往右第一  1 往右该列第二  2 往左第一 3 往左第二
                            /*
                            if (k > 0) {
                                dp[1][x][y][k] = dp[0][1 ^ x][y][k - 1];
                                if (y > 0) dp[0][x][y][k] = (dp[0][x][y - 1][k - 1] + dp[1][x][y - 1][k - 1]) % MOD;
                                dp[3][x][y][k] = dp[2][1 ^ x][y][k - 1];
                                // WA2: the range of y
                                if (y < n - 1) dp[2][x][y][k] = (dp[2][x][y + 1][k - 1] + dp[3][x][y + 1][k - 1]) % MOD;
                            }
                            if (getMatchType(1 ^ x, y - 1, -1, 0, k - 1) >= 0) dp[0][x][y][k]++;
                            if (getMatchType(1 ^ x, y + 1, 1, 0, k - 1) >= 0) dp[2][x][y][k]++;

                            if (getMatchType(x, y + 1, 1, k + 1, m - 1) >= 0)
                                ans = (ans + dp[0][x][y][k] + dp[1][x][y][k]) % MOD;
                            if (getMatchType(x, y - 1, -1, k + 1, m - 1) >= 0)
                                ans = (ans + dp[2][x][y][k] + dp[3][x][y][k]) % MOD;
                                */
                            dp[0][x][y][k2] = 0;
                            dp[1][x][y][k2] = 0;
                            dp[2][x][y][k2] = 0;
                            dp[3][x][y][k2] = 0;
                            if (k > 0) {
                                dp[1][x][y][k2] = dp[0][1 ^ x][y][k1];
                                if (y > 0) dp[0][x][y][k2] = (dp[0][x][y - 1][k1] + dp[1][x][y - 1][k1]) % MOD;
                                dp[3][x][y][k2] = dp[2][1 ^ x][y][k1];
                                // WA2: the range of y
                                if (y < n - 1) dp[2][x][y][k2] = (dp[2][x][y + 1][k1] + dp[3][x][y + 1][k1]) % MOD;
                            }
                            if (getMatchType(1 ^ x, y - 1, -1, 0, k - 1) >= 0) dp[0][x][y][k2]++;
                            if (getMatchType(1 ^ x, y + 1, 1, 0, k - 1) >= 0) dp[2][x][y][k2]++;

                            if (getMatchType(x, y + 1, 1, k + 1, m - 1) >= 0)
                                ans = (ans + dp[0][x][y][k2] + dp[1][x][y][k2]) % MOD;
                            if (getMatchType(x, y - 1, -1, k + 1, m - 1) >= 0)
                                ans = (ans + dp[2][x][y][k2] + dp[3][x][y][k2]) % MOD;
                        }
                    }
                }
            }
            for (int x = 0; x < 2; x++) {
                for (int y = -1; y < n; y++) {
                    for (int k = -1; k < m; k++) {
                        int l = getMatchType(x, y, -1, 0, k);
                        int r = getMatchType(1^x, y+1, 1, k+1, m-1);
                        if (l >=0 && r >= 0) ans++;
                        l = getMatchType(x, y+1, 1, 0, k);
                        r = getMatchType(1^x, y, -1, k+1, m-1);
                        if (l+r==2) ans++;
                    }
                }
            }
        }
        else {
            for (int x = 0; x < 2; x++) {
                for (int y = 0; y < n; y++) {
                    ans = (ans+gao(x,y))%MOD;
                }
            }
        }
        System.out.println(ans%MOD);
    }
    private static int gao(int x, int y) {
        if (target[0] == a[x][y]) {
            if (m == 1) return 1;
            else {
                int cnt = 0;
                if (y+1<n && target[1] == a[x][y+1]) cnt++;
                if (y-1>=0 && target[1] == a[x][y-1]) cnt++;
                if (target[1] == 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) >= 0 && 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 = 0; 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;
            }
        }
    }
}