#include <fstream>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n, k, cnt, s[15];
int diagprin[35], diagsec[35], col[15];
int valid(int k, int i){
if(col[i] == 1)
return 0;
if(diagprin[k+i-1] == 1)
return 0;
if(diagsec[n-k+i] == 1)
return 0;
return 1;
}
void perm(int k){
if(k == n+1){
cnt++;
if(cnt == 1){
for(int i=1; i<=n; i++)
fout << s[i] << ' ';
fout << '\n' << cnt+1;
}
}
else
for(int i=1; i<=n; i++)
if(valid(k, i)){
diagprin[k+i-1] = 1;
col[i]=1;
diagsec[n-k+i]=1;
s[k]=i;
perm(k + 1);
diagprin[k+i-1]=0;
col[i]=0;
diagsec[n-k+i]=0;
}
}
int main()
{
fin >> n;
perm(1);
return 0;
}