#include <iostream>
#include <cstring>
#define mod 10e8
#define ll long long

using namespace std;

int a, b;

struct S{
    ll a[2][2];
};

int gcd(int a, int b){
    int c;
    while (a % 2 == 0 && ((b & 2) != 0)){
        a = a / 2;
        b = b / 2;
    }
    while (a != b){
        if (a > b){
            c = a - b;
            a = c;
        }
        else {
            c = b - a;
            b = c;
        }
    }
    return c;
}

S S_mull(S x, S y)  {
    S res;
    memset(res.a, 0, sizeof(res.a));
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++) {
                res.a[i][j] += x.a[i][k] * y.a[k][j];
                res.a[i][j] %= int(mod);
            }
    return res;
}
ll fib(int n) {
    S c, res;
    c.a[0][0] = c.a[0][1] = c.a[1][0] = 1;
    c.a[1][1] = 0;
    memset(res.a, 0, sizeof(res.a));
    for (int i = 0; i < 2; i++) {
        res.a[i][i] = 1;
    }
    while (n) {
        if (n & 1) res = S_mull(res, c);
        c = S_mull(c, c);
        n >>= 1;
    }
    return res.a[0][0];
}

int main(){
    cin >> a >> b;
    cout << gcd(fib(a), fib(b)) % int(mod) << endl;
    return 0;
}```