#P18134. Power Divisions

Power Divisions

Power Divisions

给定长度为 nn 的非负整数序列 a1,…,ana_1,\dots,a_n,令

bi=2ai.b_i=2^{a_i}.

把 bb 分成若干连续区间。若每个区间的元素和都恰好是 2 的整数次幂,则称这个划分为好划分。

求好划分的数量,对 109+710^9+7 取模。

输入格式

第一行包含整数 nn,满足 1≤n≤3⋅1051\le n\le3\cdot10^5。

第二行包含 nn 个整数 a1,…,ana_1,\dots,a_n,满足 0≤ai≤1060\le a_i\le10^6。

输出格式

输出好划分数量模 109+710^9+7 的结果。

样例

5
2 0 0 1 1
6

此时 b=(4,1,1,2,2)b=(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]