#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
struct mt{
	int n,m;
	vector<vector<int> > matrix;
	mt(int n,int m,vector<vector<int> > matrix){
		this->n=n;
		this->m=m;
		this->matrix=matrix;
	}
	mt mul(mt other){
		vector<vector<int> > res(this->n,vector<int>(other.m,0));
		for(int i=1;i<=this->n;i++)
			for(int j=1;j<=other.m;j++)
				for(int x=1;x<=this->m;x++)
					res[i-1][j-1]+=this->matrix[i-1][x-1]*other.matrix[x-1][j-1];
		return {this->n,other.m,res};
	}
	void print(){
		cout<<this->n<<" "<<this->m<<endl; 
		for(int i=0;i<this->n;i++){
			for(int j=0;j<this->m;j++){
				cout<<this->matrix[i][j]<<" "<<i<<" "<<j<<endl;
			}
		}
		cout<<endl;
	}
};
mt qp(mt a,int b){
	if(b==0){
		vector<vector<int> > vt(a.m,vector<int>(a.m,0));
		for(int i=0;i<a.m;i++)
			vt[i][i]=1;
		return mt(a.m,a.m,vt);
	}
	if(b==1){
		a.matrix[0][0]%=32768;
		a.matrix[0][1]%=32768;
		a.matrix[1][0]%=32768;
		a.matrix[1][1]%=32768;
		return a;
	}
	mt t=qp(a,b/2);
	t.matrix[0][0]%=32768;
	t.matrix[0][1]%=32768;
	t.matrix[1][0]%=32768;
	t.matrix[1][1]%=32768;
	mt res=t.mul(t).mul(qp(a,b%2));
	return res;
}
int main(){
	int n;
	cin>>n;
	if(n<3){
		cout<<1;
		return 0;
	}
	mt a={1,2,{{1,1}}},b={2,2,{{0,1},{1,1}}};
	a=a.mul(qp(b,n-2));
	a.matrix[0][0]%=32768;
	a.matrix[0][1]%=32768;
	cout<<a.matrix[0][1];
	return 0;
}

求斐波那契数列第n项,n<=1e9