#include <bits/stdc++.h>
#define DAU ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define PLEC return 0;

using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");
#define cin fin
#define cout fout

#define N 15
int n, st[N], ok, sol;

int mod(int x)
{
    if(x < 0)return -x;
    else return x;
}
void afis()
{
    if(sol == 0)
    {
        for(int i = 1 ; i <= n ; i++)
        {
            cout << st[i] << " ";
        }
        cout << '\n';
    }
    sol++;
}
int valid(int k)
{
    for(int i = 1 ; i < k ; i++)
    {
        if(st[k] == st[i]  ||  k-i == mod(st[k]-st[i]))return 0;
    }
    return 1;
}
void bkt(int k)
{
    for(int i = 1 ; i <= n ; i++)
    {
        st[k] = i;
        if(valid(k))
        {
            if(k == n)
            {
                afis();
            }
            else bkt(k+1);
        }
    }
}

int main()
{
    DAU
    cin >> n;
    bkt(1);
    cout << sol;
    PLEC
}