/*
 * Greater NY Regional 2019
 * Unicycles
 * Fred Pickel
 */
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

typedef unsigned int DWORD;

#ifdef WIN32
typedef __int64 LLONG;
#else
typedef long long LLONG;
#endif

#define MODULUS	100007

#define MAX_N	4000

DWORD fibs[2*MAX_N + 16];

/*
 * cycle v1, ... vn on the outside connect to v0 in the center
 * for each of the following there are n different rotations
 * 1. cycle is v1 ... vn, v1, edge form v1 to v0
 * 2. cycle is v1...vn,v0,v1
 * 3 cycle is v1...v(n-1),v0,v1 3 cases {vn-v(n-1), vn-v1, vn-v0}
 * 4. cycle is v1...v(n-k),v0,v1 need to connect v(n-k+1) ...vn
 * let M(k) = #unicycles with cycle v1 ... v(n-k),v0,v1 (For 0 ... (n-2))
 * by 2, M(0) = 1, by 3, M(1) = 3
 * now look at M(k+1) in terms of M(j) for j <= k
 *	v(n-k) is the addiitonal vertes, with edges to v(n-k-1), v0, v(n-k+1)
 *	A. we can add the edge from v(n-k-1) to v(n-k) to the unicycle and any set of edges that worked
 *	for M(k) note that if the edge from v(n-k+1) to v(n-k) was used to connect to the cycle in M(k)
 *	it now connects to the cycle via the edge from v(n-k-1) to v(n-k)
 *	
 *	B. In exactly the same way, if the edge from v0 to v(n-k) is used we get M(k) spanning unicycles
 *	that is a total of 2*M(k) spanning unicycles
 *
 *	C. what happens if we use neither v(n-k-1)->v(n-k) or v0->v(n-k)?
 *	 v(n-k) has to connect to the cycle thru v(n-k+1)
 *	 there are M(k) unicycles that connect v(n-k+1) ... v(n) EXCEPT
 *	 all those that connect to the cycle via the edge from v(n-k+1)->v(n-k)
 *		by A above applied to M(k) we need to subtract M(k-1) 
 *
 *	So adding A, B and C
 *	M(k+1) = 3*M(k) - M(k-1)m(0 = 1 M(1) = 3 By induction M(n) = Fib(2*n-2) with Fib(1) = Fib(2) = 1
 *
 *  So total unicycles = (rotations) * (unicycles in one rotation)
 *		= n*(1 + M(0) + M(1) + ... + M(n-2)) = (by induction again) n*Fib(2*n-1)
 */

typedef struct _mat_
{
	LLONG a;
	LLONG b;
	LLONG c;
	LLONG d;
} MAT;

typedef struct _vec_
{
	LLONG x;
	LLONG y;
} VEC;

MAT base = { 1, 1, 1, 0 };
VEC bvec = {1, 1 };

// raise mat to power pow (mod MODULUS) and mult by vec, return index of result
LLONG matPowVec(MAT *mat, VEC *vec, int pow, int index)
{
	MAT mres, fact;
	VEC res, tmp;
	int i;
	res = *vec;
	fact = *mat;
	for(i =1; i <= pow; i *= 2) {
		if((i & pow) != 0) {
			tmp.x = (fact.a*res.x + fact.b*res.y) % MODULUS;
			tmp.y = (fact.c*res.x + fact.d*res.y) % MODULUS;
			res = tmp;
		}
		mres.a = (fact.a * fact.a + fact.b*fact.c) %MODULUS;
		mres.b = (fact.a * fact.b + fact.b*fact.d) %MODULUS;
		mres.c = (fact.c * fact.a + fact.d*fact.c) %MODULUS;
		mres.d = (fact.c * fact.b + fact.d*fact.d) %MODULUS;
		fact = mres;
	}
	if(index == 0) {
		return res.x;
	} else {
		return res.y;
	}
}

// compute Fib with powers of mat {1 1} {1 0}} and vec {1 1}
// Fib(n) = first coord of mat^(n-1)*vec
LLONG quickFib(int n) 
{
	if(n <= 2) return 1;
	return matPowVec(&base, &bvec, n - 2, 0);
}

DWORD unicyc(int n)
{
	int fibin = 2*n-1;
	LLONG ret;
	ret = quickFib(fibin);
	return (DWORD)((n * ret) % MODULUS);
}

char inbuf[256];

int main()
{
	int n;
	DWORD cnt;

	fibs[1] = fibs[2] = 1;
	if(scanf("%d", &n) != 1){
		fprintf(stderr, "scan failed on data\n");
		return -3;
	}
	if((n < 3) || (n > MAX_N)) {
		fprintf(stderr, "wheel size %d not in range 1 ... %d\n", n, MAX_N);
		return -5;
	}
	cnt = unicyc(n);
//	fcnt = QFib2n_1(n);
	printf("%u\n", cnt);
	return 0;
}