#include <fstream>
using namespace std;

ifstream cin("damesah.in");
ofstream cout("damesah.out");
int n, v[15], w = 0;
bool r[15], d1[30], d2[30];

void damesah(int k){
    for(int i = 1; i<=n; ++i){
        if(!r[i] && !d1[n-i+k] && !d2[i+k]){
                v[k] = i;
                r[i] = true;
                d1[n-i+k] = true;
                d2[i+k] = true;
                if(k==n){
                    if(w==0){
                        for(int j = 1; j<=n; ++j){
                            cout<<v[j]<<' ';
                        }
                        cout<<'\n';
                    }
                    w++;
                }

                else damesah(k+1);
                r[i] = false;
                d1[n-i+k] = false;
                d2[i+k] = false;

        }
    }
}

int main()
{
    cin>>n;
    damesah(1);
    cout<<w;
    return 0;
}