#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n,i,j,sol,k,ok;
int v[15],w[15],x[15],t[15];
int cont(int a,int pas,int k){
    if(pas==1)
        return 1;
    for(int j=1;j<pas;j++){
        if(x[j]==a){
            return 0;
            break;
        }
    }
    if(k>=1){
        for(int j=1;j<k+1;j++){
            if(w[j]==a-pas){
                return 0;
                break;
            }
            if(t[j]==a+pas){
                return 0;
                break;
            }
        }
    }
    return 1;

}
void backl(int pas){
    if(pas==n+1){
        if(ok==0){
            ok=1;
            for(int i=1;i<n+1;i++){
                fout<<x[i]<<" ";
            }
            fout<<"\n";
        }
        sol++;
    }
    for(int i=1;i<n+1;i++){
        if(cont(i,pas,k)==1){
            x[pas]=i;
            w[++k]=i-pas;
            t[k]=i+pas;
            backl(pas+1);
            k--;
        }
    }

}
int main(){
    fin>>n;
    backl(1);
    fout<<sol;
    return 0;
}