{"code":"cutxau","name":"Cắt Xâu","description":"Hôm nay [user:algorit] đang đi dạo phố thì thấy một trò chơi ven đường như sau :\r\n\r\nCho 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$.\r\n\r\nHai 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.\r\n\r\n* **Yêu cầu** : *Hãy đếm số cách cắt thỏa mãn yêu cầu trên.*\r\n\r\n

Input

\r\n\r\n- Hai dòng đầu chứa xâu $A$ và $B$.\r\n\r\n

Output

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

Scoring

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

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n CAB\r\n ABCZ\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 2\r\n ```\r\n\r\n!!! question \"Test 2\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n CBA\r\n ABCC\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 1\r\n ```","points":700.0,"partial":true,"time_limit":2.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}