T4 大胃王争霸

题目信息

时间限制: 1s

空间限制: 512M

输入文件: stone.in

输出文件: stone.out

题目描述

可达鸭和呆河马正在竞争宝可梦大胃王头衔，大胃王决赛中有 $n$ 堆苹果，第 $i$ 堆苹果有 $x_i$ 个，可达鸭每次会挑选一堆苹果并吃掉 $a$ 个，呆河马每次会挑选一堆苹果然后吃掉 $b$ 个，没办法吃指定数量苹果的神奇宝贝就输了。

因为可达鸭和呆河马都是谦恭礼让的神奇宝贝，所以直到比赛开始前，它们还没有确定先后手顺序。于是聪明的皮卡丘发现了大胃王比赛的华点：一场比赛的结果要么是可达鸭必胜，要么是呆河马必胜，要么是先吃苹果的神奇宝贝必胜，要么是后吃苹果的神奇宝贝必胜。

进而，如果只选定若干堆苹果（共有 $2^n$ 种方案），可达鸭和呆河马只能在选出的苹果堆中吃苹果，那么以上四种情况对应的方案数分别是多少呢？答案对 $10^9+7$ 取模。

输入格式

首行是一个正整数 $T$，表示有 $T$ 个不同的情况。

接下来的行中，按顺序给出每个情况的描述。每个描述的格式如下：

首行是一个正整数 $N$。

第二行是一个非负整数序列 $a_1,a_2,\cdots,a_n$，代表黑板上写的数字。这些数字不一定是不同的。

输出格式

一行四个整数，分别表示可达鸭必胜，呆河马必胜，先吃苹果的神奇宝贝必胜，后吃苹果的神奇宝贝必胜的方案数，对 $10^9+7$ 取模

样例

样例输入 1

2 2 3
2 3

样例输出 1

2 0 1 1

样例解释 1

选定空集时后吃苹果的神奇宝贝必胜，选定 $\{2\}$ 时可达鸭必胜，选定 $\{3\}$ 时先吃苹果的神奇宝贝必胜，选定 $\{2,3\}$ 时可达鸭必胜。

数据范围与提示

• 对于 $10 \%$ 的数据，$n, x_i<=5$
• 对于 $50 \%$ 的数据，$\mathrm{n}<=20$
• 对于另外 $10 \%$ 的数据，$a=b$
• 对于又另外 $20 \%$ 的数据，$a=1$
• 对于 $100 \%$ 的数据，$1<=\mathrm{n}<=100000,1<=\mathrm{a}, \mathrm{b}, \mathrm{xi}<=10^9$