#include <fstream>

using namespace std;
ifstream cin("damesah.in");
ofstream cout("damesah.out");

int dx[]= {-1,-1,-1};
int dy[]= {1,-1,0};
int n,k=1,v[20];

bool ok(int i, int j)
{
    if(i>n || j>n || i<1 || j<1)
        return false;
    return true;
}

bool valid(int x)// X este coloana
{
    int dist,d,i,j,h,y;
    y=v[x];// Y este linia
    for(dist=1; dist<=n; dist++)
        for(d=0; d<3; d++)
        {
            i=x+(dx[d]*dist);// coloana
            j=y+(dy[d]*dist);// linia
            if(ok(i,j)==true)
            {
                if(v[i]==j)
                    return false;
            }
        }
    //v[x]=++y;
    return true;
}

void init()
{
    for(int i=1; i<=n; i++)
        v[i]=1;
}

void afis()
{
    for(int i=1; i<=n; i++)
        cout<<v[i]<<" ";
    cout<<endl;
}

int main()
{
    int sol=0;
    cin>>n;
    init();
    while(k>0)
    {
        if(ok(k,v[k])==true)
        {
            if(valid(k)==true)
            {
                if(k==n)
                {
                    if(sol==0)
                    {
                        afis();
                    }
                    sol++;
                }
                k++;
            }
            else
                v[k]++;
        }
        else
        {
            v[k]=1;
            k--;
            v[k]++;
        }
        //afis();
    }
    cout<<sol;
    return 0;
}