nodgd现在是南开的信息学竞赛教练，虽然工资很低，但在昔日的小伙伴眼中nodgd就是个土豪。每当昔日的小伙伴缺钱来找nodgd借钱时，nodgd就会以“钱也不是天上掉下来的，赚钱养家也都不容易”这样的借口推辞。每当nodgd缺钱去找昔日的小伙伴借钱，nodgd会说“这么多年的友情也都不容易，不要因为借钱这么点小事情破坏了感情”。久而久之，nodgd就没有小伙伴了。

nodgd上次借小伙伴的钱买了一套积木。积木共有$n$块，每块形状相同但颜色不同。每块积木都有大小两端，一块积木的大端可以和另一块积木的小端连接起来，特别的，同一块积木的大小两端也可以连接起来。如果将若干块积木的大小端首尾连接起来，就形成了一个积木圈。为了方便携带，nodgd将$n$块积木连接成若干个积木圈后，用一个绳圈将它们串起来。虽然积木圈有大有小，但串在绳圈上后它们的相对位置就不会发生变化。

一天，nodgd突发奇想，打算枚举所有将$n$个积木都挂到绳圈上的方案。聪明的nodgd掐指一算，发现方案非常多，但具体是多少nodgd才懒得算——他让你帮他算！你只要告诉nodgd方案数$\mod{1,000,000,007}$ 后的结果即可。

输入共$1$行，有一个整数$n$，表示积木的总数。

输出一行，一个整数，表示方案数$\mod{1,000,000,007}$ 的结果。

样例说明1

共有$3$个积木，不妨编号为$1,2,3$。

• 将积木$1$、积木$2$、积木$3$连接在一起形成一个积木圈，有$2$种情况，分别是$(1\to2\to3\to1)$和$(1\to3\to2\to1)$；每种情况都有$1$种串在绳圈上的方案，共$2$种方案。

• 将积木$1$单独连接成积木圈，积木$2$和积木$3$连接在一起形成一个积木圈，有$1$种情况，即$(1\to1)(2\to3\to2)$；这$1$种情况有$1$种串在绳圈上的方案，共$1$种方案，即$(1\to1)-(2\to3\to2)-(1\to1)$。

• 将积木$2$单独连接成积木圈，积木$1$和积木$3$连接在一起形成一个积木圈，同上，共$1$种方案。

• 将积木$3$单独连接成积木圈，积木$1$和积木$2$连接在一起形成一个积木圈，同上，共$1$种方案。

• 将三个积木都单独连接成积木圈，有$1$种情况；将三个积木圈串在绳圈上，共有$1$种方案，即$(1\to1)-(2\to2)-(3\to3)-(1\to1)$。绳圈可以翻转，将$(1\to1)-(2\to2)-(3\to3)-(1\to1)$翻转后得到$(1\to1)-(3\to3)-(2\to2)-(1\to1)$，这两个方案视为相同的方案。

综上，$n=3$时共有$2+1+1+1+1=6$种方案。

样例说明2

我有一个绝妙的样例说明，可惜这里太小，我写不下。

数据规模与约定

对于30%的数据，\(n\le10\)；

对于70%的数据，\(n\le200\)；

对于100%的数据，$1\le n\le5000$。