#include<bits/stdc++.h>
using namespace std;

const long double Phi = (sqrtl(5) - 1) / 2;
const int mod = 1e8;
struct dou {
		unsigned long long one, phi;
	public:
		dou(int a = 0, int b = 0) {
			one = a;
			phi = b;
		}
		inline void operator=(dou x) {
			one = x.one % mod;
			phi = x.phi % mod;
		}
		inline dou operator+(dou x) {
			return dou(one + x.one, phi + x.phi);
		}
		inline dou operator*(dou x) {
			/*
			(a+b*phi)+(x+y*phi) = xa+ xb*phi+ya*phi-yb+yb*phi
			                    = (xa-yb) + (xb+ya+yb)*phi
			*/
			return dou(x.one * one + x.phi * phi, x.one * phi + x.phi * one - x.phi * phi );
		}
		inline long double to_ldouble() {
			return one + Phi * phi;
		}
};
inline dou quick_pow(int n) {
	dou ans(1, 0);
	dou aa(1, 1);
	while (n) {
		if (n & 1)ans = ans * aa;
		n >>= 1;
		aa = aa * aa;
	}
	return ans;
}
int main() {
	int a, b;
	cin >> a >> b;
	cout << quick_pow( __gcd(a, b) ).phi;
	return 0;
}