#include <fstream>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n;
int vfcoloana[19];
int ans[19];
int cnt;
void bkt(int pas){
    if(pas==n+1){
        if(cnt==0){
            for(int i=1;i<=n;i++){
                fout<<ans[i]<<" ";
            }
            fout<<endl;
        }
        cnt++;
        return ;
    }
    for(int i=1;i<=n;i++){
        bool ok=1;
        if(vfcoloana[i]==0){
            for(int j=1;j<pas;j++){
                if(ans[j]+j==pas+i){
                    ok=0;
                }
                if(j-ans[j]==pas-i){
                    ok=0;
                }
            }
            if(ok){
                ans[pas]=i;
                vfcoloana[i]=1;
                bkt(pas+1);
                vfcoloana[i]=0;
            }
        }
    }
}
int main(){
    fin>>n;
    bkt(1);
    fout<<cnt;
    return 0;
}