#include <fstream>
#include <bitset>
using namespace std;
ifstream cin("damesah.in");
ofstream cout("damesah.out");
int n,sol,d[20];
bitset <20> dp,ds,c;
void b(int lvl)
{   int i;
    if(lvl==n+1)
    {
        if(!sol++)
        {
            for(i=1;i<=n;++i)
                cout<<d[i]<<" ";
                cout<<'\n';
        }
    }
    for(i=1;i<=n;++i)
    {
        if(c[i]==0 && dp[lvl-i+n]==0 && ds[lvl+i]==0)
        {
            d[lvl]=i;
            dp[lvl-i+n]=ds[lvl+i]=c[i]=1;
            b(lvl+1);
            dp[lvl-i+n]=ds[lvl+i]=c[i]=0;
        }
    }
}
int main()
{
    cin>>n;
    b(1);
    cout<<sol;
    return 0;
}