#include <iostream>
#include <cassert>
#include <chrono>
#include <random>

typedef long long ll;

const int mod = 2147483647;

// Calculate x % (2^31-1) fast
// 0 <= x <= (2^31-2)^2
inline int fast_mod(ll value) {
    value = (value >> 31) + (value & mod);
    value = (value >> 31) + (value & mod);
    return value == mod ? 0 : value;
}

int main() {
    auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
    std::mt19937 mt_rand(seed);
    std::uniform_int_distribution<ll> dis(ll(1e9), ll(1e18));

    for (int n = 0; n < 100000000; ++n) {
        ll value = dis(mt_rand);
        assert(value % mod == fast_mod(value));
    }
    std::cout << "ok!";
    return 0;
}