#include<cstdio>
using namespace std;
int n,v[13];
int sol;
int abs(int k)
{
    if(k>=0) return k;
      else return -k;
}
inline void wrt()
{
    if(!sol)
    {
    for(int i = 1 ; i<=n ; i++)
       printf("%d ",v[i]);    }

    sol++;
}

int valid(int k)
{
    int i;
    for(i=1 ; i<=k-1 ; i++)
        if ((v[i]==v[k]) || (abs(k-i)==abs(v[k]-v[i]))) return 0;
    return 1;


}

void back(int m)
{
    if(m==n+1) wrt();
      else
      {

          for(int i = 1 ; i<=n ; i++)
          {
              v[m]=i;
              if(valid(m)) back(m+1);
          }
      }
}

int main()
{
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);
    scanf("%d",&n);
    back(1);
    printf("\n%d",sol);
    return 0;
}