Cắt Xâu

Xem PDF




Tác giả:
Dạng bài
Điểm: 700 (p) Thời gian: 2.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

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\)\(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\)\(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

Test 1

Input
CAB
ABCZ
Output
2

Test 2

Input
CBA
ABCC
Output
1

Bình luận