Problem Description

将N个点排列成一个圆形，中间放置一个点固定为根节点，问特殊生成树的种类数。

特殊生成树：除根节点以外，其他节点只能与自己左右节点相连，或与根节点相连。

p.s.若节点的左右节点为同一个节点，向左或向右连接视为不同的生成树。

由于种类数可能过大，对1,000,000,007取模。

当N=3时，所有生成树表示如下：

Input

多组数据，请输入要文件结束。

每组数据包含一个整数N(0<N<109)。

Output

对于每组数据，输出一个整数，表示特殊生成树的种类数，答案对1,000,000,007取模。

Example

Input

2
3

Output5

16

首先根据这个数据规模就可以看出需要找规律（递推关系）。
设根节点为0，其他为1~n。（注意题目的隐藏条件是至少有一条边与0相连）
观察到当有n-1个点的关系时，再添第n个点有3种可能（n和0或n和1或n和n-1）故3*f（n-1）
但是当原n-1个点当中，1和n-1相连的话，就少了一种可能。即1和n-1那条边变成其中一个与n相连。n只能连0和另一个点。判断这种情况的总数为n-2个点的时候新增的点与1相连，即f（n-2）
最后原来n-1个点中有一种情况是f（n-1）所不具备的。即n-1个点成一个环，不与0相连，这时候n必须要与0相连，然后取1或n-1与n相连。为2种。
故f（n）= 3*f（n-1）-f（n-2）+2；
之后构造矩阵
【5,1,2】*【3,1,0
　　　　　　-1,0,0
　　　　　　1,0，1】
求出答案矩阵的左上角即可。
AC代码如下（注意开long long，以及可能（一定会）出现的负数）：

#include <algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#define MOD 1000000007
using namespace std;
typedef long long ll;
int n,out;
struct matrix{
    ll m[3][3];
};
matrix Mul(const matrix &a,const matrix &b){//a*b
    matrix c;
    memset(c.m,0,sizeof(c.m));
    for(int i =0;i<3;i++)
        for(int j=0;j<3;j++){
            c.m[i][j]=0;
            for(int k=0;k<3;k++){
                c.m[i][j]+=(a.m[i][k]*b.m[k][j])%MOD;
            }
            c.m[i][j]%=MOD;
        }
    return c;
}
matrix Quick_pow(matrix a,int n){//快速幂 
    matrix c;
    memset(c.m,0,sizeof(c.m));
    for(int i=0;i<3;i++)
        c.m[i][i]=1;
    while(n){
        if(n&1)
            c=Mul(c,a);
        a=Mul(a,a);
        n>>=1;
    }
    return c;
}
int main(){
    matrix a,ans;
    memset(a.m,0,sizeof(a.m));
    a.m[0][0]=3, a.m[0][1]=a.m[2][0]=a.m[2][2]=1, a.m[1][0]=-1;//构造转换矩阵 
    while(~scanf("%d",&n)){
        if(n==1){
            printf("1\n"); 
            continue;
        }
        ans=Quick_pow(a,n-2);
        out=((ans.m[0][0]*5%MOD+ans.m[1][0]*1%MOD+ans.m[2][0]*2%MOD)%MOD+MOD)%MOD;//直接手动计算了一下答案矩阵【0】【0】位置的值 ，注意保证不为负数 
        printf("%d\n",out);
    }
}