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