#include<bits/stdc++.h>
using namespace std;
const long long mod=100000000;
long long f[10000009];
long long n,m;
int gcd(int a,int b){
	if(b==0) return a;
	return gcd(b,a%b);
}
int main(){
	cin>>n>>m;
	f[1]=1;
	f[2]=1;
	for(int i=3;i<=max(n,m);i++){
		f[i]=(f[i-1]+f[i-2])%mod;
	}
	cout<<f[gcd(n,m)];
	return 0;
}