몬스터

2017년 국제 몬스터 회의에 전 세계에서 온 n마리의 몬스터가 모인다. 의장은 다음 문제를 해결해야 한다. i번째 몬스터(1 ≤ i ≤ n)가 0부터 ki - 1까지 번호가 붙은 ki개의 손가락을 가졌고, 그중 j개의 손가락을 들어 올리면(0 ≤ j ≤ ki) 다음과 같은 방식으로 어떤 수를 얻는다. 특정 손가락을 들면 그 손가락 번호를 지수로 한 2의 거듭제곱이 현재 수에 더해진다. 그 결과 i번째 몬스터는 손가락으로 nri개의 서로 다른 수를 셀 수 있다. 따라서 구해야 하는 값은 nr1 + nr2 + … + nrn을 109+7로 나눈 나머지이다.

이 합을 109+7로 나눈 나머지를 구하시오.

첫째 줄에 n이 주어진다.

둘째 줄에 n개의 양의 정수 k1, k2, …, kn이 주어지며, 각 몬스터의 손가락 수를 나타낸다.

요청된 합을 109+7로 나눈 나머지인 양의 정수 하나를 출력한다.

• n ≤ 200,000
• 0 ≤ ki ≤ 1,000,000,000
• 손가락 번호는 0부터 시작한다.

첫 번째 몬스터는 8개의 수를 얻을 수 있다.

• 0: 아무 손가락도 들지 않음
• 1: 든 손가락의 번호가 0
• 2: 든 손가락의 번호가 1
• 3: 든 손가락의 번호가 0과 1
• 4: 든 손가락의 번호가 2
• 5: 든 손가락의 번호가 0과 2
• 6: 든 손가락의 번호가 1과 2
• 7: 든 손가락의 번호가 0, 1, 2

두 번째 몬스터는 128개의 수를 얻을 수 있다.