#include <fstream>

std::ifstream f("damesah.in");
std::ofstream g("damesah.out");

int n,v[15],fr[15],cnt;
bool first_solution = true;

int modul(int s){
    if(s >= 0)
        return s;
    return -s;
}

bool ok(int k){

    if(fr[ v[k] ] == 1)
       return false;

    for(int i = 1;i < k;++i)
        if(i != k && modul(i - k) == modul(v[i] - v[k]))
            return false;

    return true;
}

void bkt(int k){

    if(k == n + 1){

        if(first_solution){
            for(int i = 1;i <= n;++i)
                g << v[i] << ' ';
            g << '\n';
            first_solution = false;
        }

        cnt++;

    }else{

        for(int i = 1;i <= n;++i){

            v[k] = i;

            if(ok(k)){
                fr[i] = 1;
                bkt(k + 1);
                fr[i] = 0;
            }
        }
    }

}

int main(){

    f >> n;

    bkt(1);
    g << cnt;

    return 0;
}