//String Mood - problema cu exponentierea matricii
#include 
using namespace std;
const long long MOD = 1e9 + 7;
long long sol_HH = 1, sol_HS = 0;
long long c_HH = 19, c_HS = 7, c_SH = 6 , c_SS = 20;
void update_sol()
{
    long long a = ((sol_HH * c_HH) % MOD + (sol_HS * c_SH) % MOD) % MOD;  ///HAPPY - HAPPY
    long long b = ((sol_HH  * c_HS) % MOD + (sol_HS * c_SS) % MOD) % MOD;  ///HAPPY - SAD
    sol_HH = a;
    sol_HS = b;
}

void update_current()
{
    long long a = ((c_HH * c_HH) % MOD + (c_HS * c_SH) % MOD ) % MOD; /// HAPPY - HAPPY
    long long b = ((c_HH * c_HS) % MOD + (c_HS * c_SS) % MOD ) % MOD; /// HAPPY - SAD
    long long c = ((c_SH * c_HH) % MOD + (c_SS * c_SH) % MOD ) % MOD; /// SAD -  HAPPY
    long long d = ((c_SH * c_HS) % MOD + (c_SS * c_SS) % MOD ) % MOD;  /// SAD - SAD
    c_HH = a;
    c_HS = b;
    c_SH = c;
    c_SS = d;
}

int main()
{
    unsigned long long n ;
    cin>>n;
    while(n!=0)
    {
        if(n%2==1)
            update_sol();

        update_current();

        n/=2;
    }
    cout<