#include <bits/stdc++.h>

using namespace std;

ifstream f("damesah.in");
ofstream g("damesah.out");

int n, a, b, solCnt;
vector<int> sol;

void print()
{
    for (auto x : sol)
        cout << x + 1 << ' ';
}

bool valid(int index)
{
    for (int i = 0; i < index; ++i)
        if (sol[i] == sol[index]
            || sol[index] - sol[i] == index - i
            || sol[index] - i == sol[i] - index)
                return false;

    return true;
}

void bk(int index)
{
    for (sol[index] = 0; sol[index] < n; ++sol[index])
        if (valid(index))
            if (index == n - 1)
            {
                ++solCnt;
                if (solCnt == 1)
                    print();
            }
            else
                bk(index + 1);
}

int main()
{
    f >> n;
    sol.resize(n);

    bk(0);

    g << '\n' << solCnt;

    return 0;
}