#include<conio.h>
#include<math.h>
#include<vector>
#include<string>
#include<fstream>
#include<iostream>
#include<istream>
#include <limits>
#include<algorithm>
#include<cctype>
#include<deque>
#include<iterator>
#include <bitset>
using namespace std;


int main() {

    std::ios::sync_with_stdio(false);
    cin.tie(0);

    //freopen("num2perm.in", "r", stdin);
    //freopen("num2perm.out", "w", stdout);

    int n;

    cin >> n;
    unsigned long long **mas;
    mas = new unsigned long long *[10];
    for (int i = 0; i < 10; i++) {

        mas[i] = new unsigned long long int[n];
    }
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < n; j++) {
            mas[i][j] = 0;
        }
    }
    for (int i = 0; i < 10; i++) {
        if (i == 0 || i == 8) {
            mas[i][0] = 0;
        }
        else {
            mas[i][0] = 1;
        }
    }

/*  for (int i = 0; i < 10; i++) {
        for (int j = 0; j < n; j++) {
            cout << mas[i][j] << " ";
        }
        cout << endl;
    }*/
    //mas[12][n];
    // mas[i][n-1]
    //mas[4][k]= mas[0][k-1]+mas[3][k-1] +mas[9][k-1];
    unsigned long long count = 0;
    for (int i = 1; i < n; i++) {
        mas[0][i] = (mas[4][i-1 ] + mas[6][i-1])% 1000000000;
        mas[1][i] = (mas[6][i - 1] + mas[8][i - 1])%1000000000;
        mas[2][i] = (mas[7][i - 1] + mas[9][i - 1]) % 1000000000;
        mas[3][i] = (mas[4][i - 1] + mas[8][i - 1]) % 1000000000;
        mas[4][i] = (mas[0][i - 1] + mas[3][i - 1]+mas[9][i-1]) % 1000000000;
        mas[6][i] = (mas[0][i - 1] + mas[1][i - 1]+mas[7][i-1]) % 1000000000;
        mas[7][i] = (mas[2][i - 1] + mas[6][i - 1]) % 1000000000;
        mas[8][i] = (mas[1][i - 1] + mas[3][i - 1]) % 1000000000;
        mas[9][i] = (mas[2][i - 1] + mas[4][i - 1]) % 1000000000;

    }


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

        count = (count + mas[i][n - 1])% 1000000000;

        }

    count = count % 1000000000;
    cout << count;

    return 0;
}