题目描述

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

输入描述

第一行输入一个正整数$n(1\leq n \leq 10^5)$，代表数组的大小。

第二行输入$n$个整数$a_i(-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。