[Clover 10]铁路历险

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 railwaya.in 输出文件 railwaya.out

【题目描述】

经过一番努力，Freda和Rainbow来到了魔力铁路的1号站台。它们知道，魔力铁路不同于普通的铁路，下面有一段关于魔力铁路的介绍。

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

Rainbow 和Freda想知道，有多少种不同的规定x[i]的方案，使得它们能够到达N号站台呢？方案A、B不同的条件是：存在一个i（1<=i<=N）使得方案A中的x[i]与方案B中的x[i]不同。Freda最讨厌乱七八糟的上万位数字了，所以，记得把答案 mod 1000000007（10^9+7）哦lala~


【输入格式】

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

【输出格式】

一行一个整数Ans，表示Freda和Rainbow能够到达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.

每个测试点1s

【来源】

From - This_poet

Contact me - This_poet@126.com/Freda.RD.Shi@gmail.com

This_poet's Blog - http://thispoet.blogcn.com