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 = "MOD = 10 ** 9 + 7\ns, t = input(), input()\n\np = t + '#' + s\nz = [0] * len(p)\nl = r = 0\nfor i in range(1, len(p)):\n    if i <= r:\n        z[i] = min(r - i + 1, z[i - l])\n    while i + z[i] < len(p) and p[z[i]] == p[i + z[i]]:\n        z[i] += 1\n    if i + z[i] - 1 > r:\n        l, r = i, i + z[i] - 1\n\nf = [0] * (len(p) + 1)\nfsum = [0] * (len(p) + 1)\nfsum2 = [0] * (len(p) + 1)\nfor i in range(len(p) - 1, len(t), -1):\n    if z[i] == len(t):\n        f[i] = fsum2[i + z[i]] + len(p) - i - z[i] + 1\n    else:\n        f[i] = f[i + 1]\n    fsum[i] = (fsum[i + 1] + f[i]) % MOD\n    fsum2[i] = (fsum2[i + 1] + fsum[i]) % MOD\nprint(fsum[len(t) + 1])\n"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13791