#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

ifstream fin ("damesah.in");
ofstream fout ("damesah.out");


int n,cnt;
vector<int> v;
bool print=true;
int fr[15],frd1[100],frd2[100];

bool ok()
{
//    for(int i=0; i<n; i++)
//        for(int j=i+1; j<n; j++)
//            if(i+v[i] == j+v[j] || i-j == v[i]-v[j])
//                return false;
    return true;
}

void backtracking(int k)
{
    if(k>=n)
    {
        if(ok())
        {
            cnt++;
            if(print)
            {
                for(int i=0; i<n; i++) fout<<v[i]<<' ';
                fout<<'\n';
                print = false;
            }
        }
    }
    else
    {
        for(int i=1; i<=n; i++)
        {
            if(fr[i] == 0 && frd1[i+k+1] == 0 && frd2[i-k+50] == 0)
            {
                fr[i]++;
                frd1[i+k+1]++;
                frd2[i-k+50]++;
                v[k] = i;
                backtracking(k+1);
                fr[i]--;
                frd1[i+k+1]--;
                frd2[i-k+50]--;
            }
        }
    }
}

int main()
{
    fin>>n;
    v.assign(n,0);
    backtracking(0);
    fout<<cnt;
    return 0;
}