题目描述

将 $n$ 个不同的整数分成若干组（至少两组），要求每组都同时有奇数和偶数，并且存在和相等的组，问有多少种不同的分组方法。

输入格式

第 $1$ 行是一个正整数 $n$。

第 $2$ 行是 $n$ 个互不相同的整数。

输出格式

一个整数，就是满足条件的分组方法的数量。

输入输出样例

6
1 2 3 4 5 6

3

说明/提示

对于输入样例，满足条件的分组方法有下面 $3$ 种：

1 2 | 3 6 | 4 5 
1 4 | 2 3 | 5 6 
1 6 | 2 5 | 3 4

👀️ 对于$100\%$ 的数据，$2 \leq n \leq 12$，输入的整数绝对值不超过 $1000$。