记录编号	152124	评测结果	AAAAAAAAAA
题目名称	小D的背包问题	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2015-03-12 23:39:48	内存使用	0.26 MiB

/***********************************************************************/
/**********************By Asm.Def-Wu Jiaxin*****************************/
/***********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <algorithm>
using namespace std;
FILE *in, *out;
#define SetFile(x) ( in = fopen(#x".in", "r"), out = fopen(#x".out", "w") )
#define SetIO(i, o) ( in = i, out = o )
#define getc() fgetc(in)
template<class T>inline void getd(T &x){
	char ch = getc();bool neg = false;
	while(!isdigit(ch) && ch != '-')ch = getc();
	if(ch == '-')ch = getc(), neg = true;
	x = ch - '0';
	while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
	if(neg)x = -x;
}
/***********************************************************************/
const int mod = 997;

struct Mat{
	int A[16][16];
	inline void operator *= (const Mat &b){
		static int tmp[16][16];
		int i, j, k;
		for(i = 0;i < 16;++i)for(j = 0;j < 16;++j){
			tmp[i][j] = 0;
			for(k = 0;k < 16;++k)
				tmp[i][j] = (tmp[i][j] + A[i][k] * b.A[k][j]) % mod;
		}
		for(i = 0;i < 16;++i)for(j = 0;j < 16;++j)A[i][j] = tmp[i][j];
	}
}F={{{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1},{0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1},{0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0},{0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0},{0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1},{0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0},{0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0},{1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1}}};
/*
bool A[16][16], known[16][16];

bool dfs(int a, int b){
	int i;
	if(known[a][b])return A[a][b];
	for(i = 1;i < 16;i <<= 1)
		if(((a & i) != i) && ((b & i) != i)){known[a][b] = true;return false;}
	if(a == 15 && b == 0)return A[a][b] = known[a][b] = true;
	for(i = 1;i < 16;i <<= 1)
		if(((b & i) == i) && ((a & i) != i))//竖着放置
			if(dfs(a ^ i, b ^ i))return A[a][b] = known[a][b] = true;
	for(i = 3;i < 16;i <<= 1)
		if((b & i) == i)
			if(dfs(a, b ^ i))return A[a][b] = known[a][b] = true;
	known[a][b] = true;
	return false;
}
FILE *tmpout = fopen("tmpo.txt", "w");
inline void init(){
	for(int i = 0;i < 16;++i)for(int j = 0;j < 16;++j)if(!known[i][j])dfs(i, j);
	for(int i = 0;i < 16;++i){
		fprintf(tmpout, "{%d", (int)A[i][0]);
		for(int j = 1;j < 16;++j)fprintf(tmpout, ",%d", A[i][j]);
		fprintf(tmpout, "},");
	}
}*/
int N;
inline void init(){
	getd(N);
	//for(int i = 0;i < 16;++i)for(int j = 0;j < 16;++j)F.A[i][j] = FArr[i][j];
}

inline void work(){
	--N;
	Mat Ans = F;
	while(N){
		if(N & 1)Ans *= F;
		F *= F;
		N >>= 1;
	}
	fprintf(out, "%d\n", Ans.A[15][15]);
}

int main(){

#ifdef DEBUG
	SetIO(fopen("test.txt", "r"), stdout);
#elif !defined ONLINE_JUDGE
	SetFile(baga);
#else
	SetIO(stdin, stdout);
#endif
	init();
	work();

#ifdef DEBUG
	printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}