#include <fstream>

using namespace std;

ifstream fin("backtracking.in");
ofstream fout("backtracking.out");

int n,st[102],k,as,nrsol;

void init()
{
    st[k]=0;
}

bool succesor()
{
    if (st[k]<n)
    {
        st[k]++;
        return 1;
    }
    return 0;
}

bool valid()
{
    for (int i=1;i<k;i++)
        if (st[k]==st[i] || k-i==st[k]-st[i] || k-i==st[i]-st[k]) return 0;
    return 1;
}

bool sol()
{
    return (k==n);
}

void afisare()
{
    for (int i=1;i<=n;i++)
        fout << st[i] << " ";
    fout << "\n";
}

int main()
{
    fin >> n;

    k=1;
    init();

    while (k)
    {
        do
        {
            as=succesor();
        }while (as && !valid());

        if (as)
            if (sol())
            {
                if (!nrsol)afisare();
                nrsol++;
            }
            else
            {
                k++;
                init();
            }
        else k--;
    }
    fout << nrsol;
    return 0;
}