#include <fstream>

using namespace std;

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

int sol[14], fp[14], fs[14], col[14];

int n, nr;


void afis()
{
    nr++;
    if(nr == 1)
        for(int i = 1; i <= n; i++)
            cout << sol[i] << " ";
}

int ok(int j, int i)
{
    int dp = n + 1 - j + i, ds = i + j;
    if(col[j] || fp[dp] || fs[ds])
        return 0;
    return 1;
}

void bkt(int i)
{
    if(i == n + 1)
    {
        afis();
        return;
    }
    for(int j = 1; j <= n; j++)
        if(ok(j, i))
        {
            sol[i] = j;
            int dp = n + 1 - j + i, ds = i + j;
            col[j] = 1;
            fp[dp] = 1;
            fs[ds] = 1;
            bkt(i + 1);
            col[j] = 0;
            fp[dp] = 0;
            fs[ds] = 0;
        }
}

int main()
{
    cin >> n;
    bkt(1);
    cout << '\n' << nr;
    return 0;
}