考虑一个无向图，它有 $n$ 个顶点和若干条边，每条边连接两个不同的顶点，且具有一个正整数长度。每对顶点之间最多只有一条边相连。

对于每一对顶点，我们可以找到连接它们的最短路径（路径长度为路径上各边长度之和）。对于某些顶点对，可能存在多条连接它们的最短路径。对于其他顶点对，可能根本没有路径连接它们。在本题中，我们只考虑那些任意一对顶点之间都有路径连接（即图是连通的）且任意一对顶点之间都有唯一最短路径的图。

现在我们可以忽略边及其长度，只保留所有最短路径。我们将一个最短路径系统定义为 $n$ 个顶点加上 $\frac{n(n-1)}{2}$ 条路径，每对顶点对应一条路径。每条路径仅仅是一个顶点序列。当然，并非任意一组路径都是一个最短路径系统——该系统必须对应于某个具有正整数边长的图。

对于给定的 $n$ 个顶点，有多少种不同的最短路径系统？如果可以通过对其中一个系统中的顶点进行重编号来得到另一个系统，则认为这两个系统是相同的。

输入格式

输入文件的唯一一行包含一个整数 $n$，$2 \le n \le 6$。

输出格式

输出 $n$ 个顶点的最短路径系统的数量。

样例

样例输入 1

3

样例输出 1

2

样例输入 2

4

样例输出 2

6

说明

对于 3 个顶点的最短路径系统，有两种情况：一种是每对顶点之间的最短路径就是连接它们的边，另一种是某些顶点对之间的最短路径通过了第一个顶点，而其他顶点对之间的最短路径则是直接相连的边。