Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Last week Penguin Charlie had a birthday. Chef presented him a string S.

Unfortunately, Charlie doesn't like string S, he likes string F. Charlie wants to create a few strings F from S by cutting. Cutting means getting some substrings from S that are equal to F and delete them from string S. After deleting a substring, the left and right parts of the resulting string remain separated. Note, a substring of a string S is a consecutive sequence of characters in S.

In some cases Charlie can still get substrings equal to F from the pieces that remain after cutting the original string. Your task is to calculate the number of ways to cut out at least one occurrence of the substring F in S. As this number may be too large, print it modulo 10^{9} + 7.

------ Input ------ 

Input begins with an integer T: the number of test cases.

Each test case consists of a two lines with two strings: S, F.

------ Output ------ 

For each test case, output a single line indicating the number of ways Charlie can cut at least one occurrence of F from S modulo 10^{9} + 7.

------ 
------ Constraints -----
$1 ≤ T ≤ 10 Subtask 1 : 10 points  
1 ≤ |F| ≤ |S| ≤ 100 

Subtask 2 : 30 points  
1 ≤ |F| ≤ |S| ≤ 5000 

Subtask 3 : 60 points
1 ≤ |F| ≤ |S| ≤ 300000 

----- Sample Input 1 ------ 
3
chefandcharliethebest
charliethebest
heknowsimeanityeahyouknowimeanityouknow
imeanit
aaaaa
aa
----- Sample Output 1 ------ 
1
3
7
----- explanation 1 ------ 

Example case 1.
chefand|charliethebest|
1 way to cut 1 string "charliethebest" from the string S:Example case 2.
heknows|imeanit|yeahyouknow|imeanit|youknow
2 ways to cut 1 string "imeanit" from the string S - take one of them
1 way to cut 2 strings "imeanit" from the string S - take both:Example case 3.
4 ways to cut 1 string "aa" from the string "aaaaa": |aa|aaa, a|aa|aa, aa|aa|a, aaa|aa|
3 ways to cut 2 strings "aa" from the string "aaaaa": |aa||aa|a, |aa|a|aa|, a|aa||aa|.

Difficulty: HARD
Tags: String algorithms

Dynamic programming

Data structures
Skill types: Dynamic programming

Data structures

Starter code:

Solutions:
M = 10 ** 9 + 7

def lps_compute(s):
	n = len(s)
	lps = [0] * n
	curr = 0
	lps[0] = 0
	i = 1
	while i < n:
		if s[i] == s[curr]:
			curr += 1
			lps[i] = curr
			i += 1
		elif curr != 0:
			curr = lps[curr - 1]
		else:
			lps[i] = 0
			i += 1
	return lps

def kmp(s1, s2):
	(n, m) = (len(s1), len(s2))
	lps = lps_compute(s2)
	ans = [0] * n
	(i, j) = (0, 0)
	while i < n:
		if s1[i] == s2[j]:
			i += 1
			j += 1
		elif j == 0:
			i += 1
		else:
			j = lps[j - 1]
		if j == m:
			ans[i - 1] = 1
			j = lps[j - 1]
	return ans
for _ in range(int(input())):
	s1 = input().strip()
	s2 = input().strip()
	(n, m) = (len(s1), len(s2))
	arr = kmp(s1, s2)
	dp = [0] * n
	if arr[0] == 1:
		dp[0] = 1
	for i in range(1, n):
		if arr[i] == 1:
			if i == m - 1:
				dp[i] = 1
			else:
				dp[i] = (1 + dp[i - m]) % M
		dp[i] = (dp[i - 1] + dp[i]) % M
	print(dp[-1])


def KnuthMorrisPratt(text, pattern):
	pattern = list(pattern)
	shifts = [1] * (len(pattern) + 1)
	shift = 1
	for pos in range(len(pattern)):
		while shift <= pos and pattern[pos] != pattern[pos - shift]:
			shift += shifts[pos - shift]
		shifts[pos + 1] = shift
	ans = [0] * len(text)
	startPos = 0
	matchLen = 0
	for c in text:
		while matchLen == len(pattern) or (matchLen >= 0 and pattern[matchLen] != c):
			startPos += shifts[matchLen]
			matchLen -= shifts[matchLen]
		matchLen += 1
		if matchLen == len(pattern):
			ans[startPos] = 1
	return ans

def KMPSearch(pat, txt):
	M = len(pat)
	N = len(txt)
	ans = [0] * (N + 1)
	lps = [0] * M
	j = 0
	computeLPSArray(pat, M, lps)
	i = 0
	while i < N:
		if pat[j] == txt[i]:
			i += 1
			j += 1
		if j == M:
			ans[i - j + M] = 1
			j = lps[j - 1]
		elif i < N and pat[j] != txt[i]:
			if j != 0:
				j = lps[j - 1]
			else:
				i += 1
	return ans

def computeLPSArray(pat, M, lps):
	len = 0
	lps[0]
	i = 1
	while i < M:
		if pat[i] == pat[len]:
			len += 1
			lps[i] = len
			i += 1
		elif len != 0:
			len = lps[len - 1]
		else:
			lps[i] = 0
			i += 1
MOD = 10 ** 9 + 7
for _ in range(int(input())):
	s = input().strip()
	f = input().strip()
	(n, m) = (len(s), len(f))
	arr = KMPSearch(f, s)
	dp = [0] * (n + 1)
	dp[0] = 1
	for i in range(1, n + 1):
		if arr[i] == 1:
			dp[i] = (dp[i] + dp[i - m]) % MOD
		dp[i] = (dp[i] + dp[i - 1]) % MOD
	print((dp[n] - 1 + MOD) % MOD)


import re
from collections import Counter
M = int(1000000000.0) + 7

def brute(S, F, st):
	st0 = st
	tot = 0
	while True:
		p = S.find(F, st)
		if p == -1:
			break
		tot += brute(S, F, p + len(F)) + 1
		st = p + 1
	return tot % M
for t in range(int(input())):
	S = input().strip()
	F = input().strip()
	m = len(F)
	(mc, cnt) = Counter(F).most_common(1)[0]
	if m > 1 and cnt == m:
		ans = 0
		subs = [len(match.group()) for match in re.finditer('({0})\\1*'.format(mc), S) if len(match.group()) >= m]
		if subs:
			dpsum = [i + 1 for i in range(max(subs) + 1)]
			for n in range(m, len(dpsum)):
				dpsum[n] = (1 + dpsum[n - m] + dpsum[n - 1]) % M
			ans = 1
			for n in subs:
				v = dpsum[n] - dpsum[n - 1] + M
				ans = ans * v % M
			ans -= 1
	elif len(S) <= 30:
		ans = brute(S, F, 0)
	else:
		ans = (pow(2, S.count(F), M) - 1 + M) % M
	print(ans)