#include <bits/stdc++.h>
using namespace std;
template <typename T>
ostream& operator<<(ostream& o, const vector<T>& v);
const int N = 110005;
const long long MOD = 1000000007;
vector<int> sorted;
vector<long long> hm;
struct sum_tree {
  static const long long S = 1 << 20;
  long long n, s;
  vector<long long> v;
  void init(long long n_) {
    n = n_;
    s = 1;
    while (s < n) s <<= 1;
    v.resize(2 * s, 0);
  };
  void set(long long pos, long long val) {
    assert(0 <= pos && pos < n);
    pos += s;
    val %= MOD;
    v[pos] = val;
    pos >>= 1;
    while (pos >= 1) {
      v[pos] = v[pos * 2] + v[pos * 2 + 1];
      pos >>= 1;
      v[pos] %= MOD;
    }
  }
  long long getsum(long long a, long long b) {
    if (a > b) return 0;
    assert(0 <= a && a <= b && b < n);
    a += s;
    b += s;
    long long res = v[a] % MOD;
    if (a != b) res += v[b];
    while ((a >> 1) != (b >> 1)) {
      if ((a & 1) == 0) res += v[a + 1];
      if ((b & 1) == 1) res += v[b - 1];
      a >>= 1;
      b >>= 1;
      res %= MOD;
    }
    return res;
  }
} ST;
vector<long long> res;
vector<long long> pwcnt;
vector<long long> cnt;
void update(long long x) {
  long long pos = lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin();
  pwcnt[pos] *= x;
  pwcnt[pos] %= MOD;
  long long& tmp = res[pos];
  tmp *= x;
  tmp += (ST.getsum(0, pos - 1) + 1) * x;
  tmp %= MOD;
  res[pos] = tmp;
  ST.set(pos, tmp);
}
int main() {
  int n;
  scanf("%d", &n);
  vector<int> seq(n, -1);
  for (int i = 0; i < (n); i++) scanf("%d", &seq[i]);
  {
    sorted = seq;
    sort(sorted.begin(), sorted.end());
    int d = unique(sorted.begin(), sorted.end()) - sorted.begin();
    sorted.resize(d);
    ST.init(d);
    res.resize(d, 0);
    pwcnt.resize(d, 1);
  }
  for (__typeof((seq).begin()) x = (seq).begin(); x != (seq).end(); x++) {
    update(*x);
  }
  long long ans = 0;
  for (__typeof((res).begin()) x = (res).begin(); x != (res).end(); x++) {
    ans += *x;
    ans %= MOD;
  }
  printf("%d\n", (int)ans);
}
template <typename T>
ostream& operator<<(ostream& o, const vector<T>& v) {
  o << "[";
  bool first = true;
  for (__typeof((v).begin()) x = (v).begin(); x != (v).end(); x++) {
    if (!first) {
      o << ", ";
    }
    o << *x;
    first = false;
  }
  o << "]";
  return o;
}

### Prompt

Construct a CPP code solution to the problem outlined:

Sereja has a sequence that consists of n positive integers, a1, a2, ..., an. 

First Sereja took a piece of squared paper and wrote all distinct non-empty non-decreasing subsequences of sequence a. Then for each sequence written on the squared paper, Sereja wrote on a piece of lines paper all sequences that do not exceed it.

A sequence of positive integers x = x1, x2, ..., xr doesn't exceed a sequence of positive integers y = y1, y2, ..., yr, if the following inequation holds: x1 ≤ y1, x2 ≤ y2, ..., xr ≤ yr.

Now Sereja wonders, how many sequences are written on the lines piece of paper. Help Sereja, find the required quantity modulo 1000000007 (109 + 7). 

Input

The first line contains integer n (1 ≤ n ≤ 105). The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 106).

Output

In the single line print the answer to the problem modulo 1000000007 (109 + 7).

Examples

Input

1
42


Output

42


Input

3
1 2 2


Output

13


Input

5
1 2 3 4 5


Output

719

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
ostream& operator<<(ostream& o, const vector<T>& v);
const int N = 110005;
const long long MOD = 1000000007;
vector<int> sorted;
vector<long long> hm;
struct sum_tree {
  static const long long S = 1 << 20;
  long long n, s;
  vector<long long> v;
  void init(long long n_) {
    n = n_;
    s = 1;
    while (s < n) s <<= 1;
    v.resize(2 * s, 0);
  };
  void set(long long pos, long long val) {
    assert(0 <= pos && pos < n);
    pos += s;
    val %= MOD;
    v[pos] = val;
    pos >>= 1;
    while (pos >= 1) {
      v[pos] = v[pos * 2] + v[pos * 2 + 1];
      pos >>= 1;
      v[pos] %= MOD;
    }
  }
  long long getsum(long long a, long long b) {
    if (a > b) return 0;
    assert(0 <= a && a <= b && b < n);
    a += s;
    b += s;
    long long res = v[a] % MOD;
    if (a != b) res += v[b];
    while ((a >> 1) != (b >> 1)) {
      if ((a & 1) == 0) res += v[a + 1];
      if ((b & 1) == 1) res += v[b - 1];
      a >>= 1;
      b >>= 1;
      res %= MOD;
    }
    return res;
  }
} ST;
vector<long long> res;
vector<long long> pwcnt;
vector<long long> cnt;
void update(long long x) {
  long long pos = lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin();
  pwcnt[pos] *= x;
  pwcnt[pos] %= MOD;
  long long& tmp = res[pos];
  tmp *= x;
  tmp += (ST.getsum(0, pos - 1) + 1) * x;
  tmp %= MOD;
  res[pos] = tmp;
  ST.set(pos, tmp);
}
int main() {
  int n;
  scanf("%d", &n);
  vector<int> seq(n, -1);
  for (int i = 0; i < (n); i++) scanf("%d", &seq[i]);
  {
    sorted = seq;
    sort(sorted.begin(), sorted.end());
    int d = unique(sorted.begin(), sorted.end()) - sorted.begin();
    sorted.resize(d);
    ST.init(d);
    res.resize(d, 0);
    pwcnt.resize(d, 1);
  }
  for (__typeof((seq).begin()) x = (seq).begin(); x != (seq).end(); x++) {
    update(*x);
  }
  long long ans = 0;
  for (__typeof((res).begin()) x = (res).begin(); x != (res).end(); x++) {
    ans += *x;
    ans %= MOD;
  }
  printf("%d\n", (int)ans);
}
template <typename T>
ostream& operator<<(ostream& o, const vector<T>& v) {
  o << "[";
  bool first = true;
  for (__typeof((v).begin()) x = (v).begin(); x != (v).end(); x++) {
    if (!first) {
      o << ", ";
    }
    o << *x;
    first = false;
  }
  o << "]";
  return o;
}

```