#include <fstream>

using namespace std;

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


int e_sol(int st[], int k, int n)
{
    if (k==n)
        return 1;
    return 0;
}

int suc(int st[], int k, int n)
{
    if (st[k]==n+1)
        return 0;
    return 1;
}

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

int main()
{
    int n;
    fin>>n;
    int k=1, contor=0;
    int st[n+1];
    st[1]=0;
    while(k)
    {
        do
        {
            st[k]++;
        }while(suc(st, k, n) && !e_valid(st, k));
        if (suc(st, k, n))
        {
            if (e_sol(st, k, n))
            {
                if (!contor)
                    for (int i=1; i<=n; i++) fout<<st[i]<<" ";
                contor++;
            }
            else
            {
                k++;
                st[k]=0;
            }
        }
        else
        {
//            st[k]=0;
            k--;
        }
    }
    fout<<"\n"<<contor;


    return 0;
}