#include <bits/stdc++.h>

using namespace std;

int n, k;
vector<int> l, sol;
bool dig[200], dig2[200], col[200];
#define dig (dig+100)
#define dig2 (dig2+100)
#define col (col+100)
void bkt()
{
    /*for (unsigned i = 0; i < l.size(); ++i)
        cout << l[i] << " ";
    cout << "\n";*/
    if((int)l.size() == n){
        if(sol.size() == 0){
            for (int i = 0; i < n; ++i)
                sol.push_back(l[i]);
        }
        ++k;
    }else{
        int lin = l.size()+1;
        for (int i = 1; i <= n; ++i){
            if(!col[i] && !dig[i-lin] && !dig2[n-i-lin+1]){
                col[i] = 1;
                dig[i-lin] = 1;
                dig2[n-i-lin+1]=1;
                l.push_back(i);
                bkt();
                l.pop_back();
                col[i] = 0;
                dig2[n-i-lin+1]=0;
                dig[i-lin] = 0;
            }
        }
    }
}

int main()
{
    ifstream fin ("damesah.in");
    ofstream fout ("damesah.out");
    fin >> n;
    bkt();
    for (int i = 0; i < n; ++i)
        fout << sol[i] << " ";
    fout << "\n" << k << "\n";
    fin.close();
    fout.close();
    return 0;
}