#include <fstream>

int damesah(int n, int data[])
{
    int tmp[n], it = 0, ret = 0;
    for (int i = 0; i < n; i++)
        tmp[i] = -1;
    while (it >= 0)
    {
        if (it == n)
        {
            if (!ret)
                for (int i = 0; i < n; i++)
                    data[i] = tmp[i] + 1;
            ret++;
            it--;
        }
        bool good = false;
        while (1)
        {
            tmp[it]++;
            if (tmp[it] == n)
            {
                good = false;
                break;
            }
            int i;
            for (i = 0; i < it; i++)
                if (tmp[i] == tmp[it] || tmp[i] - tmp[it] == i - it || tmp[it] - tmp[i] == i - it)
                {
                    break;
                }
            if (i == it)
            {
                good = true;
                break;
            }
        }
        if (!good)
            tmp[it] = -1, it--;
        else
            it++;
    }
    return ret;
}

int main()
{
    int n, num;
    std::ifstream in("damesah.in");
    in >> n;
    in.close();

    int sol[n];
    num = damesah(n, sol);
    std::ofstream out("damesah.out");
    for (int i = 0; i < n; i++)
        out << sol[i] << ' ';
    out << '\n' << num << '\n';
    out.close();
}