#include <fstream>
#include <vector>
using namespace std;
ifstream cin("damesah.in");
ofstream cout("damesah.out");
int cont=0;
int n;
bool ok=true;
int d1[30];
int  d2[30];
int col[30];
int rasp[30];
void backtracking(int x){
if(x==n+1){
 if(ok){
    for(int i=1;i<=n;i++){
        cout<<rasp[i]<<" ";
    }
    cout<<'\n';
    cont++;
    ok=false;
    return;
 }else{
    cont++;
    return;
 }
}
for(int i=1;i<=n;i++){
    if(d1[i+x] || d2[x-i+n] || col[i]){
        continue;
    }
    rasp[x]=i;
    d1[i+x]=true;
    d2[x-i+n]=true;
    col[i]=true;
    backtracking(x+1);
    d1[i+x]=false;
    d2[x-i+n]=false;
    col[i]=false;
}
}

void read(){
cin>>n;
}
void solve(){
read();
backtracking(1);
cout<<cont;
}
int main()
{
   int t;
   t=1;
   while(t--){
    solve();
   }
    return 0;
}