#include <bits/stdc++.h>


using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n;
int ar[20];

bool ok(int k) {

   

    for (int i = 1; i < k; i++) {
        if (k - i == abs(ar[k] - ar[i])) {
            return false;
        }
    }
    return true;

}

int f[20];
bool da = false;
int nr = 0;
void back(int k) {

    if (k == n + 1) {
        if (!da) {
            for (int i = 1; i <= n; i++) {
                fout << ar[i] << ' ';
            }
            fout << '\n';
            da = true;
        }
        nr++;
        
    }
    else {

        for (int i = 1; i <= n; i++) {
            ar[k] = i;
            if (f[i]==0 && ok(k)) {
                f[i] = 1;
                back(k + 1);
                f[i] = 0;
            }
        }

    }


}


int main()
{
    fin >> n;
    back(1);
    fout << nr;

    
    fin.close();
    fout.close();

}