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?
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.
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~.
Subtask 1 (30%)
~N \leq 14~
Subtask 2 (20%)
~N \leq 100~
Subtask 3 (20%)
~N \leq 1000~
Subtask 4 (30%)
No further constraints.
3 1 2 2