#include <bits/stdc++.h>
using namespace std;
template <typename T, typename Lambda>
struct segment_tree {
  vector<T> tree;
  T neutral;
  Lambda join;
  int size, real_size;
  segment_tree() {}
  template <typename L>
  segment_tree(int _size, const T &_neutral, const L &f) : join(f) {
    real_size = _size;
    size = nxt(_size);
    tree = vector<T>(2 * size + 1);
    neutral = _neutral;
  }
  int nxt(int x) {
    int i = 1;
    while (i < x) {
      i <<= 1;
    }
    return i;
  }
  void init(const vector<T> &v) {
    for (int i = 0; i < real_size; ++i) {
      tree[i + size] = v[i];
    }
    for (int i = size - 1; i >= 0; --i) {
      tree[i] = join(tree[i << 1], tree[i << 1 | 1]);
    }
  }
  void point_update(int id, const T &val) { point_update_iterative(id, val); }
  void point_update_iterative(int id, const T &val) {
    id += size - 1;
    tree[id] = val;
    id >>= 1;
    while (id > 0) {
      tree[id] = join(tree[id << 1], tree[id << 1 | 1]);
      id >>= 1;
    }
  }
  void point_update(int l, int r, int x, const T &val, int p) {
    if (l > x || r < x) {
      return;
    }
    if (l == r) {
      tree[p] = val;
      return;
    }
    int middle = l + r >> 1;
    point_update(l, middle, x, val, p << 1);
    point_update(middle + 1, r, x, val, p << 1 | 1);
    tree[p] = join(tree[p << 1], tree[p << 1 | 1]);
  }
  T get(int id) { return query(id, id); }
  T query(int L, int R) { return query_iterative(L, R); }
  T query_iterative(int L, int R) {
    L += size - 1;
    R += size - 1;
    T ans = neutral;
    while (L <= R) {
      if (L & 1) {
        ans = join(ans, tree[L++]);
      }
      if (!(R & 1)) {
        ans = join(ans, tree[R--]);
      }
      L >>= 1;
      R >>= 1;
    }
    return ans;
  }
  T query(int l, int r, int L, int R, int p) {
    if (L > r || l > R) return neutral;
    if (L <= l && R >= r) return tree[p];
    int middle = l + r >> 1;
    T lft = query(l, middle, L, R, p << 1);
    T rgh = query(middle + 1, r, L, R, p << 1 | 1);
    return join(lft, rgh);
  }
};
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long n;
  cin >> n;
  auto join = [](long long x, long long y) -> long long { return x + y; };
  segment_tree<long long, decltype(join)> t(1e6 + 1, 0, join);
  long long ans = 0;
  const long long MOD = 1e9 + 7;
  for (int i = 0; i < n; ++i) {
    long long x;
    cin >> x;
    long long cur =
        ((t.query(1, x) + 1) % MOD * x % MOD - t.get(x) + MOD) % MOD;
    t.point_update(x, (t.get(x) + cur) % MOD);
    ans += cur;
    if (ans >= MOD) ans -= MOD;
  }
  cout << ans << endl;
}

### Prompt

Your challenge is to write a CPP solution to the following problem:

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, typename Lambda>
struct segment_tree {
  vector<T> tree;
  T neutral;
  Lambda join;
  int size, real_size;
  segment_tree() {}
  template <typename L>
  segment_tree(int _size, const T &_neutral, const L &f) : join(f) {
    real_size = _size;
    size = nxt(_size);
    tree = vector<T>(2 * size + 1);
    neutral = _neutral;
  }
  int nxt(int x) {
    int i = 1;
    while (i < x) {
      i <<= 1;
    }
    return i;
  }
  void init(const vector<T> &v) {
    for (int i = 0; i < real_size; ++i) {
      tree[i + size] = v[i];
    }
    for (int i = size - 1; i >= 0; --i) {
      tree[i] = join(tree[i << 1], tree[i << 1 | 1]);
    }
  }
  void point_update(int id, const T &val) { point_update_iterative(id, val); }
  void point_update_iterative(int id, const T &val) {
    id += size - 1;
    tree[id] = val;
    id >>= 1;
    while (id > 0) {
      tree[id] = join(tree[id << 1], tree[id << 1 | 1]);
      id >>= 1;
    }
  }
  void point_update(int l, int r, int x, const T &val, int p) {
    if (l > x || r < x) {
      return;
    }
    if (l == r) {
      tree[p] = val;
      return;
    }
    int middle = l + r >> 1;
    point_update(l, middle, x, val, p << 1);
    point_update(middle + 1, r, x, val, p << 1 | 1);
    tree[p] = join(tree[p << 1], tree[p << 1 | 1]);
  }
  T get(int id) { return query(id, id); }
  T query(int L, int R) { return query_iterative(L, R); }
  T query_iterative(int L, int R) {
    L += size - 1;
    R += size - 1;
    T ans = neutral;
    while (L <= R) {
      if (L & 1) {
        ans = join(ans, tree[L++]);
      }
      if (!(R & 1)) {
        ans = join(ans, tree[R--]);
      }
      L >>= 1;
      R >>= 1;
    }
    return ans;
  }
  T query(int l, int r, int L, int R, int p) {
    if (L > r || l > R) return neutral;
    if (L <= l && R >= r) return tree[p];
    int middle = l + r >> 1;
    T lft = query(l, middle, L, R, p << 1);
    T rgh = query(middle + 1, r, L, R, p << 1 | 1);
    return join(lft, rgh);
  }
};
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long n;
  cin >> n;
  auto join = [](long long x, long long y) -> long long { return x + y; };
  segment_tree<long long, decltype(join)> t(1e6 + 1, 0, join);
  long long ans = 0;
  const long long MOD = 1e9 + 7;
  for (int i = 0; i < n; ++i) {
    long long x;
    cin >> x;
    long long cur =
        ((t.query(1, x) + 1) % MOD * x % MOD - t.get(x) + MOD) % MOD;
    t.point_update(x, (t.get(x) + cur) % MOD);
    ans += cur;
    if (ans >= MOD) ans -= MOD;
  }
  cout << ans << endl;
}

```