题解

经典的数数题

先分别统计数组中 1、-1 和 0 的个数,记为 $a$、$b$ 和 $c$。

对于乘积为负数的情况,需要选择奇数个 -1,其余的 1 和 -1 可以任意选择。因此,乘积为负数的方案数为:

题目描述

小红拿到了一个数组，数组的元素的绝对值不超过 1，她想取一个非空子序列（在原数组中可以不连续），并计算该子序列的乘积。 小红想知道，子序列乘积为 -1、0、1 的方案数分别有多少种？

输入描述

第一行输入一个正整数$n$，代表数组的大小。 第二行输入$n$个整数$a_i$，代表数组的元素。 $1\leq n \leq 10^5$ $-1 \leq a_i \leq 1$

输出描述

三个整数，分别代表子序列乘积为负数、0、正数的方案数。由于答案可能过大，请对$10^9+7$取模。

样例

输入

4
-1 0 -1 1

输出

4 8 3

说明

长度为 1 的子序列共有 4 个，乘积为 -1 的有 2 个，乘积为 0 的有 1 个，乘积为 1 的有 1 个。
长度为 2 的子序列共有 6 个，乘积为 -1 的有 2 个，乘积为 0 的有 3 个，乘积为 1 的有 1 个。
长度为 3 的子序列共有 4 个，乘积为 -1 的有 0 个，乘积为 0 的有 3 个，乘积为 1 的有 1 个。
长度为 4 的子序列只有 1 个，乘积为 0。