#include <iostream>
#include <cmath>
#include <fstream>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int i,k,Sol,n;
int c[13],sol[13];
void Afisare(int n)
{
for(i=1; i<=n; i++)
sol[i]=c[i];
}
bool check(int k)
{
for(i=1; i<k; i++)
if(c[k]==c[i] || k-i==abs(c[k]-c[i]))
return false;
return true;
}
int PlasareDame(int n)
{
k=1;
c[k]=0;
int nrSol=0;
bool ok=1;
while(k>0)
{
Sol=0;
while(c[k]<n && !Sol)
c[k]++,Sol=check(k);
if(!Sol)
k--;
else
{
if(k!=n)
k++,c[k]=0;
else
{if(ok)
Afisare(n),ok=0;
nrSol++;}
}
}
return nrSol;
}
int main()
{
f>>n;
int nrSol=PlasareDame(n);
for(i=1;i<=n;i++)
g<<sol[i]<<" ";
g<<"\n";
g<<nrSol;
return 0;
}