#include <bits/stdc++.h>
using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n, a[101][101]={0}, cnt=0;
bool found = false;

void afis()
{
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=n; j++)
			if(a[i][j])
            {
                fout<<j<<' ';
                break;
            }
	}
}

bool valid(int i, int j)
{
    for(int k=1; k<=n; k++)	
		if((a[i][k] && k!=j) || (a[k][j] && k!=i))
			return false;
    
    for(int row=i-1, col=j-1; row>=1 && col>=1; row--, col--)
        if(a[row][col])
            return false;
    
    for(int row=i-1, col=j+1; row>=1 && col<=n; row--, col++)
        if(a[row][col])
            return false;
    return true;
}

void back(int pas)
{
	if(pas == n+1)
    {
        if(!found)
            afis();
        found = true;
        cnt++;
    }
		
	
	for(int j=1; j<=n; j++)
	{
		a[pas][j] = 1;
		if(valid(pas, j))
			back(pas+1);
        a[pas][j] = 0;
	}	
}


void solve()
{
    fin>>n;
    back(1);
    fout<<'\n'<<cnt;
}


int main()
{
    solve();
    return 0;
}