#include<fstream>
#include<algorithm>
using namespace std;

ifstream cin("damesah.in");
ofstream cout("damesah.out");

int n,a[20],cnt,dp[30],ds[30],col[20];


void Afis()
{
    for (int i=1;i<=n;i++)
    {
        cout << a[i] << ' ';
    }
    cout << '\n';
}

void back(int k)
{
    int i,j;
    if (k==n+1)
        {cnt++;
        if (cnt==1)Afis();
        return;}
    for (i=1;i<=n;i++)
    {
        if (col[i] || dp[k-i+n] || ds[k+i-1]) continue;
        col[i]=dp[k-i+n]=ds[k+i-1]=1;
        a[k]=i;
        back(k+1);
        col[i]=dp[k-i+n]=ds[k+i-1]=0;
    }
}

int main()
{
    cin >> n;
    back(1);
    cout<<cnt;
    return 0;
}