Cho dãy \(a\) có \(n\) phần tử, tính:

Với \(S\) là tập con không rỗng của mảng \(a\) cho trước.

Input

• Dòng đầu tiên gồm số nguyên dương \(n(1 \le n \le 10^5)\)
• Dòng thứ hai gồm \(n\) số nguyên \(a_i(1 \le a_i \le 10^6)\)

Output

• In ra kết quả của bài toán modulo \(10^9+7\).

Example

4
2 3 1 6

216