In this problem you will be given an array A[] of numbers from 0 to N-1 i.e. some permutation of numbers from 0 to N-1. You have to sort the array by performing swaps. The swaps can be performed at positions 0, 1, 2,..., N-2. That is you can perform swaps at first N-1 positions of the array and this swapping takes place between ith and (i+1)th elements. For instance at position 4, you can perform swap to interchange 4th and 5th elements. Further, you can perform swap at a position once only.

You have to find the number of permutations of N-1 swap positions so that each of these permutation, which is a swap sequence when performed in sequence will make the array sorted. Since this number will be huge, you print the number of permutations modulo 1000000007.

For instance, lets suppose we have the array {1, 2, 0}. We can perform swap at 0th position interchanging 0th and 1st elements and at 1st position interchanging 1st and 2nd elements. In this case we have two possible permutations of swap sequences <0, 1> and <1, 0>. Taking the first sequence, and performing the swaps in sequence our array will be {2, 1, 0} -> {2, 0, 1}. Similarly for the second sequence, the final array after swappings will be {1, 0, 2} -> {0, 1, 2} (sorted). The second swap sequence is the only viable permutation. So the count will be 1.

Constraints
A will contain a maximum of 50 and minimum of 2 elements.
Each element lies between 0 to N-1(inclusive) where N will be the size of array.
There is no duplicates in the array.

Input
Each test case contains a line containing N integers. These N integers is a permutation of numbers from 0 to N-1.

Output
Print one line the number of permutations of swap positions as described above modulo 1000000007.

Sample Input
1 2 0
0 1
2 0 3 1
1 0 3 2
1 3 0 5 2 7 4 8 10 6 12 9 14 11 16 13 18 15 19 17

Sample Output
1
0
2
0
716743312

Problem Setter: Dhruva Bhaswar

Languages: Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Ruby,Text

Time Limit: 8 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Mode Judge

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0