给定一个非负整数序列 $a_1, a_2, \dots, a_n$。基于该序列，我们构造一个整数序列 $b_1, b_2, \dots, b_n$，其中对于每个 $i$，都有 $b_i = 2^{a_i}$。

序列 $b_1, b_2, \dots, b_n$ 的一个划分是指将其划分为若干个连续的区间，使得每个元素恰好属于一个区间。如果一个划分中每个区间的数字之和都是 2 的幂（指数为整数），则称该划分为“好的”。

你的任务是计算序列 $b_1, b_2, \dots, b_n$ 的好的划分的数量。由于这个数字可能非常大，你只需要输出其对 $10^9 + 7$ 取模后的余数。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 3 \cdot 10^5$)，表示序列 $a_1, a_2, \dots, a_n$ 的长度（即序列 $b_1, b_2, \dots, b_n$ 的长度）。

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

输出格式

输出一个整数，表示好的划分数量对 $10^9 + 7$ 取模后的余数。

样例

输入 1

5
2 0 0 1 1

输出 1

6

说明

样例测试中的序列 $b_1, b_2, \dots, b_n$ 为 $4, 1, 1, 2, 2$。其好的划分包括：

• $[4], [1], [1], [2], [2]$
• $[4], [1, 1], [2], [2]$
• $[4], [1], [1], [2, 2]$
• $[4], [1, 1], [2, 2]$
• $[4], [1, 1, 2], [2]$
• $[4, 1, 1, 2], [2]$