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;
}