#include <bits/stdc++.h>

using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n,a[20],sol,dp[100],ds[100],v[20];
bool valid(int i, int j)
{
    if (v[j]==1) return 0;
    if (ds[i+j-1]==1) return 0;
    if (dp[n-j+i]==1) return 0;
    return 1;
}
void Back(int top)
{
    if (top==n+1)
    {
        sol++;
        if (sol==1)
        {
            for (int i=1; i<=n; i++)
                fout << a[i] << " ";
            fout << "\n";
        }
    }
    else
    for (int i=1; i<=n; i++)
    if (valid(top,i))
    {
        a[top]=i;
        v[i]=1;
        ds[top+i-1]=1;
        dp[n-i+top]=1;
        Back(top+1);
        ds[top+i-1]=0;
        dp[n-i+top]=0;
        v[i]=0;
    }
}
int main()
{
    fin >>  n;
    Back(1);
    fout << sol;


    return 0;
}