Một dãy số ~x_1, x_2, \ldots, x_m~ được gọi là dominative nếu tồn tại một giá trị ~k~ xuất hiện nhiều hơn ~\frac{m}{2}~ lần. Ví dụ:

• Dãy ~[3, 2, 2]~ là dominative vì giá trị ~2~ xuất hiện ~2~ lần, lớn hơn ~\frac{3}{2}~.
• Dãy ~[1, 2, 3, 2]~ không phải dominative vì không có giá trị nào xuất hiện nhiều hơn ~\frac{4}{2} = 2~.

Yêu cầu

Cho dãy ~a_1, a_2, \ldots, a_n~, bạn cần đếm số cách chia dãy này thành các đoạn con liên tiếp sao cho mỗi đoạn con đều không dominative.

Dữ liệu vào từ tệp văn bản: DOMI.INP

• Dòng đầu tiên chứa số nguyên ~n~ (~1 \leq n \leq 2 \times 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~1 \leq a_i \leq 10^9~).

Kết quả ghi ra tệp văn bản: DOMI.OUT

• In ra số cách chia thỏa mãn chia lấy dư cho ~10^9 + 7~.

Giới hạn

• Trong tất cả các test ~n \leq 2 \times 10^5~, ~a_i \leq 10^9~.
• ~18 \%~ số test có ~n \leq 100~.
• ~18 \%~ số test có ~n \leq 1000~.
• ~24 \%~ số test có ~n \leq 5000~.
• ~15 \%~ số test có ~1 \leq a_i \leq 2~.
• ~25 \%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

4  
3 6 6 9  

Sample Output 1

2  

Sample Input 2

6  
1 2 1 2 1 2  

Sample Output 2

4  

Giải thích

• Ở test ví dụ đầu tiên, có 2 cách chia là ~[3, 6, 6, 9]~ hoặc ~[3, 6], [6, 9]~