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 a_1, a_2, ..., a_{k} and b_1, b_2, ..., b_{k} satisfying the following requirements:

  k ≥ 1  $\forall i(1 \leq i \leq k) 1 \leq a_{i}, b_{i} \leq|s|$  $\forall i(1 \leq i \leq k) b_{i} \geq a_{i}$  $\forall i(2 \leq i \leq k) a_{i} > b_{i - 1}$  $\forall i(1 \leq i \leq k)$  t is a substring of string s_{a}_{i}s_{a}_{i} + 1... s_{b}_{i} (string s is considered as 1-indexed). 

As the number of ways can be rather large print it modulo 10^9 + 7.


-----Input-----

Input consists of two lines containing strings s and t (1 ≤ |s|, |t| ≤ 10^5). 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

Difficulty: HARD
Tags: String algorithms

Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
(s, t) = (input(), input())
(n, m) = (len(t), len(s) + 1)
d = 1000000007
g = [1] * m
f = k = 0
for i in range(1, m):
	if s[i - n:i] == t:
		k = i
	if k:
		f = (f + g[k - n]) % d
	g[i] += (g[i - 1] + f) % d
print(f)


(s, t) = (input(), input())
(n, m) = (len(s), len(t))
t = '$'.join((t, s))
p = [0]
k = 0
for i in range(1, n + m + 1):
	while k and t[k] != t[i]:
		k = p[k - 1]
	if t[k] == t[i]:
		k += 1
	p.append(k)
ans = [0] * n
sums = [0] * (n + 1)
curs = 0
was = False
j = 0
mod = 1000000007
for i in range(n):
	if p[i + m + 1] == m:
		if not was:
			was = True
			curs = 1
		while j <= i - m:
			curs = (curs + sums[j] + 1) % mod
			j += 1
	ans[i] = curs
	sums[i] = (sums[i - 1] + ans[i]) % mod
print(sum(ans) % mod)


(s, t) = (input(), input())
(n, m) = (len(t), len(s) + 1)
h = t + ' ' + s
d = 1000000007
f = [0] * m
s = [1] * m
i = k = 0
p = [-1] + [0] * len(h)
for j in range(1, n + m):
	while i + 1 and h[i] != h[j]:
		i = p[i]
	i += 1
	p[j + 1] = i
	if j > n:
		j -= n
		if i == n:
			k = j
		if k:
			f[j] = (f[j - 1] + s[k - n]) % d
		s[j] += (s[j - 1] + f[j]) % d
print(f[-1])


s = input()
t = input()
n = len(s)
m = len(t)
t = t + '$' + s
p = [0] * (n + m + 1)
k = 0
for i in range(1, n + m + 1):
	while k > 0 and t[k] != t[i]:
		k = p[k - 1]
	if t[k] == t[i]:
		k += 1
	p[i] = k
ans = [0] * n
sums = [0] * (n + 1)
curs = 0
was = False
j = 0
MOD = 10 ** 9 + 7
for i in range(n):
	if p[i + m + 1] == m:
		if not was:
			was = True
			curs = 1
		while j <= i - m:
			curs = (curs + sums[j] + 1) % MOD
			j += 1
	ans[i] = curs
	sums[i] = (sums[i - 1] + ans[i]) % MOD
print(sum(ans) % MOD)


(s, t) = (input(), input())
(n, m) = (len(t), len(s))
d = 10 ** 9 + 7
p = [0] * (n + 1)
(i, j) = (0, 1)
while j < n:
	if t[i] == t[j]:
		j += 1
		i += 1
		p[j] = i
	elif i:
		i = p[i]
	else:
		j += 1
i = j = 0
f = [0] * (m + 1)
while j < m:
	if t[i] == s[j]:
		i += 1
		j += 1
		if i == n:
			i = p[i]
			f[j - n] = 1
	elif i:
		i = p[i]
	else:
		j += 1
s = [0] * (m + 1)
k = m
for j in range(m - 1, -1, -1):
	if f[j]:
		k = j
	if k < m:
		f[j] = (f[j + 1] + s[k + n] + m - k - n + 1) % d
		s[j] = (s[j + 1] + f[j]) % d
print(f[0])


MOD = 10 ** 9 + 7
(s, t) = (input(), input())
p = t + '#' + s
z = [0] * len(p)
l = r = 0
for i in range(1, len(p)):
	if i <= r:
		z[i] = min(r - i + 1, z[i - l])
	while i + z[i] < len(p) and p[z[i]] == p[i + z[i]]:
		z[i] += 1
	if i + z[i] - 1 > r:
		(l, r) = (i, i + z[i] - 1)
f = [0] * (len(p) + 1)
fsum = [0] * (len(p) + 1)
fsum2 = [0] * (len(p) + 1)
for i in range(len(p) - 1, len(t), -1):
	if z[i] == len(t):
		f[i] = fsum2[i + z[i]] + len(p) - i - z[i] + 1
	else:
		f[i] = f[i + 1]
	fsum[i] = (fsum[i + 1] + f[i]) % MOD
	fsum2[i] = (fsum2[i + 1] + fsum[i]) % MOD
print(fsum[len(t) + 1])