[FJOI2007]轮状病毒

题目描述

轮状病毒有很多变种。许多轮状病毒都是由一个轮状基产生。一个n轮状基由圆环上n个不同的基原子和圆心的一个核原子构成。2个原子之间的边表示这2个原子之间的信息通道,如图1。 n轮状病毒的产生规律是在n轮状基中删除若干边,使各原子之间有唯一一条信息通道。例如,共有16个不同的3轮状病毒,入图2所示。 给定n(N<=100),编程计算有多少个不同的n轮状病毒。 ![](https://cdn.luogu.com.cn/upload/pic/1408.png)

输入输出格式

输入格式


第一行有1个正整数n。

输出格式


将编程计算出的不同的n轮状病毒数输出

输入输出样例

输入样例 #1

3

输出样例 #1

16