// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
using namespace std;

const long long MOD = 100007;
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
  int m; cin>>m;
  long long dp2[40002] = {};
  long long dp[40002] = {};
  dp[2] = 1;
  dp[1] = 0;
  dp[3] = 5;
  dp2[3] = 8;
  dp2[0] = 1;
  dp2[1] = 1;
  dp2[2] = 3;
  for (int i = 4; i <= m; i++) {
    dp2[i] = (3*dp2[i-1] - dp2[i-2] ) % MOD;
    dp[i] = (3*dp[i-1] - dp[i-2] + dp2[i-1]-dp2[i-2]) % MOD;
    //cout<<i<<' '<<dp[i]<<' '<<dp2[i-1]<<' '<<dp3[i-1]<<endl;
  }
  if(dp[m-1]<0){ dp[m-1] = (dp[m-1]+MOD)%MOD;}
  cout<<dp[m-1];
}