#include <stdio.h>
#include <math.h>
#define MAX 13
#define FIN "damesah.in"
#define FOUT "damesah.out"

int stack[ MAX ], n;

int level,
    num_solutions = 0, 
    one = 0;

//function prototypes
void read();
void printSolution();
int isValid();
void back();

int isSol;

int main() {

    freopen(FOUT, "w", stdout);

    read();
    back();

    fclose( stdout );

  return(0);
};

void back() {

     level = 1;

     stack[ level ] = 0; 

     while(level > 0) {

           isSol = 0;

           while((stack[ level ] < n) && !isSol) {

                  stack[ level ]++;

                  isSol = isValid(); 
           } 

           if( isSol ) {

               if( level == n ) {

                 if(!one) printSolution(), one = 1;

                 num_solutions++;

               } else {

                  level++;

                  stack[ level ] = 0;
               }

           } else

             level--;
     }
 
     printf("\n%d", num_solutions);
};

void read() {

     freopen(FIN, "r", stdin);

     scanf("%d", &n);
 
     fclose( stdin );
};


void printSolution() {

     int i;

     for(i = 1; i <= n; i++) printf("%d ", stack[ i ]);
};

int isValid() {

    int i;

    for(i = 1; i < level; i++) {

        if( stack[ i ] == stack[ level ] || level - i == fabs( stack[ i ] - stack[ level ]) ) return 0;
    }      

    return 1;     
};