#include <fstream>
#include <cmath>

using namespace std;

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

int n, x[15], f[15];
int prima = 1, ans[15], sol;

void Tiparire()
{
    sol++;
    if(prima)
        for(int i = 1; i <= n; i++)
            ans[i] = x[i];
    prima = 0;
}

bool Validare(int k)
{
    for(int i = 1; i < k; ++i)
        if(k - i == abs(x[k] - x[i]))
            return false;
    return true;
}

void Backtracking(int k)
{
    if(k > n)
        Tiparire();
    else
        for(int i = 1; i <= n; ++i)
            if(f[i] == 0)
            {
                x[k] = i;
                f[i] = 1;
                if(Validare(k))
                    Backtracking(k + 1);
                f[i] = 0;
            }
}

int main()
{
    cin >> n;
    Backtracking(1);

    for(int i = 1; i <= n; i++)
        cout << ans[i] << ' ';
    cout << '\n' << sol;
    return 0;
}