SOLVE
LATER
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..
Now, 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.
Now, 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 ?
Input Format :
The first line contains a single integer $$N$$. The next line contains $$N$$ space separated integers, where the $$i^{th}$$ integer denotes $$A[i]$$.
Output Format :
Print the summation of the value of each non-empty subset of the given array Modulo $$10^9+7$$.
Constraints :
$$ 1 \le N \le 10^{5} $$
$$ 0 \le A[i] \le 10^{18} $$
The subsets of this array and their values are :
(10) : 1
(20) : 2
(30) : 3
(10,20) : 2
(10, 30) : 3
(20,30) : 3
(10,20,30 ) : 3
Thus, the final answer is $$ (1+2+3+2+3+3+3 ) $$ = $$17$$