512010 - 图的同构计数

【题目描述】图的同构计数(isomorphism)

琳琳对图同构问题产生了浓厚的兴趣。A图与B图被认为是同构的是指:A图的顶点经过一定的重新标号以后,A图的顶点集和边集要完全与B图一一对应。 琳琳现在专注于如何判断两个图是否同构,同时她还想知道两两互不同构的含N个点的图有多少种。众所周知含N个点的简单图最多有N×(N−1)/2条边,这样含N个点的图有2N×(N−1)/2种可能的情况。显然这些图中有很多图是同构的,琳琳想知道的便是:若同构的图算成一种,则有多少种不同的图。

输入

一个整数N(0≤N≤60),表示图的顶点数。

输出

输出一个整数,表示含N个点的图在同构意义下不同构的图的数目。因为答案可能很大,所以输出的最终答案是模997的结果(997是一个素数)。

样例

输入

1

输出

1

输入

3

输出

4

输入

    9


输出

493
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题