Migrated from Lutece 2561 土豆的子序列

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

土豆有一个包含 $n$ 个正整数的序列，他想问你这里面不同的非空不下降子序列都有哪些。

由于 $n$ 太大了，土豆觉得你不可能在一秒内回答上来，于是决定用非空不下降子序列中各元素乘积来代表这个子序列。

为了节约更多的时间，他想到了一个好办法，就是只用一个数来表示所有非空不下降子序列，这个数等于所有非空不下降子序列的代表值的和。

他想问你这个数是多少，如果太大了，那就对 $10^9+7$ 取模。

Input

第一行一个正整数 $n$。

第二行 $n$ 个正整数，表示 $a_1, a_2, \ldots , a_n$ 。

Output

一个整数，表示代表值的和对 $10^9+7$ 取模后的结果。

Samples

3
2 2 2

14

6
1 1 4 5 1 4

142

Constraints

$1\le n\le 10^5$ $1\le a_i\le 10^6$

Note

样例中不同的非空不下降子序列有 $(2),(2,2),(2,2,2)$，代表值之和为 $2+4+8=14$。

Resources

2021 UESTC ICPC Training for Dynamic Programming