背景

wys是TKD的妹子。

wys听说TKD总把题面写得很长很长；

于是这一次她要求TKD把题面写得很短很短。

描述

统计N个点N条边的简单无向连通图个数。

输入格式

一行一个整数N。

输出格式

输出一行一个整数，描述答案。

样例输入1

3

样例输出1

1

样例输入2

4

样例输出2

15

数据范围与约定

• 对于30%的数据:1<=N<=10;
• 对于60%的数据:1<=N<=50;
• 对于100%的数据:1<=N<=5000