#include <iostream>
#include <cmath>
using namespace std;

int v[20],j,n,cnt=0;;

int ok(int j)
{
    for(int i=1;i<j;i++)
        if(v[i]==v[j]||fabs(v[i]-v[j])==fabs(i-j))
        return 0;
    return 1;
}

void afisare()
{
    if(cnt==0)
    {
      for(int i=1;i<=n;i++)
      {
        cout<<v[i]<<" ";
      }
    }
    cnt++;

}

void bkt(int i)
{
        for(int j=1;j<=n;j++)
        {
            v[i]=j;
            if(ok(i))
            {
                if(i==n)
                    afisare();
                else
                    bkt(i+1);
            }

        }
}

int main()
{
    cin>>n;
    bkt(1);
    cout<<'\n'<<cnt;
    return 0;
}