Trên một tuyến đường có ~n~ cây cổ thụ thuộc một trong ~n~ loại khác nhau. Từ đầu đến cuối đoạn đường, cây thứ ~i~ có chiều cao là ~h_i~. Chính quyền thành phố muốn loại bỏ một số cây để những cây còn lại có chiều cao tăng dần từ đầu đến cuối đoạn đường. Đồng thời, để tăng tính thẩm mỹ, lãnh đạo cũng muốn số cây còn lại không nhỏ hơn ~3~ và chiều cao của các cây giữ lại nhìn từ đầu tới cuối tạo thành một cấp số cộng. Nói cách khác, giả sử giữ lại ~k~ cây, và các cây được giữ lại có chỉ số ~p_1, p_2, ..., p_k~ (~1 \le p_1 < p_2 < \dots < p_k \le n; k \ge 3~) thì: $$h_{p_2} - h_{p_1} = h_{p_3} - h_{p_2} = \dots = h_{p_k} - h_{p_{k-1}} > 0$$

An đang thắc mắc liệu có bao nhiêu cách chọn cây thỏa mãn yêu cầu của lãnh đạo chính quyền thành phố đưa ra. Hai cách chọn được gọi là khác nhau nếu tồn tại một cây được chọn ở cách này nhưng không xuất hiện ở cách chọn còn lại.

Input

• Dòng đầu chứa số nguyên dương ~n~ (~n \le 10^4~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~h_1, h_2, ..., h_n~ (~h_i \le 10^6, \forall i = 1, 2, ..., n~).

Output

• Một số nguyên là số cách tìm được lấy theo module ~10^9 + 7~.

Sample Input 1

6
3 1 3 5 9 7

Sample Output 1

5

Giải thích ví dụ

Có ~5~ cách lựa chọn giữ lại các cây với thứ tự: ~\{1, 4, 6\}; \{2, 3, 4\}; \{2, 3, 4, 6\}; \{2, 4, 5\}; \{3, 4, 6\}~.

Subtasks