Having finally finished the coach’s demanding tasks, Huzz had earned a rest. He found it on lazy afternoon, where the world seemed to slow to a crawl, wrapped in the warm, golden haze of impending dusk. A gentle breeze did little more than stir the dust motes dancing in the sunbeams slanting through the leaves of a great oak tree.
In that sleepy, comfortable void, Huzz found a permutation in his soft shark toy. He decided to share it with his friends for fun.
Mino loves splitting. He can split this permutation into several contiguous segments.
Yana loves swapping. He can choose contiguous segment and swap its maximum and minimum elements.
Specifically, they can perform the following types of operations any number of times, in any order:
split: Choose contiguous segment whose length is greater than . Then choose position inside it and split it into adjacent contiguous segments. For example, can be split into and , where .
swap: Choose contiguous segment and swap its maximum and minimum elements.
After performing any number of operations, they stop performing, and all resulting segments are merged in their original order to form a new permutation.
White loves counting. She wonders — how many distinct permutations can they obtain?
As the result can be very large, you only need to find the answer modulo .
输入格式
The first line the input contains an integer (), the length of the permutation.
The second line contains integers (), representing the permutation itself. It’s guaranteed that is a permutation.
输出格式
Print an integer, the number of distinct permutations they can obtain modulo .
样例
样例输入 1
4
1 4 2 3
样例输出 1
10
样例输入 2
7
5 1 4 2 6 3 7
样例输出 2
340
数据范围与提示
In the first sample, the following are all possible permutations they can obtain:
