有一个非常简单的问题：给定一个 $1\sim n$ 的排列 $p$ ，求出它唯一一个以 $1$ 开始的循环移位。

小 T 写出了如下代码：

// input p

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

// output p

给定正整数 $n$ ，求出有多少个不同的排列 $p$ 会使得上面这个算法输出错误的结果。注意答案不需要取模。

输入格式

第一行一个正整数 $n$ 。

输出格式

第一行一个正整数 $ans$ ，表示答案。

样例一

input

3

output

1

explanation

唯一一个会使得它输出错误答案的排列是 3,2,1 ，它会输出 2,1,3 。

样例二

input

7

output

1023

数据范围与提示

在同一档数据中，$n$ 近似均匀分布。

对于所有数据，$3\le n\le 42$ 。

时间限制：$2\texttt{s}$

空间限制：$512\texttt{MB}$