#include <iostream>
#include <array>

unsigned int fib_mod(unsigned int n, unsigned int m) {using M = std::array<unsigned int, 3>;
    auto mul = [m] (M & me, const M & other) {
        me[2] = ((me[1] * other[1]) % m + (me[2] * other[2]) % m) % m;
        unsigned int me_1 = me[1];
        me[1] = ((me[0] * other[1]) % m + (me[1] * other[2]) % m) % m;
        me[0] = ((me[0] * other[0]) % m + (me_1 * other[1]) % m) % m;
    };
    M r{{1, 1, 0}}, e{{1, 0, 1}}, ans{e};
    while (n) {
        if (n & 1) {
            mul(ans, r);
        }
        mul(r, M(r));
        n /= 2;
    }
    return ans[1];
}

int main() {
    std::cout << fib_mod(1<<31, 1<<31) << std::endl;
    return 0;
}