PreVOI 2025 - Contest 2 - Băng rôn

Xem dạng PDF

Gửi bài giải

Điểm: 45,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout
Test chính thức

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, PyPy, Python, Scratch

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Để chuẩn bị cho buổi lễ ra quân kỳ thi Đội tuyển Học sinh giỏi Quốc gia năm nay, các bạn trong đội tuyển môn Tin học của trường đã được giao cho nhiệm vụ chuẩn bị một băng rôn chứa dòng chữ "HSG25".

Các bạn tìm được trong nhà kho của trường một băng rôn ~s~ gồm ~n~ kí tự ~s_1s_2 \dots s_n~ (các kí tự của ~s~ thuộc một trong năm loại 'H', 'S', 'G', '2', '5'). Sau khi tìm thấy băng rôn thì Nam, một bạn trong đội tuyển, đã nghĩ ra ý tưởng sau: cậu sẽ chọn ra năm kí tự thuộc năm vị trí khác nhau trong băng rôn ~s~, sau đó cắt rời các kí tự được chọn rồi ghép chúng lại với nhau theo đúng thứ tự vị trí ban đầu để tạo thành một băng rôn mới có chứa đúng dòng chữ "HSG25".

Bình, một bạn học sinh khác trong đội tuyển, đã đố Nam đếm số cách chọn ra bộ năm vị trí trong băng rôn ~s~ sao cho băng rôn mới có chứa đúng dòng chữ "HSG25". Nam đã nhanh chóng giải được bài toán trên, đồng thời đố lại Bình một bài toán khó hơn. Bình cần trả lời ~q~ truy vấn, truy vấn thứ ~i~ được xác định bởi hai số nguyên ~l_i~ và ~r_i~, yêu cầu: xét băng rôn con ~p~ gồm các kí tự từ vị trí ~l_i~ đến ~r_i~, hãy đếm số cách chọn bộ năm vị trí khác nhau từ băng rôn ~p~ sao cho băng rôn mới có chứa đúng dòng chữ "HSG25".

Yêu cầu: Hãy giúp Bình giải bài toán hóc búa mà Nam đã đưa ra. Vì đáp án có thể rất lớn nên Bình cần đưa ra kết quả cho từng truy vấn sau khi chia lấy phần dư cho ~10^9 + 7~.

Input

  • Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~q~ ~(5 \le n \le 50000, 1 \le q \le 50000)~ là số kí tự của băng rôn ~s~ và số truy vấn.

  • Dòng thứ hai chứa xâu ~s~ gồm ~n~ kí tự ~s_1s_2 \dots s_n~ (~s_i \in \{~'H', 'S', 'G', '2', '5'~\}~) là các kí tự trên băng rôn ~s~.

  • Dòng thứ ~i~ trong ~q~ dòng tiếp theo gồm hai số nguyên ~l_i~ và ~r_i~ ~(1 \le l_i \le r_i \le n)~ mô tả truy vấn thứ ~i~.

Output

In ra ~q~ dòng, dòng thứ ~i~ gồm một số nguyên duy nhất là đáp án của truy vấn thứ ~i~ sau khi chia lấy phần dư cho ~10^9 + 7~.

Scoring

Subtask Điểm Ràng buộc
1 ~30\%~ ~n, q \le 20~
2 ~20\%~ ~n, q \le 1000~
3 ~20\%~ xâu ~s~ được tạo thành từ việc ghép lần lượt ~a~ kí tự H, ~b~ kí tự S, ~c~ kí tự G, ~d~ kí tự 2, ~e~ kí tự 5 với ~0 \le a, b, c, d, e~ và ~a+b+c+d+e=n~
4 ~30\%~ Không có giới hạn gì thêm

Sample Input 1

8 4
HHSG2525
1 6
2 8
4 5
1 8

Sample Output 1

2
3
0
6

Sample Input 2

14 5
GHSG2H5SG25S25
1 7
1 10
1 11
1 13
1 14

Sample Output 2

1
1
6
6
15

Notes

Ở ví dụ thứ nhất, đáp án cho các truy vấn được giải thích như sau:

  • Với truy vấn thứ nhất, ta có ~p =~ HHSG25. Có ~2~ cách chọn ra bộ năm kí tự từ ~p~: H̅ H S̅ G̅ 2̅ 5̅ và H H̅ S̅ G̅ 2̅ 5̅ (các kí tự có gạch ngang trên đầu cho biết các vị trí được chọn)

  • Với truy vấn thứ hai, ta có ~p =~ HSG2525. Có ~3~ cách chọn ra bộ năm kí tự từ ~p~: H̅ S̅ G̅ 2̅ 5̅ 2 5, H̅ S̅ G̅ 2̅ 5 2 5̅ và H̅ S̅ G̅ 2 5 2̅ 5̅

  • Với truy vấn thứ ba, ta có ~p =~ G2. Do xâu ~p~ chỉ có hai kí tự nên không tồn tại các chọn ra bộ năm kí tự từ ~p~ thỏa yêu cầu đề bài.

  • Với truy vấn thứ tư, ta có ~p =~ HHSG2525. Có ~6~ cách chọn ra bộ năm kí tự từ ~p~.


Bình luận

Hãy đọc nội quy trước khi bình luận.


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