题目描述

小北是一家快递中转站的调度员。今天，他面前有 $n$ 个包裹，依次编号为 $1$ 到 $n$，第 $i$ 个包裹的重量为 $a_i$ 千克。

根据最新的运输安全条例，一辆货车装车后，车上所有包裹的总重量必须是 $8$ 的倍数，否则车辆行驶时容易发生重心偏移，存在安全隐患。

由于包裹无法分割，小北只能在装车前丢弃一部分包裹（当然，他也可以一个都不丢，或者把所有包裹全部丢弃，空车不发车也算一种 “方案”）。剩余未被丢弃的包裹将被装车运走。

现在小北想知道：在所有的选择中，一共有多少种丢弃包裹的方案，能使得最终装车的包裹总重量恰好是 $8$ 的倍数？

输入格式

第一行包含一个整数 $n$，表示包裹的总数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，相邻整数之间用一个空格分隔，表示每个包裹的重量（单位：千克）。

输出格式

输出一个整数，表示满足条件的丢弃方案数。

样例

4
1 2 3 4

2

3
8 16 24

8

样例1解释

四件包裹重量分别为 $1, 2, 3, 4$ 千克。

• 丢弃全部包裹，车上剩余总重量为 $0$ 千克，$0$ 是 $8$ 的倍数，符合要求，此为一种方案。
• 只丢弃重量为 $2$ 的包裹，保留 $[1, 3, 4]$，总重量为 $8$ 千克，是 $8$ 的倍数，此为第二种方案。

其余丢弃方式得到的总重量均不是 $8$ 的倍数。因此共有 $2$ 种可行方案。

样例2解释

三件包裹的重量本身就是 $8$ 的倍数。无论丢弃哪些，保留包裹的总重量始终是 $8$ 的倍数。每件包裹都有 “丢弃” 与 “保留” 两种独立选择，因此总方案数为 $2^3 = 8$。

数据范围

对于 $100\%$ 的数据，$1\le n\le 20$，$1\le a_i\le 10^6$。