#include <bits/stdc++.h>
#define newline '\n'
#define ll long long
#define uns unsigned
#define deb(x) clog << x << ' '
#define debnewL(x) clog << x << newline
using namespace std;
///************************************
inline void __attribute__ ((constructor)) _cfun();
inline void _cfun()
{
    freopen("damesah.in", "r", stdin);
    freopen("damesah.out", "w", stdout);
    ios :: sync_with_stdio(NULL);
    cin.tie(nullptr);
    cout.tie(nullptr);
}
///************************************

#define NMAX 15
int n;
int st[NMAX];
bool vis[NMAX];
int sols;

inline bool valid(int top, int x)
{
    if (vis[x])
        return false;

    for (int i = 1; i < top; i++)
    {
        if (abs(top - i) == abs(x - st[i]))
            return false;
    }

    return true;
}

inline void display()
{
    for (int i = 1; i <= n; i++)
        cout << st[i] << ' ';
    cout << newline;
}

void backtracking(int top)
{
    if (top == n + 1)
    {
        sols++;
        if (sols == 1)
            display();
        return;
    }

    for (int i = 1; i <= n; i++)
    {
        if (valid(top, i))
        {
            vis[i] = true;
            st[top] = i;
            backtracking(top + 1);
            vis[i] = false;
        }
    }
}

signed main()
{
    cin >> n;
    backtracking(1);
    cout << sols;
    return 0;
}