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: competition

Starter code:

Solutions:
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])

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, t = input(), input()
n, m = len(t), len(s) + 1
h = t + ' ' + s

d = 1000000007
s = [1] * m

f = 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 = (f + s[k - n]) % d
        s[j] += (s[j - 1] + f) % d

print(f)

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(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(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(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(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(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(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(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(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(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)




# Made By Mostafa_Khaled


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)

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])