#include<cstdio>
using namespace std;
int n,v[14],sol=0;
int b = 1;
int abs(int a)
{
    if(a>=0) return a;
       else return -a;
}
inline void wrt(int c)
{
    if(c)
    {
    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(b);b=0;}
      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;
}