#include <bits/stdc++.h>
using namespace std;
ifstream in("damesah.in");
ofstream out("damesah.out");
int lin[50], diagprin[50], diagsec[50],n;
int A[25][25],k;
void printsol()
{
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
            if( A[i][j] ) out << j << ' ';
    }
}

void bkt(int cnt, int y )
{
    if( cnt == n ){ k++; if( k==1 ) printsol(); };

    for(int x = 1; x<=n; x++)
    {
    if( lin[x] || diagprin[x+y] || diagsec[x-y+n+1] ) continue;
        lin[x] = diagprin[x+y] = diagsec[x-y+n+1] = 1;
        A[x][y] = 1;
        bkt(cnt+1,y+1);
        A[x][y] = 0;
        lin[x] = diagprin[x+y] = diagsec[x-y+n+1] = 0;
    }
}


int main()
{
    ios::sync_with_stdio(0);
    in >> n;
    bkt(0,1);
    out << '\n' << k;


    return 0;
}