QUESTION
You are given an array of N distinct numbers. Now, we call the Digit Value of a number to be the sum of its digits.\n\nNow, a subset is a set of not-necessarily-contiguous array elements. We call the value of a set to be the the maximum over the Digit Value of all elements it contains.\n\nNow, you need to find the summation of the values of all 2^N -1 non-empty subsets of this array. As the answer can be rather large, print it Modulo 10^9+7. Can you do it ?\n\nInput Format :\n\nThe first line contains a single integer N. The next line contains N space separated integers, where the ith integer denotes A[i].\n\nOutput Format :\n\nPrint the summation of the value of each non-empty subset of the given array Modulo 10^9+7.\n\nConstraints :\n\n1<=N<=10^5\n\n0<=A[i]<=10^18.
ANSWER
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod =1000000007;
ll power(ll a,ll b){
ll res=1;
while(b>0){
if(b&1) res =(res*a)%mod;
a=(a*a)%mod;
b/=2;
}
return res%mod;
}
ll invmod(ll a){
return power(a,mod-2);
}
ll digitsum(long long num){
long long rem, div;
ll sumdigit=0;
while(num > 0){
rem = num%10;
sumdigit = (sumdigit + rem)%mod;
num /= 10;
}
return sumdigit%mod;
}
int main(){
ll n;
cin>>n;
long long number,prod;
ll arr[n];
for(int i=0;i<n;i++){
cin>>number;
arr[i]=digitsum(number);
}
sort(arr,arr+n);
reverse(arr,arr+n);
ll summ = 0,left;
for(int i=0;i<n;i++){
left = power(2,n-i-1) ;
summ = (summ + (arr[i]*left)%mod)%mod;
}
cout<<summ%mod<<endl;
return 0;
}