Để 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 50\,000, 1 \le q \le 50\,000~) 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~.