Cho ~x_1, x_2, …., x_n~. Định nghĩa hàm ~f~ như sau:

• ~f(y_1) = y_1~.
• ~f(y_1, y_2) = y_1^{y_2}~.
• ~f(y_1, y_2, y_3) = y_1{^{y_2^{y_3}}}~.
• ~f(y_1, y_2, …, y_k) = y_1^{f(y_2, …, y_k)}~.

Tính tổng ~f(x_i,x_{i+1},..., x_j)~ qua tất cả các bộ ~1\leq i\leq j\leq n~ trong modulo ~10^9+7~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~
• Dòng thứ 2 chứa ~n~ số nguyên ~x[i]~.

Output

• Tổng ~f(x_i,x_{i+1},..., x_j)~ trong modulo ~10^9+7~.

Sample Input:

5
1 5 9 2 2

Sample Output

409983298

Subtask

Giới hạn: ~1\leq N\leq 10^4, 1\leq x_i\leq 10^9~.

• ~50\%~ số điểm có ~1 \leq n \leq 10^2~.
• ~50\%~ số điểm còn lại có ~1 \leq n \leq 10^4~.