Problem D: 【中级组】素数环

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：237 Solved：82

Description

           有这样一个有趣的问题，输入n，然后取1<x<n中的数，围成一个环，使得相邻的两个数和为素数，并且第一个数一定是1，输出所有的可能序列有多少。比如说输入n=6，那么得到的序列是1 4 3 2 5 6、1 6 5 2 3 4这样两个序列，不难验证，这两个环是满足条件的（数字不重复）。
     现在要求输入一个n，求n个数围成一圈总共有多少种素数环( 不要求输出序列 )，规定第一个数字是1。




Input

      输入为一行，只有一个自然数 n 。

Output

      输出所有的可能的素数环序列总共有多少个。

Sample Input Copy 

6

Sample Output Copy 

2

HINT

提示:
  • 1 <= n <= 16 。
  • 数字不重复 。