21854번 - Monsters 다국어

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 i^th monster (1 ≤ i ≤ n) has k_i fingers, indexed from 0 to k_i - 1, so he can lift j of those fingers (0 ≤ j ≤ k_i), obtaining a certain number, in the following way: if a certain finger is lifted, 2^{finger index} is added to the current number. As a result, the i^th monster can count on his fingers nr_i distinct numbers. Therefore, the demanded result is nr₁ + nr₂ + … + nr_n, modulo 10⁹+7.

Compute the required sum, modulo 10⁹+7.

The first line of the input contains the number n.

The second line contains n positive integers, k₁, k₂, …, k_n, representing the numbers of fingers of each monster.

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

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

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.