#include <fstream>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n,ok,v[50],c[50],dp[50],ds[50];
void backt(int poz){
    if(poz>n){
        if(ok==0){
            for(int i=1;i<=n;i++){
                fout<<v[i]<<" ";
            }
            fout<<"\n";

        }
        ok++;
    }
    else{
        for(int i=1;i<=n;i++){
            if(c[i]==0 && dp[poz-i+n]==0 && ds[i+poz]==0){
                v[poz]=i;
                c[i]=1;
                dp[poz-i+n] =1;
                ds[i+poz] =1;
                backt(poz+1);
                c[i]=0;
                dp[poz-i+n] =0;
                ds[i+poz] =0;

            }
        }
    }


}
int main(){
    fin>>n;
    backt(1);
    fout<<ok;

}