#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],f[15],x[15],t[100],w[100];
///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(f[i]==0&&w[i-pas+30]==0&&t[i+pas+30]==0){
            x[pas]=i;
            f[i]++;
            w[i-pas+30]++;
            t[i+pas+30]++;
            backl(pas+1);
            f[i]--;
            w[i-pas+30]--;
            t[i+pas+30]--;
        }
    }

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