← 返回题目列表

AtCoder · arc117_b

B. ARC 清障车

中文机器翻译题面 查看原题

分数: 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.