Mật khẩu

Điểm: 4,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Java, Javascript, Kotlin, Pascal, Python, Scratch

Do dịch Covid-19, hai bạn Hồng và Chi không được đi học và gặp nhau nhưng hai bạn vẫn thường xuyên nhắn tin cho nhau. Một lần, Hồng muốn gửi mật khẩu tham gia lớp học online cho Chi nhưng không muốn em Phúc tò mò và biết được. Theo ý tưởng giấu tin trong ảnh, Hồng quyết định sẽ giấu mật khẩu vào trong đoạn văn bản gửi cho Chi. Cụ thể, với một văn bản mà Hồng gửi cho Chi được biểu diễn bằng xâu ký tự $T = t_{1} t_{2} \dots t_{n}$ (gồm $n$ ký tự, mỗi ký tự thuộc $^{'} a^{'}$ đến $^{'} z^{'}$ ) và dãy số nguyên $a_{1}, a_{2}, \dots, a_{m}$ ( $1 \leq a_{1} < a_{2} < \dots < a_{m} \leq n$ ) là dãy số mà hai bạn đã thống nhất thì mật khẩu là một xâu $P = t_{a_{1}} t_{a_{2}} \dots t_{a_{m}}$ , là xâu độ dài $m$ nhận được bằng cách ghép lần lượt các ký tự ở các vị trí $a_{1}, a_{2}, \dots, a_{m}$ . Ví dụ, $T =^{'} m i s s y o u u u^{'}$ và dãy số $a_{1} = 2, a_{2} = 3, a_{3} = 5, a_{4} = 6, a_{5} = 8$ thì mật khẩu $P = " i s y o u "$ .

Hồng nhanh chóng nhận ra rằng, với một xâu $T$ và mật khẩu $P$ sẽ tồn tại nhiều dãy số để xác định mật khẩu. Ví dụ, một dãy số khác $a_{1} = 2, a_{2} = 4, a_{3} = 5, a_{4} = 6, a_{5} = 7$ cũng xác định được mật khẩu $P = " i s y o u "$ trong xâu $T =^{'} m i s s y o u u u^{'}$ .

Trong quá trình gửi, xâu $T$ sẽ được mã hóa theo phương thức RLE (Run Length Encoding). Nghĩa là, một xâu $T$ chỉ gồm các ký tự $^{'} a^{'}$ đến $^{'} z^{'}$ được mã hóa thành xâu $T_{E}$ (chỉ gồm các ký tự $^{'} a^{'}$ đến $^{'} z^{'}$ và ký tự $^{'} 0^{'}$ đến $^{'} 9^{'}$ ) bằng cách đi từ trái sang phải, mã hóa dãy các ký tự liên tiếp giống nhau trong $T$ thành ký tự đại diện và số lượng.

Ví dụ, xâu $T =^{'} m i s s y o u u u u u u u u^{'}$ thì $T_{E} =^{'} m 1 i 1 s 2 y 1 o 1 u 10^{'}$ .

Yêu cầu: Cho xâu $T_{E}$ (là mã hóa của xâu $T$ ) và xâu mật khẩu $P$ , gọi $R$ là số lượng dãy số khác nhau có thể xác định được mật khẩu $P$ trong xâu $T$ . Hãy tính $R$ chia dư cho $10^{9} + 7$ .

Dữ liệu vào

Dòng đầu chứa hai số nguyên dương $n, m$ .
Dòng thứ hai chứa một xâu là mã hóa của xâu $T$ .
Dòng thứ ba chứa một xâu là xâu $P$ .

Dữ liệu ra

Ghi một số nguyên duy nhất là số $R$ chia dư cho $10^{9} + 7$ .

Ràng buộc

Có $20 %$ số lượng test ứng với $20 %$ số điểm thỏa mãn điều kiện: $n \leq 20, m = 1$ .
Có $20 %$ số lượng test khác ứng với $20 %$ số điểm thỏa mãn điều kiện: $n \leq 20, m < n$ .
Có $20 %$ số lượng test ứng khác với $20 %$ số điểm thỏa mãn điều kiện: $n \leq 10^{5}, m = 3$ .
Có $20 %$ số lượng test khác ứng với $20 %$ số điểm thỏa mãn điều kiện: $n \leq 10^{5}, m \leq 30$ .
Có $20 %$ số lượng test còn lại ứng với $20 %$ số điểm thỏa mãn điều kiện: $n \leq 10^{9}, m \leq 30$ và xâu mã hóa của xâu $T$ có độ dài không vượt quá $10^{5}$ .

Ví dụ

Input	Output	Giải thích
9 5 m1i1s2y1o1u3 isyou	6	Xâu $T =^{'} m i s s y o u u u^{'}$ . Có $6$ dãy số khác nhau để xác định mật khẩu $P = " i s y o u "$ trong $T$ .
11 3 m1i1s2i1s2i1p2i1 isi	14	Xâu $T =^{'} m i s s i s s i s s i p p i^{'}$ ... Có $14$ dãy số khác nhau xác định mật khẩu $P = " i s i "$ trong $T$ .

Bình luận

Không có bình luận tại thời điểm này.