#include <bits/stdc++.h>

using namespace std;

ifstream f ("damesah.in");
ofstream g ("damesah.out");

short n;
short a[20];
bool used_lin[20] , used_col[20] , used_dp[40] , used_ds[40];
int ans;

void bkt(short k)
{
    if(k == n + 1)
    {
        ++ans;

        if(ans == 1)
        {
            for(short i = 1 ; i <= n ; i++)
                g << a[i] << ' ';

            g << '\n';
        }
    }
    else
    {
        short i = k;

        for(short j = 1 ; j <= n ; j++)
        {
            int ds = i + j , dp = n - j + i + 1;

            if(!used_lin[i] && !used_col[j] && !used_dp[dp] && !used_ds[ds])
            {
                used_lin[i] = used_col[j] = used_dp[dp] = used_ds[ds] = 1;
                a[k] = j;

                bkt(k + 1);
                used_lin[i] = used_col[j] = used_dp[dp] = used_ds[ds] = 0;
            }
        }
    }
}

int main()
{
    f >> n;
    bkt(1);
    g << ans;

    return 0;
}