#include <fstream>

using namespace std;
ifstream fin ("platforma.in");
ofstream fout ("platforma.out");

const int NMAX = 15000;

int main()
{
    int test;
    fin >> test;

    if(test == 1)
    {
        int n, v[NMAX + 5];
        fin >> n;

        int i = 0;
        long long x;
        while(fin >> x)
        {
            if(x > n)
            {
                fout << 0;
                return 0;
            }

            v[++i] = x;

            if(i > n)
            {
                fout << 0;
                return 0;
            }
        }

        bool ok = true;

        for(int i = 1; i < n; i++)
        {
            if(i == v[i] and i + 1 == v[i + 1])
                continue;

            if(i == v[i] and i == v[i + 1])
            {
                int nr = i, ap = nr, cnt = 0;

                while(i <= n and v[i++] == nr)
                    cnt++;

                i--;

                if(cnt != ap)
                {
                    ok = false;
                    break;
                }
            }
            else
            {
                ok = false;
                break;
            }
        }

        fout << ok;
    }

    if(test == 2)
    {
        int n;
        fin >> n;

        long long dp[NMAX + 5];
        dp[1] = 1;
        for(int i = 2; i <= n; i++)
        {
            dp[i] = dp[i - 1];

            if(i % 2 == 1)
                dp[i] = 0LL + dp[i] + dp[(i + 1) / 2 - 1];
        }

        fout << dp[n];
    }

    if(test == 3)
    {
        int n, ord;
        fin >> n >> ord;

        long long dp[NMAX + 5];
        dp[n] = 1;
        for(int i = n; i >= 1; i--)
        {
            dp[i - 1] = 0LL + dp[i - 1] + dp[i];

            if(i % 2 == 1)
                dp[(i + 1) / 2 - 1] = 0LL + dp[(i + 1) / 2 - 1] + dp[i];
        }

        int v[NMAX + 5];
        v[1] = 1;

        for(int i = 2; i <= n; i++)
        {
            if(dp[n - (2 * i) - 1] >= ord)
                v[i] = v[i - 1];
            else if(dp[n - (2 * i) - 1] < ord)
            {
                ord -= dp[n - (2 * i) - 1];
                v[i] = i;
            }
        }

        for(int i = 1; i <= n; i++)
            fout << v[i] << ' ';
    }
    /*
        if(test == 4)
        {
            int n;
            fin >> n;
            for(int i = 1; i <= n; i++)
                fin >> v[i];

            long long dp[NMAX + 5];
            dp[n] = 1;
            for(int i = n; i >= 1; i--)
            {
                dp[i - 1] = 0LL + dp[i - 1] + dp[i];

                if(i % 2 == 1)
                    dp[(i + 1) / 2 - 1] = 0LL + dp[(i + 1) / 2 - 1] + dp[i];
            }

            int ord = 1;

            for(int i = 2; i <= n; i++)
            {
                if(v[i] == v[i + 1])
                {
                    int nr = v[i];
                    while(nr == v[i])
                    ord += ();
            }//
        }*/

    fin.close();
    fout.close();
    return 0;
}