시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 6 6 4 100.000%

## 문제

The 2017 International Congress of Monsters gathers n monsters coming from all over the world. Their chairman has to solve the following problem: if the ith monster (1 ≤ i ≤ n) has ki fingers, indexed from 0 to ki - 1, so he can lift j of those fingers (0 ≤ j ≤ ki), obtaining a certain number, in the following way: if a certain finger is lifted, 2finger index is added to the current number. As a result, the ith monster can count on his fingers nri distinct numbers. Therefore, the demanded result is nr1 + nr2 + … + nrn, modulo 109+7.

Compute the required sum, modulo 109+7.

## 입력

The first line of the input contains the number n.

The second line contains n positive integers, k1, k2, …, kn, representing the numbers of fingers of each monster.

## 출력

The output must contain a single positive integer, the requested sum, modulo 109+7.

## 제한

• n ≤ 200,000
• 0 ≤ ki ≤ 1,000,000,000
• The fingers are indexed from 0.

## 예제 입력 1

2
3 7


## 예제 출력 1

136


## 힌트

The first monster can obtain 8 numbers:

• 0 - no finger was lifted;
• 1 - the index of lifted finger is 0;
• 2 - the index of lifted finger is 1;
• 3 - the indexes of lifted fingers are 0 and 1;
• 4 - the index of lifted finger is 2;
• 5 - the indexes of lifted fingers are 0 and 2;
• 6 - the indexes of lifted fingers are 1 and 2;
• 7 - the indexes of lifted fingers are 0, 1 and 2.

The second monster can obtain 128 numbers.

## 채점 및 기타 정보

• 예제는 채점하지 않는다.