当学生们遇到某个难题时经常会说“这怎么做，这不是 NP 问题吗？”，“这个只有搜了，已经被证明是 NP 问题了”。但是，你应该清楚，大多数人此时所说的 NP 问题其实都是指 NPC 问题。很多人没有真正掌握 NP 问题和 NPC 问题这两个基本概念。其实 NP 问题并不是那种“只有搜才行”的问题，NPC 问题才是。

很久以前就有一个古老的传说：有一个著名的问题，即 P 是否等于 NP 的问题，传说中谁要是证明或者证伪了这个命题，他将获得幸福。这里 P 是指能在多项式时间里求解的问题的集合。而 NP 是指可在多项式时间里验证的问题的集合。显然 P 是 NP 的子集，因为能在多项式时间里求解的问题，必定可在多项式时间里验证。

到目前为止还没有人因这个命题得到幸福。但是，有一个总的趋势，也就是人们普遍认为，P=NP 不成立，即，多数人相信，至少存在一个不可能有多项式时间复杂度的求解算法的 NP 问题。人们如此坚信 P≠NP 是有原因的，因为在研究 NP 问题的过程中找出了一类非常特殊的 NP 问题叫做 NP-完全问题，也就是所谓的 NPC 问题。正是因为存在 NPC 问题，才使人们相信 P≠NP。

在提出 NPC 的概念之后，绝大多数“自然”的难题最后都被证明是 NPC 问题，只有三个例外，它们分别是：

• 线形规划问题；
• 图同构问题；
• 素数判定问题与大数分解问题。

小雪在了解到以上情况后，自认为直接挑战终极难题还有不少困难，于是决定先从简单的问题做起，具体来说，他对图同构问题产生了浓厚的兴趣。A 图与 B 图被认为是同构的是指：A 图的顶点经过一定的重新标号以后，A 图的顶点集和边集要完全与 B 图一一对应。

小雪现在专注于如何判断两个图是否同构，同时他还想知道两两互不同构的含 $N$ 个点的图有多少种。众所周知含 $N$ 个点的简单图最多有 $N*(N-1)/2$ 条边，这样含 $N$ 个点的图有 $2^{N*(N-1)/2}$ 种可能的情况。显然这些图中有很多图是同构的，小雪想知道的便是：若同构的图算成一种，则有多少种不同的图。他把这个任务丢给了你。在他想出来之前快点解决吧！

输入格式

只有一个非负整数 $N$，表示图的顶点数，且 $0\le N\le 60$。

输出格式

输出仅包含一个整数，表示含 $N$ 个点的图在同构意义下不同构的图的数目。因为答案可能很大，所以输出的最终答案是 mod 997 的结果（997 是一个素数）。

样例数据

input.txt

• 样例一：1
• 样例二：2
• 样例三：3
• 样例四：5
• 样例五：9

output.txt

• 1
• 2
• 4
• 34
• 493

子任务

• 40%：$N\le 20$
• 100%：$N\le 60$