考虑以下问题：

• 给定一个包含 $1$ 到 $n$ 每个整数恰好一次的排列 $A = \langle a_1, a_2, \dots, a_n \rangle$。找出其唯一以 $1$ 开头的循环移位。

考虑以下解决该问题的算法：

• 输入：$A = \langle a_1, a_2, \dots, a_n \rangle$。
• 对于每个 $i = 2, 3, \dots, n$： 如果 $a_i < a_1$： 将 $A$ 进行循环移位，使得 $a_i$ 移动到最前面；即令 $A \leftarrow \langle a_i, a_{i+1}, \dots, a_n, a_1, a_2, \dots, a_{i-1} \rangle$。
• 输出：$A = \langle a_1, a_2, \dots, a_n \rangle$。

给定一个整数 $n$，求有多少个排列使得上述算法无法正确解决该问题。

输入格式

仅一行，包含一个整数 $n$ ($1 \le n \le 42$)。

输出格式

输出使得上述算法运行结果错误的排列数量。

样例

样例输入 1

3

样例输出 1

1

样例输入 2

7

样例输出 2

1023

说明

在第一个样例中，对于 $n = 3$，唯一导致输出错误的排列是 $\langle 3, 2, 1 \rangle$。该算法返回 $\langle 2, 1, 3 \rangle$，而正确答案应为 $\langle 1, 3, 2 \rangle$。