James is very naive in Mathematics, He always makes new things out of a given list of integers. Today he is given a list , so he creates a value out of it.

from a given list can be calculated as follows.

value_of_S(list L)
{
    while ((number of elements in L) > 1)
    {
        a = L[0]
        b = L[1]
        delete L[1]
        L[0] = a+b+ab
    }
    return L[0] % 1000000007
}

James has an ample amount of time, so he calculates the values of for all the permutations of the given list and finds their average value. Then he asks you to report that value.

Input Format
The first line contains an integer , the number of integers in the list.
The second line contains integral values, , separated by single spaces.

Output Format
Print the floor of the average value.

Constraints

Sample Input

2
2 3

Sample Output

11

Explanation
The value corresponding to the two permutations of the given list is .