#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <vector>

#include <cstring>

#include <set>

#include <map>

using namespace std;

typedef long long ll;

inline void r(ll&num){

    num=;ll f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<='')num=num*+ch-'',ch=getchar();

    num*=f;

}

inline void r(int &num){

    num=;int f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<='')num=num*+ch-'',ch=getchar();

    num*=f;

}

const long long N = ;

const long long M = 1e9+;

struct Matr

{

    long long line;

    long long a[N+][N+];

    Matr(){

        line=;

        a[][] = ; a[][] = ;

        a[][] = ; a[][] = ;

    }

};

Matr isit(Matr x,long long c)  //矩阵初始化

{

    for(long long i=;i<N;i++)

        for(long long j=;j<N;j++)

            x.a[i][j]=c;

    return x;

}

Matr Matlab(Matr x,Matr s)  //矩阵乘法

{

    Matr ans;

    ans.line = x.line;

    ans=isit(ans,);

    for(long long i=;i<x.line;i++)

    {

        for(long long j=;j<x.line;j++)

        {

            for(long long k=;k<s.line;k++)

            {

                ans.a[i][j] = (ans.a[i][j]+x.a[i][k]*s.a[k][j])%M;

                ans.a[i][j]=(ans.a[i][j]+M)%M;

            }

        }

    }

    return ans;

}

long long Fast_Matrix(Matr tmp,long long n)

{

    if(n==)

        return ;

    if(n==)

        return ;

    if(n==)

        return ;

    n--;

    Matr ans,ch;

    ans.line = ;

    ans.a[][] = ;

    ans.a[][] = ;

    ans.a[][] = ;

    ans.a[][] = ;

    while(n>)

    {

        if(n%)

        {

            ans=Matlab(ans,tmp);

        }

        tmp=Matlab(tmp,tmp);

        n/=;

    }

    return (ans.a[][]+ans.a[][])%M;

}

int main()

{

    Matr T;

    long long n;

    cin>>n;

    long long x = Fast_Matrix(T,n);

    cout<<(x*x+(n&))%M<<endl;

    return ;

}