Hamed has recently found a string t and suddenly became quite fond of it. He spent several days trying to find all occurrences of t in other strings he had. Finally he became tired and started thinking about the following problem. Given a string s how many ways are there to extract k ≥ 1 non-overlapping substrings from it such that each of them contains string t as a substring? More formally, you need to calculate the number of ways to choose two sequences a1, a2, ..., ak and b1, b2, ..., bk satisfying the following requirements:

  * k ≥ 1
  * <image>
  * <image>
  * <image>
  * <image> t is a substring of string saisai + 1... sbi (string s is considered as 1-indexed). 



As the number of ways can be rather large print it modulo 109 + 7.

Input

Input consists of two lines containing strings s and t (1 ≤ |s|, |t| ≤ 105). Each string consists of lowercase Latin letters.

Output

Print the answer in a single line.

Examples

Input

ababa
aba


Output

5


Input

welcometoroundtwohundredandeightytwo
d


Output

274201


Input

ddd
d


Output

12
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class ObsessiveString {
	private static final long MOD = 1000000007;

	private ObsessiveString() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		char[] s = br.readLine().toCharArray();
		char[] t = br.readLine().toCharArray();

		boolean[] tStart = zAlgorithm(s, t);
		int first = -1;
		for (int i = 0; i < tStart.length; i++) {
			if (tStart[i]) {
				first = i;
				break;
			}
		}
		if (first == -1) {
			System.out.println(0);
			return;
		}

		int[] last = new int[s.length + 1];
		long[] ways = new long[s.length + 1];
		long[] acc = new long[s.length + 1];

		last[first + t.length] = first + 1;
		ways[first + t.length] = first + 1;
		acc[first + t.length] = ways[first + t.length];

		for (int i = first + t.length + 1; i < ways.length; i++) {
			if (tStart[i - t.length]) {
				last[i] = i - t.length + 1;
			} else {
				last[i] = last[i-1];
			}
			
			ways[i] = ways[i - 1] + last[i] + acc[last[i]-1];
			ways[i] %= MOD;
			
			acc[i] = ways[i] + acc[i-1];
			acc[i] %= MOD;
		}

		System.out.println(ways[s.length]);
		
		//System.out.println(); 
		//System.out.println(Arrays.toString(last));
		//System.out.println(Arrays.toString(ways)); 
		//System.out.println(Arrays.toString(acc));
		 
	}

	boolean[] zAlgorithm(char[] text, char[] pattern) {
		char[] concat = new char[text.length + pattern.length + 1];
		System.arraycopy(pattern, 0, concat, 0, pattern.length);
		System.arraycopy(text, 0, concat, pattern.length + 1, text.length);
		concat[pattern.length] = '$';

		int[] zValues = zValues(concat);
		boolean[] patternStart = new boolean[text.length];
		for (int i = 0; i <= text.length - pattern.length; i++) {
			if (zValues[i + pattern.length + 1] == pattern.length) {
				patternStart[i] = true;
			}
		}

		return patternStart;
	}

	int[] zValues(char[] c) {
		int[] z = new int[c.length];
		int r = 0;
		int l = 0;

		for (int i = 1; i < c.length; i++) {
			if (i > r) {
				for (int j = i; j < c.length; j++) {
					if (c[j - i] == c[j]) {
						if (i == j) {
							l = i;
						}
						r = j;
					} else {
						break;
					}
				}
				if (r >= i) {
					z[i] = r - l + 1;
				}
			} else {
				if (z[i - l] < r - i + 1) {
					z[i] = z[i - l];
				} else {
					l = i;
					for (int j = r + 1; j < c.length; j++) {
						if (c[j - i] == c[j]) {
							r = j;
						} else {
							break;
						}
					}
					z[i] = r - l + 1;
				}
			}
		}

		return z;
	}

	public static void main(String[] args) throws IOException {
		new ObsessiveString();
	}
}
