题目描述

Saratov ACM ICPC 队伍把一种特殊的图称为 Mescher Tree：

• 图是无向连通图；
• 有 $n$ 个带编号的顶点；
• 恰好有 $n$ 条边。

由于连通图若有 $n$ 个顶点和 $n$ 条边，恰好含有一个环，因此 Mescher Tree 本质上就是一个带标号的连通单环图。

给定 $n$，求不同 Mescher Tree 的数量。两个图当且仅当邻接矩阵不同才视为不同。

答案可能非常大，需要输出十进制精确值。

输入格式

一个整数 $n$，满足 $3\le n\le5000$。

输出格式

输出一个整数，表示 $n$ 个带标号顶点的 Mescher Tree 数量，不含前导零。

样例

3

1