有一个非常简单的问题：给定一个 $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
给定正整数 $n$ ，求出有多少个不同的排列 $p$ 会使得上面这个算法输出错误的结果。注意答案不需要取模。
输入格式
第一行一个正整数 $n$ 。
输出格式
第一行一个正整数 $ans$ ，表示答案。
样例
3
1
explanation
唯一一个会使得它输出错误答案的排列是 3,2,1 ，它会输出 2,1,3 。
7
1023
数据范围与提示
| 测试点编号 | $n\leq$ |
|---|---|
| $1\sim 4$ | $13$ |
| $5\sim 8$ | $22$ |
| $9\sim 16$ | $38$ |
| $17\sim 20$ | $42$ |
在同一档数据中，$n$ 近似均匀分布。
对于所有数据，$3\le n\le 42$ 。
时间限制：$2\texttt{s}$
空间限制：$512\texttt{MB}$