如果一个数除以 $p$ 的余数是偶数，则称该数为 $mopadulo_p$。我们不知道除了 $10^9 + 7$ 以外的其他大质数，因此我们只考虑 $mopadulo_{1\,000\,000\,007}$。

请计算有多少种方法可以将给定的数列 $a_1, a_2, \dots, a_n$ 分割成若干个区间，使得每个区间内所有数字之和均为 $mopadulo_{1\,000\,000\,007}$。在这种分割中，数列中的每个元素必须恰好属于一个区间。由于分割方案的数量可能非常大，你只需要输出其对 $10^9 + 7$ 取模后的结果。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 300\,000$)，表示给定数列的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i < 10^9 + 7$)。

输出格式

输出一个整数，表示将数列 $a_1, a_2, \dots, a_n$ 分割成符合条件的区间的方案数，对 $10^9 + 7$ 取模后的结果。

样例

输入 1

4
1000000006 1 5 1000000004

输出 1

3

说明 1

合法的区间分割方式为： $[1000000006, 1, 5, 1000000004]$ $[1000000006, 1], [5, 1000000004]$ * $[1000000006], [1, 5], [1000000004]$

子任务

• 在某些测试组中，$a_i \le 100$。
• 在其他测试组中，$n \le 3000$。

在上述两种情况下，均至少存在一组测试数据。