Một số người thích giả vờ rằng họ là một pharaoh. Hoặc một con cá heo. Luka là một trong những người như vậy.

Anh ấy đã xây dựng một bức phù điêu bao gồm một hàng dài gồm ~N~ cột có chiều cao nguyên không âm. Chiều cao của tất cả các cột ban đầu bằng không. Bức phù điêu được xây dựng theo từng bước, trong đó trong mỗi bước, Luka sẽ chọn một dãy cột liền kề có chiều cao bằng nhau và nâng tất cả các cột trong dãy con, ngoại trừ cột đầu tiên và cột cuối cùng lên một.

Hàng trăm năm đã trôi qua, một số cột đã bị đánh cắp. Cháu chắt nhiều đời của Luka đang cố gắng xác định số lượng phù điêu có thể được Luka xây dựng sao cho chiều cao của các cột còn lại phù hợp với bức phù điêu ban đầu.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(1 ≤ N ≤ 10 000)~, số cột trong bức phù điêu của Luka.
• Dòng đầu vào thứ hai chứa ~N~ số nguyên được phân tách bằng dấu cách ~h_i~ ~(-1 ≤ h_i \le 10 000)~, chiều cao của cột. Chiều cao ~-1~ tượng trưng cho cột bị đánh cắp.

Output

• Dòng đầu tiên và duy nhất của đầu ra phải chứa số lượng hình phù điêu có thể có chia dư cho ~1 000 000 007~.

Sample Input 1

3
-1 2 -1

Sample Output 1

0

Sample Input 2

3
-1 -1 -1

Sample Output 2

2

Sample Input 3

6
-1 -1 -1 2 -1 -1

Sample Output 3

3