#include<cstring>
#include<cstdio>	         
#include<iostream>  
#include<algorithm>       
using namespace std;
const int mod=1e4,N=2;
struct ma{
	int m[N][N];
};
ma operator * (const ma& a,const ma& b){
	ma c;
	memset(c.m,0,sizeof c.m);
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			for(int k=0;k<N;k++){
				c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
			}
		}
	}
	return c;
}
ma po(ma a,long long n){
	ma ans;
	memset(ans.m,0,sizeof ans.m);
	for(int i=0;i<N;i++){
		ans.m[i][i]=1;
	}
	while(n){
		if(n&1){
			ans=ans*a;
		}
		a=a*a;
		n>>=1;
	}
	return ans;
}
int main(){
	long long n,mm;
	cin>>n>>mm;
	ma a;
	for(int i=0;i<=1;i++){
		a.m[i][0]=1;
		a.m[0][i]=1;
	}
	a.m[1][1]=0;
	ma anns;
	long long ikun=__gcd(n,mm);
	if(ikun<=2){
		cout<<1;
		return 0;
	}
	anns=po(a,ikun);
	cout<<anns.m[1][0]<<endl; 
	
	return 0;
}