题目描述

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

输入描述

第一行输入一个正整数$n$，代表数组的大小。