Reference:: The Hobbit: The Desolation of Smaug

J. R. R. Tolkien decided to make Thorin Oakenshield’s task more difficult. This time he was given an infinite number of keys represented by a small string. The hidden entrance has a lot of keyholes side by side represented by one long string. The key fits only into a slit that matches it completely. Oakenshield does not know how many keys he would require and which all keyholes he will have to try out. So if there are n keyholes where the key fits, he might need any number of keys between 1 to n (both inclusive). Moreover he does not know which keyholes among the ones where the keys fit, he will have to use. All he knows is that there is a unique way to open the door. Trying out each configuration takes 1 second. The last light of Durin’s day does not last long and will have to try out all possibilities before it goes. He wants you to find out how long, in the worst case, it will take for him to try out all possibilities.

Since the answers may be huge, output it modulo 1000000007. If there are no keyholes where the key fits, output 0.

Input

First line containing a string representing the key. Second line containing a string representing the keyholes.

Output

Single line containing an integer for the required answer.

Notes

1. Key fits into a keyhole at index i if key is a substring of keyhole string at index i.
2. If there are two overlapping keyholes where the key may fit, you cannot insert a key in both simultaneously.

Constraints

1 ≤ key ≤ 10^4

1 ≤ keyholes ≤ 5*(10^5)

Sample

Input:
c
a

Output:
0

Input:
aba
abababa

Input:
4

Explanation:

Explanation for Test Case #1:
There is no slit where the key fits hence 0 seconds.

Explanation for Test Case #2:
The key fits into keyholes at positions {1, 3, 5}
If he requires only 1 key he may put them at {1} or {3} or {5} = 3 seconds.
If he required 2 keys, he may put them at {1, 5} = 1 second.
Total = 1+3 = 4 seconds.
He cannot use 3 keys without overlapping them.

Problem Setter: Vidit Gupta