#include <bits/stdc++.h>
using namespace std;
ifstream in("damesah.in");
ofstream out("damesah.out");
int c[30], d1[30], d2[30], v[30];
int cnt,n ;

void solve( int y )
{

    if ( y == n )
    {
        if ( !cnt )
        {
            for(int i=0; i<n; i++)
                out << v[i] +1 << ' ';
        }
        cnt ++;
        return;

    }
    for (int x=0; x<n; x++)
    {
        if( c[x] || d1[x+y] || d2[x-y+n+1] ) continue;
        v[y]=x;
        c[x] = d1[x+y] = d2[x-y+n+1]=1;
        solve(y+1);
        c[x] = d1[x+y] = d2[x-y+n+1]=0;
    }

}
int main()
{
    in >> n;
    solve(0);
    out  << '\n' << cnt;


    return 0;
}