#include <fstream>

using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int n,j,ok,c[20],d1[30],d2[30],i[20];
int fnc(int x)
{
    int s=0;
    if(x<n)
    {
        for(i[x]=1; i[x]<=n; i[x]++)
        {
            c[i[x]]++;
            d1[i[x]-x+n]++;
            d2[i[x]+x]++;
            if(c[i[x]]==1&&d1[i[x]-x+n]==1&&d2[i[x]+x]==1)
            {
                s+=fnc(x+1);
            }
            c[i[x]]--;
            d1[i[x]-x+n]--;
            d2[i[x]+x]--;
        }
    }
    else
    {
        for(i[x]=1; i[x]<=n; i[x]++)
        {
            c[i[x]]++;
            d1[i[x]-x+n]++;
            d2[i[x]+x]++;
            if(c[i[x]]==1&&d1[i[x]-x+n]==1&&d2[i[x]+x]==1)
            {
                s++;
                if(ok==0)
                {
                    ok=1;
                    for(j=1; j<=n; j++) g<<i[j]<<" ";
                }
            }
            c[i[x]]--;
            d1[i[x]-x+n]--;
            d2[i[x]+x]--;
        }
    }
    return s;
}
int main()
{
    f>>n;
    g<<'\n'<<fnc(1);
    f.close(); g.close();
    return 0;
}