Ông Từ đang ôn bài tập về dãy số, hôm nay ông có $1$ dãy số $a$ gồm $n$ phần tử, đối với ông $1$ dãy con liên tiếp của $a$ được xem là dãy đẹp nếu số lượng phần tử của dãy con đó không bé hơn giá trị bé nhất trong dãy con và không lớn hơn giá trị lớn nhất trong dãy con. Hay nói cách khác, đoạn con từ $i$ đến $j$ được xem là đẹp nếu $Min(a_i,a_{i+1},...a_j)\le j-i+1\le Max(a_i,a_{i+1},...a_j)$. Ông Từ muốn tính số cách chia dãy thành các đoạn đẹp sao cho mỗi phần tử phải thuộc duy nhất $1$ đoạn đẹp. Vì số cách có thể rất lớn nên bạn hãy in số cách dưới dạng modulo cho ${10}^9+7$ giúp ông nhé.

Input

• Dòng đầu tiên ghi số $n$ $(1\le n\le {10}^5)$;
• Dòng tiếp theo gồm $n$ số mô tả mảng $a$ $(1\le a_i\le n)$.

Output

• Gồm $1$ số nguyên là kết quả bài toán.

Sample Input

7
1 6 2 3 4 3 4

Sample Output

6