Australia consists of a single long road from west to east. There are ~N~ stores along this road, with the ~i~-th store having an integer position of ~p_i~.

You have been commissioned to design and install a signpost. First, you will choose a real number ~K~, representing the position of the signpost. Let ~d_i = |p_i-K|~ represent the distance from the signpost to the ~i~-th store. The signpost will contain all ~N~ stores on it in some order from top to bottom, under the condition that if ~d_i < d_j~, then store ~i~ is listed higher up on the signpost than store ~j~. If two stores are equidistant from the signpost, then you can decide which of stores ~i~ and ~j~ is listed higher up the signpost.

Your first task is to calculate how many distinct signposts you could make. Since this number may be large, you want to find this number modulo ~10^9+7~.

Constraints

~1 \le N \le 5 \times 10^5~

~1 \le p_i \le 5 \times 10^5~

All ~p_i~ are distinct.

Subtask 1 [50%]

~1 \le N \le 3000~

Subtask 2 [50%]

No additional constraints.

Input Specification

The first line contains a single integer, ~N~.

The second line contains ~N~ space-separated integers, ~p_1, p_2, \dots, p_N~.

Output Specification

On a single line, print the number of possible distinct signposts, modulo ~10^9+7~.

Sample Input

3
1 2 3

Sample Output

4

Explanation

Consider the case where the signpost is at position ~K = 2~. Then ~d_1 = 1, d_2 = 0, d_3 = 1~. From the top to bottom, the signpost could list stores ~2~ then ~1~ then ~3~, or stores ~2~ then ~3~ then ~1~.

If we consider all possible values of ~K~, including non-integer and negative values, we see that there are ~4~ distinct signposts which can be made.