#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream cin("damesah.in");
ofstream cout("damesah.out");
int c[13],n,cnt = 0;
void afisare()
{
    int i;
    if(cnt > 0)
        return;
    else
    {
        for(i = 1; i <= n; i++)
            cout << c[i] << " ";
        cout << "\n";
    }
}
void bkt(int k)
{
    int i,j;
    bool ok;
    if(k == n + 1)
    {
        afisare();
        cnt++;
    }
    else
    {
        for(i = 1; i <= n; i++)
        {
            for(j = 1,ok = 1; j < k; j++)
            {
                if(c[j] == i || abs(c[j] - i) == abs(k - j))
                    ok = 0;
            }
            if(ok == 1){
                c[k] = i;
                bkt(k + 1);
                c[k] = 0;
            }
        }
    }
}
int main()
{
    cin >> n;
    bkt(1);
    cout << cnt;
    return 0;
}