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

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