题目描述

经过一番努力，你终于来到了魔力铁路的 1 号站台。

魔力铁路不同于普通的铁路，下面有一段关于魔力铁路的介绍。

魔力铁路一共有 N 座站台，从第 i(1<i<=N)号站台出发可以到达第 i-1 号站台。同时，对于每个 i(1<=i<=N)，你需要规定 x[i]为 1~N 当中的任意一个数字，表示从第 i 号站台出发可以到达的另外一个站台，当然，你也可以把 x[i]规定为 i 或者 i-1。

你想知道，有多少种不同的规定 x[i]的方案，使得你能够到达 N 号站台呢？方案 A、B 不同的条件是：存在一个 i（1<=i<=N）使得方案 A 中的 x[i]与方案 B 中的x[i]不同。

你最讨厌乱七八糟的上万位数字了，所以，记得把答案 mod 1000000007（10^9+7）

输入格式

一行一个整数 N，表示站台的总数。

输出格式

一行一个整数 Ans，表示你能够到达 N 号站台的方案数。

样例输入

3

样例输出

12

样例解释

12 种可能的方案如下(每行代表一种方案)：

x[1] x[2] x[3]
2 3 1
2 3 2
2 3 3
3 1 1
3 1 2
3 1 3
3 2 1
3 2 2
3 2 3
3 3 1
3 3 2
3 3 3

数据范围与约定

对于 30%的数据，N<=5.

对于 50%的数据，N<=10.

对于 70%的数据，N<=100.

对于 100%的数据，0<N<=5000