Background

This problem comes from the original BZOJ. We acknowledge that the copyright of the statement and the original testdata belongs to the original BZOJ or the problem setter who authorized BZOJ to use it. If you are the copyright holder and believe that we have infringed your rights, please contact us.

Problem Description

You are given a sequence $a_1, a_2, \dots a_n$ of length $n$. If the sequence $a$ is not non-decreasing, you must delete one number from it.

This operation will be performed repeatedly until $A$ becomes non-decreasing. Find how many different operation plans there are. Two operation plans are considered different if and only if the deletion order or the number of deletions is different. Output the answer modulo $10^9+7$.

Input Format

The first line contains a positive integer $n$, representing the length of the sequence.

The second line contains $n$ non-negative integers $a_i$, representing the sequence.

Output Format

Output one integer per line, representing the value of the answer modulo $10^9+7$.

4
1 7 5 3

18

Hint

For $100\%$ of the testdata, $1 \leq n \leq 2 \times 10^3$, and $0 \leq a_i \leq 2^{31}-1$.

Translated by ChatGPT 5