Newton's Beautiful Sequence

Sort each non-empty contiguous subarray of the original array independently. After sorting, the subarray's contribution increases by 1 for each pair of adjacent elements whose difference is greater than 1; a subarray of length 1 also contributes 1. Output the total contribution of all subarrays modulo 10^9+7.

输入格式

The input is N followed by N integers. This site adopts the constraints listed separately in the statement, 1≤N≤1000 and 1≤sequence[i]≤N; the text of the main constraint line is run together, so this site organizes it according to this readable constraint.

输出格式

Output the total beauty modulo 10^9+7.

样例 1

输入：

5
2 2 2 1 5

输出：

9

样例 2

输入：

1
1

输出：

1

样例 3

输入：

4
1 3 2 3

输出：

5