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

ifstream fin("damesah.in");
ofstream fout("damesah.out");

int c[10];
int n;
int ma[15];
int s[15];

int verifica(int x,int k)
{
    for(int i=1;i<k;i++)
    {
        if(k + x == i + ma[i] || k-x == i-ma[i])
        {
            return 0;
        }
    }
    return 1;
}

int ok = 0;
int sol = 0;

void back(int k)
{
    if(k==n+1)
    {
        if(!ok)
        {
            for(int i=1;i<=n;i++)
                s[i] = ma[i];
            ok = 1;

        }
        sol++;
    }
    else
    {
        for(int i=1;i<=n;i++)
        {
            if(!c[i])
            {
                if(verifica(i,k))
                {
                    c[i] = 1;
                    ma[k] = i;
                    back(k+1);
                    c[i] = 0;
                }
            }
        }
    }
}


int main(){

    fin>>n;
    back(1);
    for(int i=1;i<=n;i++)
        fout<<s[i]<<" ";
    fout<<'\n';
    fout<<sol;

    return 0;
}