/**
 * Author: Andu Scheusan (not_andu)
 * Created: 09.09.2023 11:18:59
*/

#include <bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;

#define INFILE "damesah.in"
#define OUTFILE "damesah.out"
// #define INFILE "date.in"
// #define OUTFILE "date.out"

typedef long long ll;

const short VMAX = 15;

short n;
ll cnt = 0;
bool col[VMAX], diag1[VMAX], diag2[VMAX];
bool found = false;
vector<int> sol(VMAX);

void back(int y){
    
    if(y == n){

        if(!found){

            found = true;

            for(int i = 1; i <= n; ++i){

                cout << sol[i] << " ";

            }

            cout << '\n';

        }

        ++cnt;

        return;

    }

    for(int x = 0; x < n; ++x){

        if(col[x] == true || diag1[x + y] == true || diag2[x - y + n - 1] == true){

            continue;

        }

        sol[y + 1] = x + 1;

        col[x] = true;
        diag1[x + y] = true;
        diag2[x - y + n - 1] = true;

        back(y + 1);

        col[x] = false;
        diag1[x + y] = false;
        diag2[x - y + n - 1] = false;

    }

}

void solve(){

    cin >> n;

    back(0);

    cout << cnt << '\n';

}

int main(){
    
    ios_base::sync_with_stdio(false);

    freopen(INFILE, "r", stdin);
    freopen(OUTFILE, "w", stdout);

    cin.tie(nullptr);
    cout.tie(nullptr);

    solve();

    return 0;
}