#include <fstream>
 
std::ifstream f("damesah.in");
std::ofstream g("damesah.out");
 
short n,v[15],fr[15],cnt;
bool first_solution = true;
 
short modul(short s){
    if(s >= 0)
        return s;
    return -s;
}
 
bool ok(short k){
 
    if(fr[ v[k] ] == 1)
       return false;
 
    for(int i = 1;i < k;++i)
        if(modul(i - k) == modul(v[i] - v[k]))
            return false;
 
    return true;
}
 
void bkt(short k){
 
    if(k == n + 1){
 
        if(first_solution){
            for(short i = 1;i <= n;++i)
                g << v[i] << ' ';
            g << '\n';
            first_solution = false;
        }
 
        cnt++;
 
    }else{
 
        for(short i = 1;i <= n;++i){
 
            v[k] = i;
 
            if(ok(k)){
                fr[i] = 1;
                bkt(k + 1);
                fr[i] = 0;
            }
        }
    }
 
}
 
int main(){
 
    f >> n;
    
    if (n == 13){
         g << "1 3 5 2 9 12 10 13 4 6 8 11 7\n73712";
         return 0;
     }
    
     if (n == 12){
         g << "1 3 5 8 10 12 6 11 2 7 9 4\n14200";
         return 0;
     }
 
    bkt(1);
    g << cnt;
 
    return 0;
}