#include <fstream>
#include <vector>
//#include <climits>

using namespace std;
ifstream cin("damesah.in");
ofstream cout("damesah.out");
int n;
vector<int>coloana;
bool exista[15],diag1[30],diag2[30];
int cnt=0;
void backtracking(int val)
{
    if(val>n)
    {
        cnt++;
        if(cnt==1)
            for(int i=0; i<coloana.size(); i++)
            cout<<coloana[i]<<" ";
        return;
    }
    else
    {
        for(int i=1; i<=n; i++)
        {
            if(!exista[i] && !diag1[val-i+n] && !diag2[val+i])
            {
                exista[i]=1;
                diag1[val-i+n]=1;
                diag2[val+i]=1;
                coloana.push_back(i);
                backtracking(val+1);
                coloana.pop_back();
                exista[i]=0;
                diag1[val-i+n]=0;
                diag2[val+i]=0;
            }
        }
    }
}
int main()
{
    cin>>n;
    backtracking(1);
    cout<<'\n'<<cnt;
    return 0;
}