Public Judge

pjudge

Time Limit: 2 s Memory Limit: 512 MB Total points: 100

#21656. 【PR #5】循环移位

Statistics

有一个非常简单的问题:给定一个 $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\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}$