#include <bits/stdc++.h>
#include "ancient2.h"
using namespace std;
int Query(int m, std::vector<int> a, std::vector<int> b);
#define rep(i,l,r) for(int i(l);i<=(r);++i)
#define per(i,r,l) for(int i(r);i>=(l);--i)
#define eb emplace_back
#define Debug(...) fprintf(stderr,__VA_ARGS__)
const int N = 1e3 + 7, M = 1e2 + 2, L = 1e2 + 7;
typedef long long ll;
typedef vector<int> vi;
typedef bitset<N> bit;

int n, m;
vi a, b;
string str;


struct Basis {
    vector<pair<int, bit>>S;
    bool ins(bit cur) {
        for (auto &[ft, bt] : S)
            if (cur.test(ft))
                cur ^= bt;

        if (cur.any())
            return S.eb(cur._Find_first(), cur), 1;
        else
            return 0;
    }
    int size() {
        return S.size();
    }
};

vector<tuple<int, int, bit>>buc[L], qmd;
vector<pair<int, bit>>qft, qbk;

vector<bit>mar;

string Solve(int _n) {
    n = _n;
    auto getmd = [&]() {
        bit sit;
        rep(x, 1, M >> 1)rep(r, 0, x - 1) {
            rep(i, 0, n - 1)sit.set(i, i % x == r);
            buc[2 * x].eb(x, r, sit);
        }
    };
    auto getft = [&]() {
        bit sit;
        rep(i, 0, M - 3) {
            rep(j, 0, n - 1)sit.set(j, j == i);
            buc[i + 3].eb(-1, i, sit);
        }
    };
    auto getbk = [&]() {
        bit sit;
        rep(i, 0, M - 2) {
            rep(j, 0, n - 1)sit.set(j, j == (n - 1 - i));
            buc[i + 2].eb(-2, i, sit);
        }
    };
    auto merge = [&]() {
        Basis tmp;

        rep(i, 1, M)for (auto &[x, r, s] : buc[i]) {
            if (tmp.size() == n)
                break;

            if (tmp.ins(s)) {
                // Debug("%d %d ",x,r);
                // for(int j=0;j<n;j++)Debug("%d",s.test(j));
                // Debug("\n");
                if (x == -1)
                    qft.eb(r, s);
                else if (x == -2)
                    qbk.eb(r, s);
                else
                    qmd.eb(x, r, s);
            }
        }
    };
    getft(), getmd(), getbk(), merge();


    auto qryft = [&]() {
        auto loop = [&](int i) {
            a[i] = i, b[i] = i;
        };

        for (auto &[p, s] : qft) {
            m = p + 3;
            a.resize(m), b.resize(m);
            rep(j, 0, p - 1)a[j] = b[j] = j + 1;
            a[p] = p + 1, b[p] = p + 2;
            loop(p + 1), loop(p + 2);
            auto cur = s;
            cur.set(n, Query(m, a, b) == p + 2);
            mar.eb(cur);
        }
    };
    auto qrybk = [&]() {
        vi res;

        for (auto &[p, s] : qbk) {
            res.insert(res.begin(), 0);
            m = p + 2;
            a.resize(m), b.resize(m);
            auto get = [&](int v, int _p, int i) {
                auto cur = vi(res.begin(), res.begin() + i);
                cur.push_back(v);
                per(j, min(_p + 1, i + 1), 1)

                if (vi(cur.end() - j, cur.end()) == vi(res.begin(), res.begin() + j))
                    return j;

                return 0;
            };
            rep(i, 0, p + 1)a[i] = get(0, p, i), b[i] = get(1, p, i);
            auto cur = s;
            cur.set(n, (res[0] = (Query(m, a, b) != p + 1)));
            mar.eb(cur);
        }
    };
    auto qrymd = [&]() {
        for (auto &[x, r, s] : qmd) {
            m = 2 * x;
            a.resize(m), b.resize(m);
            rep(j, 0, x - 1)a[j] = b[j] = (j + 1) % x, a[j + x] = b[j + x] = (j + 1) % x + x;
            swap(b[r], b[r + x]);
            auto cur = s;
            cur.set(n, Query(m, a, b) >= x);
            mar.eb(cur);
        }
    };
    auto solve = [&]() {
        rep(i, 0, n - 1) {
            int k = -1;

            rep(j, i, n - 1)if (mar[j].test(i)) {
                k = j;
                break;
            }

            // Debug("%d\n",k);
            swap(mar[i], mar[k]);

            rep(j, 0, n - 1)if (j != i && mar[j].test(i))
                mar[j] ^= mar[i];
        }
        str.resize(n);
        rep(i, 0, n - 1)str[i] = mar[i].test(n) + '0';
        // Debug("%s\n",str.c_str());
    };


    qryft(), qrymd(), qrybk();
    solve();
    // for(auto bt:mar){for(int j=0;j<n;j++)Debug("%d",bt.test(j));Debug(" %d\n",bt.test(n));}

    return str;
}