#include <fstream>

using namespace std;
ifstream fin ("damesah.in");
ofstream fout ("damesah.out");
int n, ans[17], sol, anss[17];
bool f[17];
bool check(int k)
{
    for(int i = 1; i < k; ++i)
        if(k - i == abs(ans[k] - ans[i])) return 0;
    return 1;
}
void solve(int k)
{
    for(int i = 1; i <= n; ++i) {
        if(!f[i]) {
        ans[k] = i;
        f[i] = 1;
        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;
                }
            }
        }
            f[i] = 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;
}