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

inline bool Valid(const int k,const int x){
    for(int i = k-1; i ; --i)
        if(k - i == abs(x - St[i]))
            return false;
    return true;
}

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] && Valid(k,i)){
            viz[i] = 1;
            St[k] = i;
            Back(k+1);
            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;
}