#include <cstdio>
#include <cstdlib>

using namespace std;

int n,nr,sol[15];

bool succesor (int k)
{
    if (sol[k]<n)
    {
        sol[k]++;
        return 1;
    }
    else
        return 0;
}
bool valid(int k)
{
    for ( int i = 1 ; i < k ; ++i )
        if (sol[i]==sol[k])return 0;
    for ( int i = 1 ; i < k ; ++i )
        if ((k-i)==abs(sol[k]-sol[i]))return 0;
    return 1;

}
void back(int k)
{
    sol[k]=0;
    if (k==n+1)
    {
        nr++;
        if (nr==1)
        for (int i = 1 ; i <= n ; ++i )
            printf ("%d ",sol[i]);
    }
    else
        while(succesor(k))
            if(valid(k))
                back(k+1);
}
int main()
{
    freopen ("damesah.in" , "r" , stdin );
    freopen ("damesah.out" , "w" , stdout );
    scanf("%d",&n);
    back(1);
    printf("\n%d",nr);
    return 0;
}