← 返回题目列表

Codeforces · 314/C

C. Sereja 和后续

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

Sereja 有一个由 n 个正整数 a1, a2, ..., an 组成的序列。

首先,Sereja 拿了一张方格纸,写下了序列 a 的所有不同的非空非递减子序列。然后,对于写在方格纸上的每个序列,Sereja 在一张线条纸上写下了所有不超过它的序列。

如果以下不等式成立,则正整数 x = x1, x2, ..., xr 的序列不超过正整数 y = y1, y2, ..., yr 的序列:x1 ≤ y1, x2 ≤ y2, ..., xr ≤ yr。

现在Sereja 想知道,有多少序列写在纸上。帮助 Sereja,找到所需数量对 1000000007 (109 + 7) 求模。

输入

第一行包含整数 n (1 ≤ n ≤ 105)。第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 106)。

输出

在单行中打印以 1000000007 (109 + 7) 为模的问题的答案。

示例

输入 #1

1
42

输出 #1

42

输入 #2

3
1 2 2

输出 #2

13

输入 #3

5
1 2 3 4 5

输出 #3

719