#include <fstream>

using namespace std;
ifstream fin ("damesah.in");
ofstream fout ("damesah.out");
int n, ans[17], sol, anss[17];
bool ok1 = 1, ok2 = 0;
bool check(int k)
{
    for(int i = 1; i < k; ++i)
        if(ans[k] == ans[i] || k - i == abs(ans[k] - ans[i])) return 0;
    return 1;
}
void solve(int k)
{
    for(int i = 1; i <= n; ++i) {
        ans[k] = i;
        if(check(k)) {
            if(ans[k] > anss[k]) ok1 = 0;
            else if(ans[k] < anss[k] && ok1 == 1) ok2 = 1;
            if(k != n) solve(k + 1);
            else {
                ++sol;
                if(ok2) {
                        for(int j = 1; j <= n; ++j) anss[j] = ans[j];
                        ok2 = 0;
                }
            }
        }
    }
}
int main()
{
    fin >> n;
    for(int i = 1; i <= n; ++i) anss[i] = 15;
    solve(1);
    for(int i = 1; i <= n; ++i) fout << anss[i] << " ";
    fout << "\n";
    fout << sol;
    return 0;
}