解题思路

题目定义了一个数列 (F(x))，满足 (F(0)=1)，且对于 (x\ge 1)： [ F(x) = \left( x+1 + \sum_{i=0}^{x-1} (i+1) \cdot F(i) \right) \bmod (10^9+7) ]

题目内容

小蓝最近在研究一种特殊的递推数列，这种数列在数字增殖模型中经常出现。数列 $F$ 的定义如下：

• $F(0) = 1$。
• 对于任意正整数 $x$，有$$F(x) = \left( x+1 + \sum_{i=0}^{x-1} (i+1) \cdot F(i) \right) \bmod (10^9+7)$$

现在他获得了一个长度为 $n$ 的正整数序列 $a_1, a_2, \dots, a_n$。请你帮他计算所有 $F(a_i)$ 之和，即

由于结果可能很大，请输出 $S$ 对 $10^9+7$ 取模的结果。

数据规模与约定：序列长度 $n$ 不超过 $10^5$；每个 $a_i$ 均为正整数且不超过 $10^5$。

输入描述

第一行包含一个整数 $n$，表示序列的长度。 第二行包含 $n$ 个正整数，第 $i$ 个数为 $a_i$，相邻整数之间用空格分隔。

输出描述

输出一个整数，表示 $\sum_{i=1}^n F(a_i)$ 对 $10^9+7$ 取模的结果。

样例1

输入

1
1

输出

3

说明

序列中只有一个元素 $a_1 = 1$，因此需要计算 $F(1)$。 已知 $F(0)=1$。根据递推式：

求和项只有 $i=0$：$(0+1) \cdot F(0) = 1 \cdot 1 = 1$。 于是 $F(1) = (2 + 1) \bmod (10^9+7) = 3$。答案为 3。

样例2

输入

3
2 3 4

输出

257

说明

序列包含三个元素 $2, 3, 4$。我们依次递推计算 $F$ 的值：

• $F(0)=1$，前缀和 $S_0 = 1 \times F(0) = 1$。
• $F(1)=2 + S_0 = 3$，更新 $S_1 = 1 + 2 \times 3 = 7$。
• $F(2)=3 + S_1 = 10$，更新 $S_2 = 7 + 3 \times 10 = 37$。
• $F(3)=4 + S_2 = 41$，更新 $S_3 = 37 + 4 \times 41 = 201$。
• $F(4)=5 + S_3 = 206$。 因此 $F(2)=10$，$F(3)=41$，$F(4)=206$。总和为 $10+41+206=257$，对 $10^9+7$ 取模后仍为 257。

样例3

输入

2
5 5

输出

2474

说明

序列包含两个 $5$，需要计算 $2 \times F(5)$。 由前面的递推已知 $S_3 = 201$，$F(4)=206$，计算得 $S_4 = 201 + 5 \times 206 = 1231$。 于是 $F(5) = 6 + S_4 = 6 + 1231 = 1237$。 总和为 $1237 + 1237 = 2474$，模 $10^9+7$ 后仍为 2474。