First differences of permutations
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. |
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.
Example 1
Input9 1 4 2 5 7 6 9 8 3Output
8The permutations and their respective first differences are depicted in the Image 1.
Example 2
Input12 12 3 6 1 9 11 8 5 2 4 7 10Output
12The 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
Input14 12 13 11 10 1 2 6 7 8 5 3 14 4 9Output
536
Example 4
Input15 14 12 8 13 4 5 3 7 15 1 2 9 6 10 11Output
2300
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.
Link to public data set