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

using namespace std;

int N;
vector<int> oszl;

bool bizt(int r,int c);
void megold(int r,int &count,ofstream &g);

void megold(int r,int &count,ofstream &g) {
    if (r==N) {
        for (int i=0;i<N;i++) {
            g<<oszl[i]+1<<" ";
        }
        g<<endl;
        count++;
        return;
    }

    for (int c=0;c<N;c++) {
        if (bizt(r,c)) {
            oszl[r]=c;
            megold(r+1,count,g);
        }
    }
}

bool bizt(int r, int c) {
    for (int i=0; i<r; i++) {
        if (oszl[i]==c||abs(r-i)==abs(oszl[i]-c)){
            return false;
        }
    }
    return true;
}

int main() {
    ifstream f("damesah.in");
    f>>N;
    f.close();
    ofstream g("damesah.out");
    oszl.resize(N);
    int count = 0;
    megold(0, count, g);
    g<<count;
    g.close();

    return 0;
}