#呜呜蒟蒻算出的个数没错，输出顺序错误

#include <iostream>
using namespace std;
int n,cnt = 0;
int h1[20] = {0},x1[40] = {0},x2[40] = {0};
void dep(int dp,int l)
{
    if(dp == n+1)
    {
        cnt++;
        for(int i=1;i<=n;i++)
        {
            cout<<h1[i]<<" ";
        }
        cout<<endl;
        return;
    }
    if(l <= 0||l > n)
        return;

    for(int h=1;h<=n;h++)
    {
        if(h1[h] == 0&&!x1[l+h]&&!x2[n + l - h])
        {
            h1[h] = l;
            x1[l+h] = 1;
            x2[n + l - h] = 1;
            dep(dp+1,l+1);
            h1[h] = 0;
            x1[l+h] = 0;
            x2[n + l - h] = 0;
        }
    }
}
int main()
{
    cin>>n;
    dep(1,1);
    cout<<cnt;
    return 0;
}