In Spring Time University (STU), there is a small park. The roads of the park looks like an M*M chessboard. There is only two gate, one is in the northwest of the park,the other is in the southwest of the park . LJ wants to stroll through the park and pass through all the crossing, but he doesn't know how many ways he can do that,please help him.

  

Now, this is one way to stroll through a 3*3 park.



Input
each input line contains one small number M (2<=M<=6)

  

Output
each output line also contains only one number W----the ways.

  

Sample Input
2

Sample Output
2
这是题的网址http://acm.stu.edu.cn/cgi-bin/problem?id=1031
下面是我的程序
#include<stdio.h>
int jzh[10][10],point;long num;
find(int i,int j,int n)
  { if ((i==n)&&(j==0)&&(point==((n+1)*(n+1)-1)))
         num++;
    if ((i<n)&&(jzh[i+1][j]))
     { jzh[i+1][j]=0;
        point++;
       find(i+1,j,n);
       jzh[i+1][j]=1;
        point--;
      }
     if ((j<n)&&(jzh[i][j+1]))
    { jzh[i][j+1]=0;
        point++;
       find(i,j+1,n);
       jzh[i][j+1]=1;
        point--;
      }
    if ((i>0)&&(jzh[i-1][j]))
     { jzh[i-1][j]=0;
        point++;
       find(i-1,j,n);
       jzh[i-1][j]=1;
        point--;
      }
    if ((j>0)&&(jzh[i][j-1]))
    { jzh[i][j-1]=0;
        point++;
       find(i,j-1,n);
       jzh[i][j-1]=1;
        point--;
      }
   }
int main()

  {  int n,j,i;
     while(scanf("%d",&n)!=EOF)
      { point=0;num=0;
        for(i=0;i<=n;i++)
         for(j=0;j<=n;j++)
           jzh[i][j]=1;
           jzh[0][0]=0;
        i=j=0;
        find(i,j,n);
        printf("%ld\n",num);
       }
   }