#include <fstream>
#include <algorithm>
using namespace std ; 
int N , sol , v[20], St[20];
bool ok, viz[20], First[20] , Second[30];
inline void Read(){
    ifstream f("damesah.in");
    f >> N;
}

inline void Back(const int k){
    if(k==N+1){
        if(ok)
            ++sol;
        else{
            ++sol; ok = 1;
            for(int i = 1;i <= N;++i)
                v[i] = St[i];
        }
        return ;
    }
    for(int i = 1; i <= N; ++i)
        if(!viz[i] && !First[k - i + N] && !Second[k + i]){
            viz[i] = 1;
            St[k] = i;
            First[k - i + N] = Second[k + i] = 1;
            Back(k+1);
            First[k - i + N] = Second[k + i] = 0;
            viz[i] = 0;
        }
}

inline void Write(){
    ofstream g("damesah.out");
    for( int i = 1; i <= N; ++i)
        g << v[i]<<" ";
    g<<"\n"<<sol<<"\n";
    g.close();
}

int main(){
    Read();
    Back(1);
    Write();
    return 0;
}