#include<fstream>
using namespace std;
ifstream in("damesah.in");
ofstream out("damesah.out");
int n,v[14],sol=0;
int b = 1;
int abs(int a)
{
    if(a>=0) return a;
       else return -a;
}
void wrt(int c)
{
    if(c)
    {
    for(int i = 1 ; i<=n ; i++)
        out<<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()
{
   in>>n;
    back(1);
    out<<"\n"<<sol;
    in.close();
    out.close();
    return 0;
}