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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 's, t = input(), input()\nn, m = len(t), len(s)\n\nd = 10 ** 9 + 7\n\np = [0] * (n + 1)\ni, j = 0, 1\nwhile j < n:\n    if t[i] == t[j]:\n        j += 1\n        i += 1\n        p[j] = i\n    elif i: i = p[i]\n    else: j += 1\n\ni = j = 0\nf = [0] * (m + 1)\nwhile j < m:\n    if t[i] == s[j]:\n        i += 1\n        j += 1\n        if i == n:\n            i = p[i]\n            f[j - n] = 1\n    elif i: i = p[i]\n    else: j += 1\n\ns = [0] * (m + 1)\nk = m\nfor j in range(m - 1, -1, -1):\n    if f[j]: k = j\n    if k < m:\n        f[j] = (f[j + 1] + s[k + n] + m - k - n + 1) % d\n        s[j] = (s[j + 1] + f[j]) % d\n\nprint(f[0])'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13403