#include<stdio.h>
#include<map>

using namespace std;

int n;

map <int,int> s;

inline int sqr(int k)
{return k*k;}

int solve(int k)
{
	if(s.find(k)!=s.end())
	{
		return s[k];
	}
	int tmp=0;
	if(k%2)
	{
		tmp+=sqr(solve(k>>1));
		tmp+=sqr(solve((k>>1)-1))<<1;
		tmp+=solve(k>>1)*solve((k>>1)-1)<<3;
	}
	else
	{
		tmp+=sqr(solve(k>>1));
		tmp+=solve((k>>1)-1)*solve((k>>1)-2)<<2;
		tmp+=sqr(solve((k>>1)-1))<<2;
	}
	s[k]=tmp%997;
	return tmp%997;
}

int main()
{
	freopen("baga.in","r",stdin);
	freopen("baga.out","w",stdout);
	int i;s[0]=1;s[1]=1;s[2]=5;
	scanf("%d",&n);
	printf("%d\n",solve(n));
	return 0;
}