#include <fstream>

using namespace std;
ifstream cin("damesah.in");
ofstream cout("damesah.out");
int dp[26],ds[26],c[14],rez,v[14],n;
void bkt(int pas)
{
    if(pas==n+1)
    {
        rez++;
        if(rez==1)
        for(int i=1;i<=n;i++)
            cout<<v[i]<<" ";
    }
    else
    {
        int j;
        for(j=1;j<=n;j++)
            if(c[j]==0&&dp[n+pas-j]==0&&ds[pas+j]==0)
            {
                c[j]=1;
                dp[n+pas-j]=1;
                ds[pas+j]=1;
                v[pas]=j;
                bkt(pas+1);
                c[j]=0;
                dp[n+pas-j]=0;
                ds[pas+j]=0;
            }
    }
}
int main()
{
    cin>>n;
    bkt(1);
    cout<<'\n'<<rez;
    return 0;
}