Let's define a special array of length ~N~ as an array where the first occurrence of ~i~ comes before the first occurence of ~i+1~ for all ~1 \leq i < M~, where ~M~ is the maximum element of the array. A special array ~a~ is considered better than a special array ~b~ if ~a~ is lexicographically less than ~b~.

Everyone at Larry's school is collecting special arrays of length ~N~ these days. Being very competitive, Larry wants to know how many special arrays of length ~N~ are at least as good as his modulo ~10^6+7~. Can you help him?

Input Specification

The first line will contain one integer ~N\ (1 \leq N \leq 10^4)~.

The second line will contain ~N~ integers ~a_i\ (1 \leq a_i \leq N)~. It is guaranteed that ~a~ is a special array.

Output Specification

On one line you are to output the number of special arrays of length ~N~ that are at least as good as Larry's modulo ~10^6+7~.

Subtasks

Subtask 1 (30%)

~N \leq 14~

Subtask 2 (20%)

~N \leq 100~

Subtask 3 (20%)

~N \leq 1000~

Subtask 4 (30%)

No further constraints.

Sample Input

3
1 2 2

Sample Output

4