First differences of permutations

Assignment

Quido discovered that permutations can be an endless source of amusement. As he often does, he just started doodling and chose one of the most simple set of numbers {1, 2, 3, 4, 5, 6, 7, 8, 9}.
He wrote down one random permutation of this set: (1, 4, 2, 5, 7, 6, 9, 8, 3). Then, without too much thinking he wrote under this permutation its first difference. The first difference, in this case, is (3, -2, 3, 2, -1, 3, -1, -5). Now, he started wondering. Are there other permutations of the same set which share the same first difference? Well, not exactly the same first difference, because the first difference is obviously unique for each permutation of this set, but a first difference which would contain all the numbers of the original first difference, arranged in different order. After some thought he came up with the solution drawn bellow. Note that the original Quido’s permutation is the second one in the first column of the list. He was quite sure that there are no more permutations with this property. To investigate more in this direction Qiudo decided to do some programming.

Image 1. All eight permutations of the set {1, 2, 3, 4, 5, 6, 7, 8, 9} which first difference is

(3, -2, 3, 2, -1, 3, -1, -5) up to permutation.
The permutations are written in gray cells, the first differences are written in orange cells. image::old_practical_exams/firstdifference/pic1sm.png[pic1sm, 700]

The task

Given a permutation π of a set S(N) = {1, 2, 3, …, N} find the number of all such permutations φ of S(N) for which it holds that the first difference of φ is a permutation of the first difference of π.

The first difference of permutation π of S(N) is defined to be the sequence (π(2) − π(1), π(3) − π(2), …, π(N) − π(N−1)).

Input

The input consists of two text lines. The first line contains one positive integer N ≤16 specifying the set S(N) = {1, 2, 3, …, N}. Next line contains a permutation π of S(N) in the form
π(1) π(2) π(3) … π(N)
All values are separated by spaces.

Output

Output contains a single text lines with the number of permutations of S(N) which first difference is a permutation of the first difference of π. The output value does not exceed 5000.

Examples

Example 1

Input

9
1  4  2  5  7  6  9  8  3

Output

The permutations and their respective first differences are depicted in the Image 1.

Example 2

Input

12
12  3  6  1  9 11  8  5  2  4  7 10

Output

The respective permutations of S(N) are

 3 11  8  5  2  4  6  9 12  7 10  1
 3  6  9 11  8  5  2  4 12  7 10  1
 4 12  7 10  1  3  6  9 11  8  5  2
 4  7 10 12  3  6  1  9 11  8  5  2
 4  6  9 12  7 10  1  3 11  8  5  2
 6  9 12  7 10  1  3 11  8  5  2  4
 9 11  8  5  2 10 12  3  6  1  4  7
11  8  5  2 10 12  3  6  1  4  7  9
11  8  5  2  4 12  7 10  1  3  6  9
11  8  5  2  4  7 10 12  3  6  1  9
12  3  6  1  9 11  8  5  2  4  7 10
12  3  6  1  4  7  9 11  8  5  2 10

Example 3

Input

14
12 13 11 10  1  2  6  7  8  5  3 14  4  9

Output

Example 4

Input

15
14 12  8 13  4  5  3  7 15  1  2  9  6 10 11

Output

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.

Veřejná data