#include <fstream>

std::ifstream input ("damesah.in");
std::ofstream output ("damesah.out");

int solutionCount = 0;
bool firstsolutionFound = false;

void solve(int size, int currentRow, int arr[], bool occupiedColumns[], bool occupiedDiagonals1[], bool occupiedDiagonals2[]) {

    //col = column
    //arr[row] = queenColumn
    if (currentRow < size) {
        for (int col = 1; col <= size; col++) {
            if (occupiedColumns[col] == false && occupiedDiagonals1[currentRow + col] == false && occupiedDiagonals2[currentRow - col + size] == false) {
                arr[currentRow] = col;
                occupiedColumns[col] = true;
                occupiedDiagonals1[currentRow + col] = true;
                occupiedDiagonals2[currentRow - col + size] = true;
                solve(size, currentRow + 1, arr, occupiedColumns, occupiedDiagonals1, occupiedDiagonals2);
                occupiedColumns[col] = false;
                occupiedDiagonals1[currentRow + col] = false;
                occupiedDiagonals2[currentRow - col + size] = false;
            }
        }
    }

    else {
        for (int col = 1; col <= size; col++) {
            if (occupiedColumns[col] == false && occupiedDiagonals1[currentRow + col] == false && occupiedDiagonals2[currentRow - col + size] == false) {
                arr[currentRow] = col;
                solutionCount++;
                if (!firstsolutionFound) {
                    firstsolutionFound = true;
                    for (int i = 1; i <= size; i++) {
                        output << arr[i] << " ";
                    }
                    output << "\n";
                }
            }
        }
    }
}

int main () {

    int n;
    input >> n;
    if (n == 1){
        output << 1 << "\n" << 1;
        return 0;
    }
    int arr[n+1];
    bool occupiedColumns[n+1] = {};
    bool occcupiedDiagonals1[2*n+1] = {};
    bool occcupiedDiagonals2[2*n+1] = {};
    solve(n, 1, arr, occupiedColumns, occcupiedDiagonals1, occcupiedDiagonals2);
    output << solutionCount;

    return 0;
}