Problem 73: Sum Over Subsets DP

Problem Statement: Given an array of n integers, compute for every subset the sum of its elements, and then compute the total of all these subset sums modulo 10^9+7.

Input

The first line contains an integer n. The second line contains n space-separated integers.

Output

Print the total sum of all subset sums modulo 10^9+7.

Examples


Input:
3
1 2 3

Output:
24

Solution Explanation

Each element appears in exactly 2^(n-1) subsets. Therefore, the answer is (sum of elements) * 2^(n-1) modulo 10^9+7.

Solution in C++


#include 
#include 
using namespace std;

const long long MOD = 1000000007;

long long modExp(long long base, int exp){
    long long res = 1;
    while(exp){
        if(exp & 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return res;
}

int main(){
    int n; 
    cin >> n;
    long long sum = 0;
    for(int i = 0; i < n; i++){
        int x; 
        cin >> x;
        sum = (sum + x) % MOD;
    }
    long long ans = (sum * modExp(2, n - 1)) % MOD;
    cout << ans << "\n";
    return 0;
}