#include <fstream>

using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n, i, j, lin[15], col[15], diags[31], diagp[61], sol[15], ans, sol2[15];
bool ok=false;
void bkt(int k)
{
    for(int i=1; i<=n; i++) //coloana
    {
        if(col[i]==0)
        {
            col[i]=1;
            sol[k]=i;
            int p=0;
            if(k-i<0)
                p=2*n+1+k-i;
            else
                p=k-i;
            int s=k+i;

            if(diagp[p]==0 && diags[s]==0)
            {

                diagp[p]=1;
                diags[s]=1;
                if(k<n)
                    bkt(k+1);
                else if(k==n)
                {
                    if(ok==false)
                    {
                        for(int j=1; j<=n; j++)
                        sol2[j]=sol[j];
                        ok=true;
                    }

                    ans++;
                }
                diagp[p]=0;
                diags[s]=0;
            }
            col[i]=0;
        }
    }
}
int main()
{
    fin>>n;
    bkt(1);
    for(i=1; i<=n; i++)
        fout<<sol2[i]<<" ";
    fout<<'\n';
    fout<<ans;
    return 0;
}