Notice：Don't output extra spaces at the end of one line.
Let p1,p2,⋯,pn
be a permutation of length n
, Dodo bird built an array a
of length n
where ai
indicates the size of the monotonic stack got from p1,p2,⋯,pi
. For instance, if p
is 3,1,4,5,6,2
, we add the elements in the permutation to the monotonic stack one by one, the changes of the monotonic stack is as follows:
3→1→1,4→1,4,5→1,4,5,6→1,2
So the corresponding array a
is 1,1,2,3,4,2
.
Years later, Dodo bird found the array a
, but the value in some positions cannot be recognized anymore. He wants to know how many permutations can possibly be the original permutation. As the answer can be very large, you only need to output the answer module 109+7
.