#include <fstream>
#include <queue>
#include <iostream>
using namespace std;

//ifstream cin("damesah.in");
//ofstream cout("damesah.out");
int perm[15];
bool col[15];
bool d1[35];
bool d2[35];
int n,s=0;

void bt(int lvl){
    if (lvl > n){
        s++;
        if (s==1){
            for (int i=1; i<=n; i++){
                cout<<perm[i]<<" ";
            }
            cout<<'\n';
        }
        return;
    }
    for (int i=1; i<=n; i++){
        if (!col[i] && !d1[lvl-i+n] && !d2[i+lvl]){
            col[i] = true;
            d1[lvl-i+n]=true;
            d2[i+lvl]=true;
            perm[lvl] = i;

            bt(lvl+1);

            col[i] = false;
            d1[lvl-i+n]=false;
            d2[i+lvl]=false;
        }
    }
}





int main() {
    cin>>n;
    bt(1);
    cout<<s;
    return 0;
}