#include <cstdio>
using namespace std;
int sol[15], n, col[15], dp[30], ds[30], nsol;
void back(int k);
int main()
{
    freopen("damesah.in", "r", stdin);
    freopen("damesah.out", "w", stdout);
    scanf("%d", &n);
    back(1);
    printf("\n%d", nsol);
    return 0;
}
void back(int k){
    int i;
    if(k==n+1){
        if(nsol==0)
            for(i=1; i<=n; i++)
                printf("%d ", sol[i]);
        nsol++;
    }
    else
        for(i=1; i<=n; i++)
            if(col[i]==0 and dp[k-i+n]==0 and ds[k+i]==0){
                col[i]=1; dp[k-i+n]=1; ds[k+i]=1;
                sol[k] = i;
                back(k+1);
                col[i]=0; dp[k-i+n]=0; ds[k+i]=0;
            }

}