一个含有 $n$ 个顶点的有向图被称为竞赛图（tournament），如果满足以下条件：

• 顶点编号为 $1$ 到 $n$。
• 对于每对顶点 $1 \le u < v \le n$，恰好有一条边连接 $u$ 和 $v$，且该边的方向要么是 $u \to v$，要么是 $v \to u$。

因此，总共存在 $2^{n(n-1)/2}$ 个含有 $n$ 个顶点的竞赛图。Snuke 画出了所有含有 $n$ 个顶点的竞赛图，并对其中的每一个图计算了其强连通分量（strongly connected components）的数量。

计算 Snuke 计算出的所有 $2^{n(n-1)/2}$ 个值的总和，结果对 $1,000,000,007$ 取模。

输入格式

输入包含一个整数 $n$。

数据范围

• $1 \le n \le 10^5$

输出格式

输出该总和对 $10^9 + 7$ 取模后的结果。

样例

输入样例 1

3

输出样例 1

20

输入样例 2

21

输出样例 2

736073462

说明

对于第一个样例，总共有 8 个竞赛图。其中两个图只有 1 个强连通分量，其余的图有 3 个强连通分量。答案为 $1 \times 2 + 3 \times 6 = 20$。