#include <bits/stdc++.h>
using namespace std;
 
#define pb push_back
#define mp make_pair
#define dbg(x) cout << #x <<": " << x << "\n";
#define sz(x) ((int)x.size())
 
using ll = long long;
 
const string fn = "damesah";
ifstream fin(fn + ".in");
ofstream fout(fn + ".out");

int n;
int ans;

int x[20], viz[20];
int prin[20], sec[20];

void good(){
    ans++;
    if(ans == 1){
        for(int i = 1; i <= n; ++i)
            fout << x[i] << " ";
        fout << '\n';
    }
}


inline bool ok(int i, int j){

    return !(viz[j] || prin[n - j + i] || sec[i + j - 1]);

}


void Back(int i){
   
    if(i == n + 1)
        good();
    else for(int j = 1; j <= n; ++j){
        if(ok(i, j)){

            x[i] = j;
            viz[j] = 1;
            prin[n - j + i] = 1;
            sec[i + j - 1] = 1;
            Back(i + 1);
            viz[j] = 0;
            prin[n - j + i] = 0;
            sec[i + j - 1] = 0;
            
        }
    }

}


int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie();
	
    fin >> n;
    Back(1);
    fout << ans << '\n';

    return 0;
}