Plant 矩阵快速幂，，，，有点忘了

题目链接：https://codeforces.com/contest/185/problem/A

题目大意就是求n次以后  方向朝上的三角形的个数

以前写过这个题，但是忘了怎么做的了，，，又退了一遍，发现第n次后  总个数为2^n+(2^n+!)/2个，，但是部分数据过不去，可能是卡long long 把，然后看了其他人写的。

规律  每一次分解 朝上的三角形可以分解为 新的3个朝上的三角形和一个朝下的三角形，朝下的三角形可以分解为3个朝下的新三角形和一个朝上的三角形

所以  b(n)=3*b(n-1)+a(n-1)....　　a(n)=3*a(n-1)+b(n-1);

构造矩阵

3  1

1  3

b(n-1)  0;

a(n-1)  0

OVER

//n  b(shang)   s(xia)

//0    1            0

//1         3            1

//2    10            6

//b(1)=1

//a(1)=3

//bn=3b(n-1)+a(n-1);

//an=3a(n-1)+b(n-1);

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod=1e9+;

struct stu{

    ll arr[][];

};

stu mul(stu x,stu y){

    stu ans;

    memset(ans.arr,,sizeof(ans.arr));

    for(int i=;i<;i++){

        for(int j=;j<;j++)

            for(int k=;k<;k++){

                ans.arr[i][j]=(ans.arr[i][j]%mod+(x.arr[i][k]%mod*y.arr[k][j]%mod)%mod)%mod;

            }

    }

    return ans;

}

stu ksm(stu x ,ll y){

    stu res;

    memset(res.arr,,sizeof(res.arr));

    for(int i=;i<;i++){

        res.arr[i][i]=;

    }

    while(y){

        if(y&)    res=mul(res,x);

        x=mul(x,x);

        y>>=;

    }

    return res;

}

int main(){

    stu ans,a;

    a.arr[][]=;

    a.arr[][]=;

    a.arr[][]=;

    a.arr[][]=;

    memset(ans.arr,,sizeof(ans.arr));

    ans.arr[][]=;

    ll n;

    cin>>n;

    if(n==){

        cout<<<<endl;

    }

    else {

        ans=ksm(a,n-);

        ans=mul(ans,a);

        cout<<ans.arr[][]%mod<<endl;

    }

    return ;

}