#include <bits/stdc++.h>

using namespace std;
/***********************************************************/
ifstream f("damesah.in");
ofstream g("damesah.out");
/***********************************************************/
const int nmax = 16;
bool amGasitPrimaSol;
int n;
int col[nmax];
int diag_1[2*nmax];
int diag_2[2*nmax];
int rasp[nmax];
int r;
/***********************************************************/
///------------------------------------------------------------------
inline void readInput()
{
    f>>n;
}
///------------------------------------------------------------------
bool Verificare(int i, int  j)
{
    if(col[j] == 0 && diag_1[j-i+n] == 0 && diag_2[i+j] == 0)
    {
        return true;
    }
    return false;
}
///------------------------------------------------------------------
inline void Afisare()
{
    for(int i=1;i<=n;i++) g<<rasp[i]<<" ";
}
///------------------------------------------------------------------
void bkt(int poz)
{
    if(poz == n+1)
    {
        r++;
        if(r==1)
        {
            Afisare();
        }
    }
    for(int j=1;j<=n;j++)
    {
        if(Verificare(poz , j))
        {
            rasp[poz] = j;
            col[j] = 1;
            diag_1[j- poz + n] = 1;
            diag_2[poz + j] = 1;
            bkt(poz + 1);
            col[j] = 0;
            diag_1[j- poz + n] = 0;
            diag_2[poz + j] = 0;
        }
    }
}
///------------------------------------------------------------------
inline void Solution()
{
    bkt(1);
    g<<"\n"<<r;
}
///------------------------------------------------------------------
int main()
{
    readInput();
    Solution();
    return 0;
}