Hôm nay algorit đang đi dạo phố thì thấy một trò chơi ven đường như sau :

Cho hai xâu ký tự \(A\) và \(B\) chỉ bao gồm các chữ cái in hoa (từ '\(A\)' tới '\(Z\)'). Người ta muốn cắt xâu \(A\) ra thành các xâu khác rỗng sao cho mọi xâu nhận được sau khi cắt đều xuất hiện trong xâu \(B\).

Hai cách được xem là khác nhau nếu tồn tại vị trí cắt khác nhau trong hai cách.

• Yêu cầu : Hãy đếm số cách cắt thỏa mãn yêu cầu trên.

Input

• Hai dòng đầu chứa xâu \(A\) và \(B\).

Output

• Gồm một số nguyên duy nhất là đáp án của bài toán sau khi chia lấy chư cho \(10^9 + 7\).

Scoring

• Gọi \(f(X)\) là số lượng kí tự của xâu \(X\).
• Subtask \(1\) (\(20\%\) số điểm): \(f(A),f(B) \le 100\).
• Subtask \(2\) (\(20\%\) số điểm): \(f(A),f(B) \le 300\).
• Subtask \(3\) (\(20\%\) số điểm): \(f(A),f(B) \le 10^3\).
• Subtask \(4\) (\(20\%\) số điểm): \(f(A) \le 10^5 , f(B) \le 10^3\).
• Subtask \(5\) (\(20\%\) số điểm): *\(f(A),f(B) \le 3 * 10^5\).

Example

CAB
ABCZ

2

CBA
ABCC

1