Độ khó: Khó (4/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Quang có một dãy số nguyên dương ~a_1, a_2, \ldots, a_n~. Quang đố Linh viết một chương trình đếm số lượng dãy con ~b_1, b_2, \ldots, b_k~ của ~a~ sao cho tích ~b_1 \times b_2 \times \ldots \times b_k~ không vượt quá một số ~x~ cố định.

Do Linh mới học lập trình nên chương trình của Linh phải mất 69420ms mới có thể đưa ra kết quả. Liệu bạn có thể viết một chương trình chỉ chạy trong 694ms hay không?

Nhắc lại: một dãy ~b~ là một dãy con của dãy ~a~ khi và chỉ khi có thể xóa một số phần tử trong ~a~ và giữ nguyên thứ tự các phần tử còn lại để thu được dãy ~b~.

Yêu cầu: Bạn hãy viết một chương trình kiểm tra xem kết quả chương trình của Linh đưa ra có đúng hay không.

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên dương ~n, x~ ~(1 \le n \le 10^5,\ 1 \le x \le 2 \times 10^5)~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ ~(1 \le a_i \le x)~.

Kết quả

• Một dòng duy nhất là số lượng dãy con thỏa mãn. Vì kết quả có thể rất lớn nên chỉ cần in ra phần dư của nó khi chia cho ~10^9 + 7~.

Subtask

• ~20\%~ số điểm có ~n \le 20~.
• ~20\%~ số điểm khác có ~a_i = 1~.
• ~20\%~ số điểm khác có ~n, x \le 5000~.
• ~15\%~ số điểm khác có ~a_i~ là lũy thừa của ~2~.
• ~15\%~ số điểm khác có ~a_i = i~.
• ~10\%~ số điểm còn lại không có giới hạn gì thêm.

Sample Input 1

4 6
2 3 3 4

Sample Output 1

6

Giải thích

Các dãy con thỏa mãn là:

• 1 phần tử: ~(2), (3), (3), (4)~.
• 2 phần tử: ~(2, 3), (2, 3)~.

Không có dãy con có 3 hoặc 4 phần tử nào thỏa mãn điều kiện.

Nguồn: Thi thử HSG9 SQRTOJ 2025 – Ngày 1 Bài 3.