Độ 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

---

Bài toán được chuyển sang dạng nhập/xuất chuẩn (stdin/stdout); định dạng xem ở mục Dữ liệu vào.

Một dãy được gọi là đặc biệt nếu nó gồm một số dương các số ~0~, tiếp theo là một số dương các số ~1~, rồi đến một số dương các số ~2~.

• Ví dụ, [0,1,2] và [0,0,1,1,1,2] là các dãy đặc biệt.
• Ngược lại, [2,1,0], [1] và [0,1,2,0] không phải dãy đặc biệt.

Cho mảng nums (chỉ gồm các số nguyên ~0~, ~1~ và ~2~), hãy in ra số lượng dãy con khác nhau là dãy đặc biệt. Vì đáp án có thể rất lớn, hãy in ra nó theo modulo ~10^9 + 7~.

Một dãy con của mảng là dãy thu được từ mảng bằng cách xoá đi một số (hoặc không xoá) phần tử mà không làm thay đổi thứ tự các phần tử còn lại. Hai dãy con được coi là khác nhau nếu tập chỉ số được chọn của chúng khác nhau.

Dữ liệu vào

• Dòng đầu là số nguyên ~n~ (độ dài mảng).
• Dòng thứ hai gồm ~n~ số nguyên nums[0], nums[1], ..., nums[n-1].

Kết quả

• Một số nguyên là số dãy con đặc biệt, lấy modulo ~10^9 + 7~.

Giới hạn

• ~1 \le n \le 10^5~.
• ~0 \le~ nums[i] ~\le 2~.

Sample Input 1

4
0 1 2 2

Sample Output 1

3

Giải thích

Các dãy con đặc biệt (in đậm là phần được chọn) là [0,1,2,2], [0,1,2,2] và [0,1,2,2].

Sample Input 2

4
2 2 0 0

Sample Output 2

0

Giải thích

Không có dãy con đặc biệt nào trong [2,2,0,0].

Sample Input 3

6
0 1 2 0 1 2

Sample Output 3

7

Giải thích

Các dãy con đặc biệt là [0,1,2,0,1,2], [0,1,2,0,1,2], [0,1,2,0,1,2], [0,1,2,0,1,2], [0,1,2,0,1,2], [0,1,2,0,1,2], [0,1,2,0,1,2].

Nguồn: LeetCode 1955.