암호 해독

셜록 홈즈는 어떤 퍼즐이든 풀어내지만, 모든 비밀을 한 번에 밝혀내지는 못한다. 반년 전 연락책이 암호로 쓰인 편지를 그에게 가져왔다. 편지에는 해독에 필요한 키가 없었다. 봉투의 반송 주소도 이상할 만큼 길었다. 거리 이름과 번지 대신 $n$개의 수가 적혀 있었던 것이다. 홈즈는 여러 방법을 써 봤지만 편지를 읽지 못했다.

오늘 아침 홈즈가 집 문 앞에서 레스트레이드 형사를 만났다. 형사는 새로운 소식을 가져왔다. 스코틀랜드 야드가 미스터리한 교수 M.의 조직원 한 명을 붙잡았고, 그 조직원은 형량을 줄이는 대가로 범죄망이 쓰는 암호의 비밀을 털어놓기로 했다. 모든 천재적인 것이 그렇듯 이 암호도 매우 단순했다. 키는 모든 부분 구간에서 그 구간의 수만으로 만들 수 있는 서로 다른 부분수열의 개수를 구해 모두 더한 값이다.

부분 구간이란 $1 \le l \le r \le n$을 만족하는 두 수 $l, r$로 정해지는 구간 $[l, r]$을 말한다. 구간 $[l, r]$의 부분수열은 $l \le i_1 < i_2 < \ldots < i_k \le r$을 만족하는 수열 $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$이며, 빈 수열도 포함한다. 두 부분수열 $a_i$와 $a_j$는 길이가 다르거나, 어떤 $k$에 대해 $a_{i_k} \ne a_{j_k}$이면 서로 다른 것으로 본다.

값이 매우 클 수 있으므로 $1\,000\,000\,007$로 나눈 나머지를 구하시오. 홈즈는 수학에 약하므로 키를 찾는 데 도움이 필요하다.

첫 줄에 수열의 길이 $n$ ($1 \le n \le 100\,000$)이 주어진다.

둘째 줄에는 수열의 원소 $a_i$ ($1 \le a_i \le 100\,000$) $n$개가 주어진다.

키를 $1\,000\,000\,007$로 나눈 나머지를 한 줄에 출력한다.

첫 번째 예제 설명:

수 집합 $\{1, 1, 2\}$에는 부분 구간이 여섯 개 있다.

• 부분 구간 $[1, 1]$은 $\{1\}$이며, 부분수열은 2개($\{\}$, $\{1\}$)이다.
• 부분 구간 $[2, 2]$은 $\{1\}$이며, 부분수열은 2개($\{\}$, $\{1\}$)이다.
• 부분 구간 $[3, 3]$은 $\{2\}$이며, 부분수열은 2개($\{\}$, $\{2\}$)이다.
• 부분 구간 $[1, 2]$은 $\{1, 1\}$이며, 부분수열은 3개($\{\}$, $\{1\}$, $\{1, 1\}$)이다.
• 부분 구간 $[2, 3]$은 $\{1, 2\}$이며, 부분수열은 4개($\{\}$, $\{1\}$, $\{2\}$, $\{1, 2\}$)이다.
• 부분 구간 $[1, 3]$은 $\{1, 1, 2\}$이며, 부분수열은 6개($\{\}$, $\{1\}$, $\{2\}$, $\{1, 1\}$, $\{1, 2\}$, $\{1, 1, 2\}$)이다.

따라서 답은 $2+2+2+3+4+6=19$이다.