Introduction

差分

I'm sorry for dragging you all the way.
很抱歉一直以来拽着你到处乱跑
I just hope you didn't think I'm mad or so.
我只希望你别认为我疯掉了或者怎样
(For all l've done)
（对于我所做的这一切）
Just take a breath,make yourself.
来做个深呼吸，放松放松
Cause there's something you may not could imagine since you closed your eyes.
对于看不见的你来说有些事物会很难想象。
But it's nothing scary.
但这种感觉也没那么恐怖
Nothing to be afraid of.
没什么好害怕的
More it's like a taste of a breeze from the south.
你就把它当成南方微风轻柔地拂过你的脸颊
Might be crunchy in the morning and bright in the night.
对你来说早上不再会有太阳升起晚上也会变得怪异的明亮
You can get it,I believe you did?
但你总可以抓住声音吧，我相信你能？
(Now concentrate)
（现在来集中注意力）
Can you listen all the things around your knees?
你能听到所有声音正环绕在你的膝边吗？
Rabbit hop,water drop.
兔子跳跃的声音、水滴落下的声音
Whole reflection of yourself.
构成了一幅完美的图景。
Feeling dizzy of the spectacle.
被这等奇观包围着，你感到眼花缭乱，目不暇接。
Life is ever changing.
人生总是千变万化
Not so entertaining.
这不是很有意思吗
Nothing to care.
什么都不去关心
Nothing to lose.
也就不会失去任何
And no need to hesitate.
也就从不需要顾虑
Play like you never did before.
演奏吧就像你第一次这样做！
Grab the beauty of the world.(beauty of the world we never knew)
捕捉这世间散布的所有美好（我们未曾了解的世界之美）
All the joys and wonders you might be wanted to but you never knew that even exist.
你总是在试图寻找欢乐和奇迹但那双帮助你发现美的眼睛早已不复存在
Here's everything you're looking for.
不过这儿有你一直以来所寻找的所有东西
There's no reason to be shy,just spread the wings of possibilities on your back and fly
没什么好害羞的，现在你只需插上想象里的翅膀然后振翅高飞！
I don't know,go random!
（我也不知道，即兴发挥吧！）
Cmon,which one?
（来看看吧，这回的又是哪个呢？）
(进入差分）
Play like you never did before.
像你从来没有做过的那样去演奏吧！

Description

给你一个长度为 \(n\) 序列 \(p\) 。
记 \(U\) 为 \(1\) 至 \(n\) 的全集。
对于 \(1 \leq i，j \leq n\) , 记 \(q_{i, j} = \sum \limits_{S \sub U, |S| = j, i \in S} \prod \limits_{k \in S} p_k\)
求 \(\sum \limits_{i = 1}^{n} \sum \limits_{j = 1}^{n} {q_{i, j}}^2\) 。
由于答案可能很大，输出的数模 \(10^9 + 7\) 。

Format

Input

第一行一个整数 \(n\) ，表示序列的长度。
接下来一行， \(n\) 个数。第 \(i\) 个数表示 \(p_i\) 。

Output

一行一个整数 \(\sum \limits_{i = 1}^{n} \sum \limits_{j = 1}^{n} {q_{i, j}}^2\) 。

Sample 1

Input

2
1 2

Output

13

Sample 2

Input

3
2 4 3

Output

2677

Sample 3

Input

6
12 23 76 91 12 34

Output

661057474

Limitation

对于\(10\%\)的数据，\(1 \leq n \leq 10\)
对于\(30\%\)的数据，\(1 \leq n \leq 100\)
对于\(100\%\)的数据，\(1 \leq n \leq 2000\)，\(1 \leq p_i \leq 10^9\)