#include <bits/stdc++.h>

using namespace std;

ifstream fin ("damesah.in");
ofstream fout ("damesah.out");

int c[22],dp[22],ds[22];
vector <int> ans,sol;
int totalsol = 0;

void BackTrackin(int n,int row){
    if (sol.empty()) for (int i=1;i<=n+2;++i) sol.push_back(0);
    if (row==n+1){
        totalsol++;
        if (ans.empty()){
            ans = sol;
        }
        return;
    }
    for (int col=1;col<=n;++col){
        if (c[col]==0 and dp[row-col+n]==0 and ds[row+col-1]==0){
            sol[row] = col;
            c[col] = 1;
            dp[row-col+n] = 1;
            ds[row+col-1] = 1;
            BackTrackin(n,row+1);
            c[col] = 0;
            dp[row-col+n] = 0;
            ds[row+col-1] = 0;
        }
    }
}

int main()
{
    int n;
    fin >> n;
    BackTrackin(n,1);
    for (int i=1;i<=n;++i) fout << ans[i] << ' ';
    fout << '\n';
    fout << totalsol;
    return 0;
}