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

int dame[15];
bool lin[15],diag1[30],diag2[30];
int n,nrsol,ok;

int bkt(int pas)
{
    int i;
    if(pas==n+1)
    {
        if(!ok) { for(i=1;i<=n;i++) printf("%d ",dame[i]); ok=1; }
        nrsol++;
    }
    else
    {
        //if(pas==3) cout<<"ASFDAS "<<lin[1]<<' '<<diag1[pas-1+n]<<' '<<diag2[pas+1-1]<<'\n';
        for(i=1;i<=n;i++)
        {
            //cout<<pas<<' '<<i<<"  "<<lin[i]<<' '<<pas-i+n<<' '<<diag1[pas-i+n]<<"  "<<pas+i-1<<' '<<diag2[pas+i-1]<<'\n';
            if(!lin[i] && !diag1[pas-i+n] && !diag2[pas+i-1])
            {
                dame[pas]=i;
             //   cout<<pas<<' '<<i<<"   "<<pas<<' '<<dame[pas]<<' '<<pas-i+n<<' '<<pas+i-1<<'\n';
                lin[i]=diag1[pas-i+n]=diag2[pas+i-1]=1;
                bkt(pas+1);
                lin[i]=diag1[pas-i+n]=diag2[pas+i-1]=0;
            }
        }
    }
}


int main()
{
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);

    scanf("%d",&n);
    bkt(1);
    printf("\n%d\n",nrsol);
    fclose(stdin);
    fclose(stdout);
    return 0;
}