#include<fstream>
#include<algorithm>
using namespace std;

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

int n,a[20],cnt;


void Afis()
{
    for (int i=1;i<=n;i++)
    {
        cout << a[i] << ' ';
    }
    cout << '\n';
}

void back(int k)
{
    int i,j;
    if (k==n+1)
        {cnt++;
        if (cnt==1)Afis();
        return;}
    for (i=1;i<=n;i++)
    {
        int ok=1;
        for (j=1;j<k && ok;j++)
            if (i==a[j] || abs(k-j)==abs(i-a[j])) ok=0;
        if (ok)
            a[k]=i,
            back(k+1);
    }
}

int main()
{
    cin >> n;
    back(1);
    cout<<cnt;
    return 0;
}