#include <fstream>

using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n, i, lin[15], col[15], diag_secund[30], diag_princip[30], st[15], nr, ans[15];
bool ok=true;
void bkt(int l)
{
    for(int c=1; c<=n; c++)
        if(col[c]==0 && diag_secund[c+l]==0 && diag_princip[c-l+n]==0)
        {
            col[c]=1;
            diag_secund[c+l]=1;
            diag_princip[c-l+n]=1;
            st[l]=c;
            if(l==n)
            {
                if(ok==true)
                {
                    for(int i=1; i<=n; i++)
                        ans[i]=st[i];
                    ok=false;
                }
                nr++;
            }
            else
                if(l<n)
                bkt(l+1);
            col[c]=0;
            diag_secund[c+l]=0;
            diag_princip[c-l+n]=0;
        }
}
int main()
{
    fin>>n;
    bkt(1);
    for(i=1; i<=n; i++)
        fout<<ans[i]<<" ";
    fout<<'\n'<<nr;
    return 0;
}