大小为 $n$ 的轮图（Wheel Graph）是一个包含 $n$ 个顶点 $v[1], \dots, v[n]$ 的环，其中每个顶点都与一个中心顶点 $v[0]$ 相连。下图展示了大小为 4、5、6 和 8 的轮图示例：

大小为 $n$ 的破损轮图（Broken Wheel Graph）是指将大小为 $n$ 的轮图中连接 $v[n]$ 到 $v[1]$ 的边移除后得到的图。下图展示了大小为 4、5、6 和 8 的破损轮图示例：

图 $G$ 中的生成单圈（spanning unicycle）是指在 $G$ 的生成树中额外添加一条边，从而形成唯一一个环的子图。下图中的每个示例都是大小为 5 的破损轮图中的生成单圈：

编写一个程序，计算大小为 $n$ 的破损轮图中不同生成单圈的数量。请注意，图 $G$ 的两个子图 $S1$ 和 $S2$ 是不同的，当且仅当存在至少一条属于 $S1$ 但不属于 $S2$ 的边，或者存在一条属于 $S2$ 但不属于 $S1$ 的边。

输入格式

输入包含一行，为一个十进制整数 $m$ ($3 \le m \le 4000$)，表示要计算生成单圈数量的破损轮图的大小。

输出格式

输出一行，包含生成单圈的数量对 $100007$ 取模的结果。

样例

样例输入 1

5

样例输出 1

19

样例输入 2

1234

样例输出 2

50380