#include <iostream>
#include <fstream>
#include <bitset>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int n, cont;
pair <int,int> regina[20];
bitset <20> col;
bitset <40> dp, ds;

void afisare()
{   cont++;
    if(cont==1)
        for(int i=1;i<=n;i++)
            g<<regina[i].second<<' ';
}
inline int mabs(int x) //inline pt optimiazare
{   if(x<0) return -x;
    return x;
}

void back(int linie)
{   if(linie==n+1)
    {   afisare();
        return;
    }
    for(int coloana=1; coloana<=n;coloana++)
        if(!col[coloana] && !dp[linie+coloana-1] && !ds[linie+n-coloana])//in loc de functia valid , in O(1)
        {   regina[linie]=make_pair(linie, coloana);
            //actualizam, adica punem 1
            col[coloana]=1;
            dp[linie+coloana-1]=1;
            ds[linie+n-coloana]=1;
            back(linie+1);
            //dupa ce s-a facut back-ul, golim, punem 0
            col[coloana]=0;
            dp[linie+coloana-1]=0;
            ds[linie+n-coloana]=0;

        }
}
int main()
{   f>>n;
    back(1);
    g<<'\n'<<cont;
    return 0;
}