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} \)