分数: 400 点
问题陈述
有 N AtCoder 路沿线的建筑物。最初, i左边第 1 栋楼有 A_i 故事。
ARC Wrecker, Inc. 总裁 Takahashi 可以执行以下操作任意次数,可能为零:
- 选择一个正整数 X 他喜欢并在那个高度发射炮弹,该高度减少 1 每栋建筑的层数 X 或更多故事。
求建筑物最终可能场景的数量,模 (10^{9} + 7).
当满足以下条件时,我们认为两个场景 A 和 B 是不同的:
- 让 P_i 是故事的数量 i场景 A 中左起第 1 栋建筑;
- 让 Q_i 是故事的数量 i风景 B 中左起第 1 栋建筑;
- 当场景 A 和 B 不同时,我们认为场景 A 和 B 是不同的 P_i \neq Q_i 对于一个或多个索引 i.
约束
- 1 \leq N \leq 100000
- 1 \leq A_i \leq 10^{9}
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \cdots A_N
输出
打印答案。
示例输入 1
2 1 2
示例输出 1
4
建筑物的高度有四种可能的组合,如下所示:
- (大楼 1,建筑 2) = (0, 0)
- (大楼 1,建筑 2) = (0, 1)
- (大楼 1,建筑 2) = (1, 1)
- (大楼 1,建筑 2) = (1, 2)
示例输入 2
6 5 3 4 1 5 2
示例输出 2
32
示例输入 3
7 314 159 265 358 979 323 846
示例输出 3
492018656
有 20192492160000 可能的最终场景。正确的输出是该数模 10^{9} + 7,即 492018656.