#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 init();
int solution();
void printSolution();
int isValid();
int has_next();
void back();

int main() {

    freopen(FOUT, "w", stdout);

    read();
    back();

    fclose( stdout );

  return(0);
};

void back() {

     int HS;

     level = 1;
     init();

     while(level > 0) {
 
           while((HS = has_next()) && !isValid());

           if( HS ) {

               if( solution() ) {

                  printSolution();

               } else {

                  level++;

                  init();
               }

           } else

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

void read() {

     freopen(FIN, "r", stdin);

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

void init() {

     stack[ level ] = 0;
};


int solution() {

    return level == n;
};

void printSolution() {

     int i;

     if( !one )

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

         one = 1;
     
     num_solutions++;
};

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;     
};

int has_next() {

    if(stack[ level ] < n) {

       stack[ level ]++;

       return 1;  
    }

    return 0;
};