#include <bits/stdc++.h>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

const int mod = 1000;

struct Mod {
  int n;
  Mod () : n(0) {;}
  Mod (int n) : n(n) {
    if (n >= mod) n %= mod;
    else if (n < mod) n = (n % mod + mod) % mod;
  }
  operator int() { return n; }
};

Mod operator+=(Mod &a, Mod b) { a.n += b.n; if (a.n >= mod) a.n -= mod; return a; }
Mod operator-=(Mod &a, Mod b) { a.n -= b.n; if (a.n < 0) a.n += mod; return a; }
Mod operator*=(Mod &a, Mod b) { a.n = ((long long)a.n * b.n) % mod; return a; }
Mod operator+(Mod a, Mod b) { return a += b; }
Mod operator-(Mod a, Mod b) { return a -= b; }
Mod operator*(Mod a, Mod b) { return a *= b; }

typedef Mod Data;
typedef vector<Data> Array;
typedef vector<Array> Matrix;

Matrix operator*(const Matrix &lhs, const Matrix &rhs) {
  Matrix res(lhs.size(), Array(rhs[0].size(), 0));
  REP(i,lhs.size()) REP(j,rhs[0].size()) REP(k,rhs.size())
    res[i][j] += lhs[i][k] * rhs[k][j];
  return res;
}

Matrix scalar(int size, Data k) {
  Matrix mat(size, Array(size, 0));
  REP(i,size) mat[i][i] = k;
  return mat;
}

Matrix operator^(const Matrix &lhs, const int n) {
  if (n == 0) return scalar(lhs.size(), 1);
  Matrix res = (lhs * lhs) ^ (n / 2);
  if (n % 2) res = res * lhs;
  return res;
}

int main() {
  int n; cin >> n;
  Matrix mat = {{1, 3}, {1, 1}};
  mat = mat ^ n;
  Mod res = mat[0][0];
  cout << res * Mod(2) - Mod(1 - n % 2) << endl;
  return 0;
}