#include <bits/stdc++.h>

using namespace std;
int n, ans[17], sol, anss[17];
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(k != n) solve(k + 1);
            else {
                ++sol;
                for(int ii = 1; ii <= n; ++ii) {
                    if(ans[ii] < anss[ii]) {
                        for(int jj = 1; jj <= n; ++jj) anss[jj] = ans[jj];
                        break;
                    }
                    else if(ans[ii] > anss[ii]) break;
                }
            }
        }
    }
}
int main()
{
    freopen("damesah.in", "r", stdin);
    freopen("damesah.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) anss[i] = 15;
    solve(1);
    for(int i = 1; i <= n; ++i) printf("%d ", anss[i]);
    printf("\n");
    printf("%d", sol);
    return 0;
}