题解

抽象一下题意，给定 $n$ 个数 $a_i$，随机排列后求有多少种情况满足相邻的两个数的和都是素数。

原题给的 $n$ 最大为12， 这样直接暴力是很大概率超时的，需要用状压DP来解决，比较繁琐。

根据塔子哥的群友描述，本题直接暴力在机试的时候也是能够全过的，因此本题将数据范围缩小至 $n \le 8$

题目描述

小红拿到了 $n$ 个数 $a_i$ ，他想知道，使用这些数构造一个长度为 $n$ 的数组，且满足相邻两个数的和均为素数，共有多少种不同的数组构造方案。

输入描述

第一行，一个整数表示数组长度 $n$

第二行，$n$ 个整数表示数组中的每个数

$1\leq n\leq 8$

$1\leq a_i\leq 10^9$

输出描述

一个整数，表示不同的数组构造方案数

样例1

输入

3
1 1 2

输出

3

样例2

输入

2
2 2

输出

0