#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
#define ll long long
#define ull unsigned long long
#define nmax 20
#define MOD 1999999973
#define INF 2123456789
//#define fin cin
//#define fout cout
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n;
int st[nmax], cnt;
int viz[nmax];
bool ok;
void Afis()
{
int i;
++cnt;
if (!ok)
{
for (i = 1; i <= n; i++)
fout << st[i] << " ";
fout << "\n";
}
ok = 1;
}
bool Valid(int top)
{
int i;
for (i = 1; i < top; i++)
if (top - i == abs(st[top] - st[i]))
return 0;
return 1;
}
void Back(int top)
{
if (top > n)
Afis();
else
for (int i = 1; i <= n; i++)
if (!viz[i])
{
st[top] = i;
viz[i] = 1;
if (Valid(top))
Back(top + 1);
viz[i] = 0;
}
}
int main()
{
fin >> n;
Back(1);
fout << cnt << "\n";
fin.close();
fout.close();
return 0;
}