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} \)
No editorial available for this problem.