#include <cstdio>

using namespace std;

int n, rez, v[16], sol[16];
bool c[16], d1[32], d2[32];

inline void verif ()
{
    ++rez;
    if (rez == 1)
    {
        for (int i = 1; i <= n; ++i)
            sol[i] = v[i];

        return;
    }

    bool OK = false;
    for (int i = 1; i <= n; ++i)
        if (!OK && v[i] > sol[i]) break;
        else if (v[i] < sol[i] || OK) OK = true, sol[i] = v[i];
}

inline void back (int k)
{
    if (k > n)
    {
        verif ();
        return;
    }

    for (int i = 1; i <= n; ++i)
        if (!c[i] && !d1[k - i + n] && !d2[2 * n - k - i])
        {
            c[i] = true;
            d1[k - i + n] = true;
            d2[2 * n - k - i] = true;

            v[k] = i;
            back (k + 1);

            c[i] = false;
            d1[k - i + n] = false;
            d2[2 * n - k - i] = false;
        }
}

int main ()
{
    freopen ("damesah.in", "r", stdin);
    freopen ("damesah.out", "w", stdout);

    scanf ("%d", &n);

    back (1);

    for (int i = 1; i <= n; ++i)
        printf ("%d ", sol[i]);

    printf ("\n%d\n", rez);

    return 0;
}