#include <bits/stdc++.h>
int n, m, g, a = 1, b = 1;
int main() {
	scanf("%d %d", &n, &m);
	g = std::__gcd(n, m) % 150000000;
	for (int i = 2; i <= g + 1 >> 1; i++) {
		a = (a + b) % 100000000;
		b = (a + b) % 100000000;
	}
	if (g & 1)
		printf("%d\n", a);
	else
		printf("%d\n", b);
	return 0;
}

如果我这样写一定要判断 ${g}$ 的奇偶， 当我只输出 ${b}$ 时也能过

所以 ${\forall g\equiv0\pmod{2}}$, 没有${g\equiv1\pmod{2}}$ 的情况