东湖航线

题目描述

福海，又称东湖，是圆明园遗址公园中最大的湖。东湖是圆形的，我们要在东湖的边上建 $N$ 个游船码头，用以建立航线（可能为 $0$ 条航线），航线只能是一个码头到另一个码头，并且多条航线之间不能相交，共用码头也算相交。请你计算一下，共有多少建立航线的方案？

输入格式

一行一个数 $N$。

输出格式

由于结果可能很大，你只需要输出这个答案 $mod$ $10007$的值。

4

9

提示

#### 数据范围 对于 $30\%$数据：$N\le 10$ 对于 $50\%$数据：$N\le 100$ 对于 $100\%$数据：$N\le 1000$

来源

童程童美