#include <fstream>
using namespace std;
ifstream in ("damesah.in");
ofstream out ("damesah.out");
int n, nr, D[14], C[14], dP[26], dS[26];

void back (int l) {
    for (int c = 1; c <= n; c++)
        if (!C[c] and !dP[n + c - l] and !dS[l + c - 1]) {
            D[l] = c; C[c] = dP[n + c - l] = dS[l + c - 1] = 1;
            if (l == n) {
                nr++;
                for (int i = 1; nr == 1 and i <= n; i++)
                    out << D[i] << " ";
            }
            else back(l + 1);
            C[c] = dP[n + c - l] = dS[l + c - 1] = 0;
        }
}

int main() {
    in >> n; back(1);
    out << '\n' << nr << '\n';
    out.close(); return 0;
}