Drawing Edges

n labeled vertices form an undirected simple graph with no self-loops and no multiple edges; the graph may be disconnected. Find the number of distinct graphs modulo 1000000007.

输入格式

One line containing n. On this site 1≤n≤10^9.

输出格式

Output one integer, the answer.

样例 1

输入：

4

输出：

64

样例 2

输入：

1

输出：

1

样例 3

输入：

3

输出：

8

样例说明

The examples give 64, 1 and 8 respectively; with one vertex, only the edgeless graph exists.