Дистанционный практикум по программированию

Bubble sort is well known to all computer scientists. While studying the complexity of this algorithm, a notable programming theorist Bublikov asked himself how many times an element of the original array is moved. To find the answer, he wrote a program, which used array S to count moves in the array A being sorted. To make things easier, Bublikov used numbers 1 to n (in random order) when filling the array to be sorted. He even remembered to fill array S with zeroes during initialization!

Below is an extract from his Pascal program that sorts array A consisting of n elements and counts the moves for each element.

for i=1 to n-1 do

   for j=1 to n-i do

      if A[j]>A[j+1] then

         begin

            r:=A[j]; A[j]:=A[j+1]; A[j+1]:=r;

            inc(S[A[j]]);  inc(S[A[j+1]]);

         end;

After one of his experiments Bublikov noted that all elements in S are equal
to 2. The scientist wondered if it was possible to find out the original order of elements in array A. It turned out that the answer is ambiguous. For example, for n=7 there are two variants of element order in A: “3 2 1 6 7 4 5” or “3 4 1 2 7 6 5”.

Write a program that will determine the number of ways to restore the original array if every element in S is equal to 2.

Limitations

1 <= n <= 100

Input

The input file specifies an integer n, the number of elements in the array being sorted.

Output

The first line of the input file should contain an integer k, the number of distinct original arrays corresponding to the given counter values. Then n space-delimited integers follow (all numbers from the range 1 to n). These integers show one of the possible element orders in the array being sorted.

Sample

Standard input	Standard output
7	2 3 2 1 6 7 4 5
5	0