#include <iostream>
#include <fstream>
#include <string.h>
//#include <vector>
//#include <queue>
//#include <stack>
//#include <algorithm>

using namespace std;

#define mpair make_pair
#define endl "\n"
#define c_false ios_base::sync_with_stdio(false); cin.tie(0)
#define pushb push_back
#define pushf push_front
#define popb pop_back
#define popf pop_front
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define X first
#define Y second
#define ashar(a) cout << fixed << setprecision((a))
#define reset(a,b) memset(a, b, sizeof(a))
#define for0(a, n) for (int (a) = 0; (a) < (n); (a)++)
#define for1(a, n) for (int (a) = 1; (a) <= (n); (a)++)

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;

ll lnno(ll a, ll b) { return (a ? lnno(b%a, a) : b); }
ll power(ll a, ll n) { ll p = 1; while (n > 0) { if (n % 2) { p = p * a; } n >>= 1; a *= a; } return p; }
ll power(ll a, ll n, ll mod) { ll p = 1; while (n > 0) { if (n % 2) { p = p * a; p %= mod; } n >>= 1; a *= a; a %= mod; } return p % mod; }

const int INF = 0x3f3f3f3f, MOD = 1e9 + 7;
const int n_ = 1e5 + 1000;
//const ld  PI = acos(-1.0);

//////////////////////////// START THE CODE WRITING ////////////////////////////
 
int v[20] , lin[20] , des[40], cres[40];
int n, res = 0;
bool firstTime = true;

bool valid(int k, int val) {
	if (lin[val] != 0) return false;
	if (cres[k + val - 1] != 0) return false;
	if (des[n - k + val ] != 0) return false;
	return true;
}

bool solutie(int k) {
	return k == n;
}

void afisare(){
	for (int i = n; i > 0 ; i--)
	{
		cout << v[i] << " ";
	}
	cout << endl;
}

void bt(int k){
	
	for (int i = 1; i <= n; i++) {
		if ( valid(k, i) ) {
			v[k] = i;
			if (solutie(k)) {
				if (firstTime) { afisare();  firstTime = false; }
				res++;
			}
			else {
				lin[i]				= 1;
				cres[k + i - 1]		= 1;
				des[n - k + i ]		= 1;
				bt(k + 1);
				des[n - k + i ]		= 0;
				cres[k + i - 1]		= 0;
				lin[i]				= 0;
			}

		}
	}
}



int main(){
	c_false;
	freopen("damesah.in", "r", stdin);
	freopen("damesah.out", "w", stdout);
	
	cin >> n;

	bt(1);
	
	cout << res << endl;
	fclose(stdin);
	fclose(stdout);
	return 0;
}