#include <bits/stdc++.h>
#define N 15
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");

int x[N];
int n;
bool viz[N];

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

}

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

bool gata;
int ct;

void backt(int k)
{
    int i;
    for(i=1;i<=n;++i)
        if(!viz[i])
    {
        viz[i]=1;
        x[k]=i;
        if(valid(k))
            if(k<n)backt(k+1);
            else if(gata==0){afisare();gata=1;ct++;}
                 else ct++;

        viz[i]=0;

    }

}

int main()
{
    fin>>n;
    backt(1);
    fout<<"\n";
    fout<<ct;




    return 0;
}