#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e8;
int x,y;
struct node {
	int n,m;
	int z[4][4];
	node() {
		memset(z,0,sizeof(z));
	}
} ans,id;
node operator * (const node & a,const node & b) {
	node c;
	c. n = a.n;
	c.m = b.m;
	for(int i =1; i <= 2 ; i ++)
		for(int k = 1; k <= 2; k ++)
			for(int j = 1; j <= 2; j ++)
				c.z[i][j] = (c.z[i][j] + a.z[i][k] * b.z[k][j]) % mod;
	return c;

}
int gcd(int a,int b) {
	if(b == 0) return a;
	else return gcd(b,a % b);
}
inline int read() {
	int x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9') ch = getchar();
	while(ch >= '0' && ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x;
}
void init() {
	id.n = id.m = 2;
	id.z[1][2] = id.z[2][2] = id.z[2][1] = 1;
	ans.n = 1;
	ans.m = 2;
	ans.z[1][1] = ans.z[1][2] = 1;
}
node ksm(node base,int power) {
	node res;
	res.n = res.m = 2;
	res.z[1][1] = res.z[2][2] = 1;
	while(power) {
		if(power & 1) {
			ans = ans * base;
			
		}
		base = base * base;
		power = power >> 1;
	}
	return res;
}
signed main() {
	x = read();
	y = read();
	int  g = gcd(x,y);
	init();
	id = ksm(id,g - 2);
	cout << ans.z[1][2];
	return 0;
}