#include <bits/stdc++.h>
using namespace std;

int N,v[14],nr;

int valid(int k){

    for(int i=1;i<k;++i)
        if(v[i]==v[k] || abs(v[k]-v[i])==k-i)
            return 0;
    return 1;

}

int sol(int k){
    return k==N;
}

void afis(int k){

    for(int i=1;i<=k;++i)printf("%d ",v[i]);
    printf("\n");

}

void back(int k){

    for(int i=1;i<=N;++i){
        v[k]=i;

        if(valid(k)){

            if(sol(k)){
                nr++;
                if(nr==1)afis(k);
            }else back(k+1);

        }

    }

}

int main()
{
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);
    scanf("%d",&N);
    back(1);
    printf("%d",nr);

}