#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");

int st[20],n, viz[20];
int nr;

void Afisare()
{
    int i;
    for(i=1;i<=n;i++)
        fout<<st[i]<<" ";
}
inline int Valid(int top, int x)
{
    int i;
    if (viz[x] == 1) return 0;
    for(i = 1; i < top; i++)
        if(abs(st[i] - x)==abs(top-i)) return 0;
    return 1;
}

inline void Back(int top)
{
    if(top > n)
    {
        if(!nr) Afisare();
        nr++;
        return;
    }
    for(int i = 1; i <= n; i++)
        if (Valid(top,i))
        {
            st[top] = i;
            viz[i] = 1;
            Back(top+1);
            viz[i] = 0;
        }
}

int main()
{
    fin>>n;
    fin.close();
    Back(1);
    fout<<"\n";
    fout<<nr;
    fout.close();
    return 0;
}