# Swaps

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 i

^{th}and (i+1)

^{th}elements. For instance at position 4, you can perform swap to interchange 4

^{th}and 5

^{th}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 1

^{st}position interchanging 1

^{st}and 2

^{nd}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.

Read until EOF.

**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