[HNOI2009]图的同构

给定顶点数 $N$，求含有 $N$ 个顶点、在同构意义下两两不同的简单图数量。

简单图是不含自环，且任意一对顶点之间至多存在一条无向边的图。

若将图 $A$ 的顶点按照某种方式重新编号后，其顶点集和边集能够分别与图 $B$ 的顶点集和边集一一对应，则称图 $A$ 与图 $B$ 同构。

输入格式

输入一行一个整数 $N$，表示图的顶点数。

输出格式

输出一行一个整数，表示含有 $N$ 个顶点、在同构意义下两两不同的简单图数量。答案对 $997$ 取模。

样例输入

样例一

1

样例二

2

样例三

3

样例输出

样例一

1

样例二

2

样例三

4

数据范围

• $0\le N\le 60$。

来源与许可

本题为 HNOI 2009 试题「图的同构」，题面与测试数据整理自 BZOJ。

样例 1

输入

1

输出

1

样例 2

输入

2

输出

2

样例 3

输入

3

输出

4