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

using namespace std;

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

const int VMAX  = 14;

int n;
int ans[VMAX], counter = 0;
bool oriz[VMAX], diag1[2 * VMAX], diag2[2 * VMAX];
bool found = false;

void back(int pos = 1){

    if (pos == n + 1){

        if (!found) {

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

                cout << ans[i] << ' ';

            }

            cout << '\n';
        }

        found = 1;

        ++counter;
    }

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

        if (!oriz[i] && !diag1[n + pos - i] && !diag2[pos + i]){

            ans[pos] = i;

            oriz[i] = true;
            diag1[n + pos - i] = true;
            diag2[pos + i] = true;

            back(pos + 1);

            oriz[i] = false;
            diag1[n + pos - i] = false;
            diag2[pos + i] = false;

        }
    }
}

void solve(){

    cin >> n;

    back();

    cout << counter << '\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;
}