#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second

int ipow(ll b, int e, int mod){
	int ret = 1;
	for(; e; e >>= 1){
		if(e & 1) ret = ret * b % mod;
		b = b * b % mod;
	}
	return ret;
}

const int ptst = 4;
int p[ptst] = {2, 3, 5, 7};
bool ptest(int x){
	if(x < 4) return x > 1;
	for(int i = 0; i < ptst; i++) if(x % p[i] == 0) return 0;

	int y = x - 1, e = __lg(y & -y);
	y >>= e;
	for(int i = 0; i < ptst; i++){
    	ll z = ipow(p[i] % x, y, x);
    	if(z == 1) continue;
    	for(int i = 0; i < e && z != x - 1; i++) z = z * z % x;
    	if(z != x - 1) return 0;
	}

	return 1;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	cout << ptest(1000000007) << endl;
	cout << ptest(1350451049) << endl;
	cout << ptest(1000696969) << endl;

	return 0;
}