Cho 2 xâu ~S~ và ~T~. Ta định nghĩa xâu con của ~S~ là xâu con gồm các kí tự liên tiếp trong ~S~. Gọi ~p~ là số xâu con không gối lên nhau lớn nhất có thể lấy được từ xâu ~S~ sao cho các xâu con này đều bằng ~T~. Ví dụ ta có xâu ~S = “aaaaa”~, ~T = “aa”~, khi đó ~p = 2~.

Ta định nghĩa hàm ~C(k)~ là số cách cắt từ xâu ~S~ ra ~k~ xâu con không gối lên nhau sao cho các xâu con này đều bằng ~T~. Trong ví dụ trên ta có: ~C(1) = 4~: |aa|aaa, a|aa|aa, aa|aa|a, aaa|aa| ~C(2) = 3~: |aa||aa|a, |aa|a|aa|, a|aa||aa|

Hãy tính ~C(1) + C(2) + \dots + C(p)~.

Yêu cầu: Tính tổng số cách chọn ~k~ xâu con không gối lên nhau bằng ~T~ với mọi ~k~ từ 1 đến ~p~.

Input

• Dòng đầu tiên chứa xâu ~S~ (~1 \le |S| \le 3 \times 10^5~).
• Dòng thứ hai chứa xâu ~T~ (~1 \le |T| \le |S|~).

Output

• Ghi ra một dòng duy nhất là kết quả của bài toán. Do kết quả có thể rất lớn nên bạn cần ghi ra phần dư trong phép chia kết quả cho ~10^9 + 7~.

Sample Input 1

heknowsimeanityeahyouknowimeanityouknow
imeanit

Sample Output 1

3

Sample Input 2

aaaaa
aa

Sample Output 2

7