Hàng cây

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,\dots ,p_k$ ($1\le p_1<p_2<\cdots <p_k\le n$; $k\ge 3$) thì:

$$h_{p_2}-h_{p_1}=h_{p_3}-h_{p_2}=\cdots =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 (các cây khác vị trí là khác nhau, kể cả khi có cùng chiều cao).

Dữ liệu vào

• 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,\dots ,h_n$ ($h_i\le {10}^6$, $\forall i=1,2,\dots ,n$).

Dữ liệu ra

In ra một số nguyên là số cách tìm được lấy theo modulo ${10}^9+7$.

Ràng buộc

• $1\le n\le {10}^4$.
• $1\le h_i\le {10}^6$ với mọi $i=1,2,\dots ,n$.

Subtasks

Điểm được tính theo từng test.

• Subtask 1 ($15\%$ số test): $n\le 20$; $h_i=i$, $\forall i=1,2,\dots ,n$.
• Subtask 2 ($15\%$ số test): $n\le 20$.
• Subtask 3 ($20\%$ số test): $20<n\le 500$.
• Subtask 4 ($20\%$ số test): $500<n\le 2000$.
• Subtask 5 ($30\%$ số test): $2000<n\le {10}^4$.

Ví dụ