using namespace std;
#include <fstream>
ifstream fin("damesah.in");
ofstream fout("damesah.out");
const int Nmax = 13;

long long nr = 0;
int n;
int v[Nmax], col[Nmax], dp[2 * Nmax], ds[2 * Nmax];

void bkt(int) ;

int main()
{
    fin >> n;
    for(int i = 0; i < n; ++i)
    {
        v[0] = i;
        col[i] = 1;
        dp[i] = 1;
        ds[n - i] = 1;
        bkt(1);
        v[0] = 0;
        col[i] = 0;
        dp[i] = 0;
        ds[n - i] = 0;
    }
    fout << '\n' << nr << '\n';
    return 0;
}


void bkt(int poz)
{
    //completam linia poz
    if(poz == n)
    {
        if(nr == 0) for(int i = 0; i < n; ++i) fout << 1 + v[i] << ' ';
        ++nr; return;
    }
    for(int i = 0; i < n; ++i)
        if(!col[i] && !ds[poz - i + n] && !dp[poz + i])
        {
            v[poz] = i;
            col[i] = 1; ds[poz - i + n] = 1; dp[poz + i] = 1;
            bkt(poz + 1);
            v[poz] = 0;
            col[i] = 0; ds[poz - i + n] = 0; dp[poz + i] = 0;
        }
}