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