#include <iostream>
#include <fstream>
#include <queue>
#include <set>
#include <algorithm>
#include <stack>
#include <vector>
#include <iomanip>
#include <cstdio>

using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

int x[13];
int solutie[13];

void tipareste(int n) {
	for (int i = 1; i <= n; ++i)
		solutie[i] = x[i];
}

bool OK(int k) {
	for (int i = 1; i < k; ++i)
		if (x[k] == x[i] || k - i == abs(x[k] - x[i]))
			return false;

	return true;
}

int backtrack(int n) {
	int eSolutie, k;
	k = 1;
	x[1] = 0;

	int nrSolutii = 0;
	int prima = 1;

	while (k > 0) {
		eSolutie = 0;

		while (x[k] < n && !eSolutie) {
			x[k]++;
			eSolutie = OK(k);
		}

		if (!eSolutie)
			k--;

		else {
			if (k == n) {
				if (prima) {
					tipareste(n);
					prima = 0;
				}
				nrSolutii++;
			}
			else {
				k++;
				x[k] = 0;
			}
		}
	}
	return nrSolutii;
}

int main() {
	int n, k, eSolutie;
	fin >> n;

	int nrSolutii = backtrack(n);

	for (int i = 1; i <= n; ++i)
		fout << solutie[i];

	fout << "\n" << nrSolutii;

	return 0;
}