#include <fstream>
#include <cstdlib>

using namespace std;

ifstream cin ("damesah.in");
ofstream cout ("damesah.out");

int n,x[20],p[20],nr;

void afisare()
{
    for (int i=1; i<=n; ++i) cout<<x[i]<<" ";
    cout<<"\n";
}

void bectreching (int k)
{
    for (int i=1; i<=n; ++i)
    {
        if (!p[i])
        {
            bool ok=1;
            p[i]=1;
            x[k]=i;
            for (int j=1; j<k; ++j)
                if (k-j==abs(x[k]-x[j])) ok=0;
            if (ok){
                if (k<n) bectreching(k+1);
                else{
                    nr++;
                    if (nr==1) afisare();
                }

            }
            p[i]=0;
        }
    }
}

int main()
{
    cin>>n;
    bectreching(1);
    cout<<nr;

    return 0;
}