[GZOI2017] 取石子游戏
题目背景
GZOI2017 D1T1
题目描述
Alice 和 Bob 在玩一个古老的游戏。现在有若干堆石子,Alice 和 Bob 轮流取,每次可以选择其中某一堆的石子中取出任意颗石子,但不能不取,谁先取完使得另一个人不能取了算赢。
现在场地上有 $N$ 堆石子,编号为 $1$ 至 $N$。Alice 很快发现了这个游戏存在一些固定的策略。阴险的 Alice 想赢得这场比赛就来找到主办方你,希望你在这 $N$ 堆石子中选出若干堆石子作为最后游戏用的石子堆并使得 Alice 能获得胜利。你自然不想让 Alice 得逞,所以你提出了一个条件:Alice 在这个游戏中第一次取的那堆石子的编号需要你来指定(仅指定取的石子堆编号,不指定第一次取多少个,这个指定的石子堆必然包含在最后游戏用的石子堆中)。
现在你很好奇,你想算算有多少种方案让 Alice 不能获胜。注意,即使选出的石子堆的编号的集合完全相同,指定第一次取的石子堆的编号不同,也认为方案是不同的。
输入输出格式
输入格式
第一行,一个正整数 $N$,表示石子堆数。
第二行,$N$ 个正整数,表示各堆石子的数量,按编号 $1$ 至 $N$ 依次给出。
输出格式
一行,表示方案数。答案对 $10^9+7$ 取模。
输入输出样例
输入样例 #1
3
2 4 5
输出样例 #1
5
输入样例 #2
3
1 2 2
输出样例 #2
6
说明
【样例 $1$ 解释】
第一种:选编号 $1$ 和编号 $2$,指定编号 $1$。
第二种:选编号 $1$ 和编号 $3$,指定编号 $1$。
第三种:选编号 $1$、编号 $2$ 和编号 $3$,指定编号 $2$。
第四种:选编号 $1$、编号 $2$ 和编号 $3$,指定编号 $3$。
第五种:选编号 $2$ 和编号 $3$,指定编号 $2$。
【数据约束】
| 数据编号 | $N$ | 每堆石子数量 |
| :-: | :-: | :-: |
| $1$ | $\le 5$ | $\le 5$ |
| $2$ | $\le 10$ | $\le 10$ |
| $3$ | $\le 100$ | $\le 100$ |
| $4$ | $\le 200$ | $\le 200$ |
| $5$ | $\le 200$ | $\le 200$ |