#include <fstream>

using namespace std;

const int NMax = 16;

int n;
int ans[NMax];
int nrans;
int st[NMax];
bool column[NMax], diag_p[NMax + NMax], diag_s[NMax + NMax];

inline void back(const int k)
{
    if (k == n+1)
    {
        if (++nrans == 1)
            for (int i = 1; i<=n; ++i)
                ans[i] = st[i];
        return ;
    }
    for (int i = 1; i<=n; ++i)
    {
        /// vreau sa pun pe linia k si coloana i o dama
        if (!column[i] && !diag_p[-i+k+n] && !diag_s[i+k-1])
        {
            st[k] = i;
            column[i] = diag_p[-i+k+n] = diag_s[i+k-1] = true;
            back(k+1);
            column[i] = diag_p[-i+k+n] = diag_s[i+k-1] = false;
        }
    }
}

int main()
{
    ifstream f("damesah.in");
    f>>n;
    f.close();
    back(1);
    ofstream g("damesah.out");
    for (int i = 1; i<=n; ++i)
        g<<ans[i]<<" ";
    g<<"\n"<<nrans<<"\n";
    g.close();
    return 0;
}