#include <fstream>
using namespace std;
int n,p[14],sol;
bool c[14],dp[27],dm[27];
ifstream f("damesah.in");
ofstream g("damesah.out");
void back(int i)
{
    for(int j=1;j<=n;++j)
        if(!c[j]&&!dp[i+j]&&!dm[i-j+n])
        {
            p[i]=j;
            c[j]=dp[i+j]=dm[i-j+n]=1;
            if(i==n)
            {
                if(!sol++)
                    for(int k=1;k<=n;++k)
                        g<<p[k]<<" ";
            }
            else back(i+1);
            c[j]=dp[i+j]=dm[i-j+n]=0;
        }
}
int main()
{
    f>>n;
    back(1);
    g<<'\n'<<sol;
    return 0;
}