Here is a very simple problem: given a permutation $p$ of $1 \sim n$, find its unique cyclic shift that starts with $1$.

Little T wrote the following code:

// input p

for (int i=2;i<=n;i++)
    if (p[i]<p[1])
        shift(i); // change p to p[i],p[i+1],...,p[n],p[1],...,p[i-1]

// output p

Given a positive integer $n$, find how many different permutations $p$ will cause the algorithm above to output an incorrect result. Note that the answer does not need to be taken modulo any number.

Input

The first line contains a positive integer $n$.

Output

The first line contains a positive integer $ans$, representing the answer.

Examples

Input 1

3

Output 1

1

Note

The only permutation that causes it to output an incorrect answer is 3,2,1, which results in 2,1,3.

Input 2

7

Output 2

1023

For all test cases, $3\le n\le 42$. Within each group of test cases, $n$ is approximately uniformly distributed.