jmy是jb协会的团支书，众所周知，只有长得帅的人才能当上。
jmy在加入协会的第一天就被内部钦定为未来的团支书，所以jym的身边总少不了一群女装大佬围着她。
jmy从这些女装大佬中挑选出n个作为自己的干事，每个女装大佬都有一个美丽度a[i]。
现在jmy把n个女装大佬排成一排来计算他们的美丽度。
定义一个[l,r]之间女装大佬的美丽度为(r-l+1)*a[l]+(r-l)*a[l+1]+...+2*a[r-1]+1*a[r]
现在jmy想要知道对于所有的子区间，女装大佬们的美丽度和为多少。
 

单组样例

第一行输入一个整数n(1<n<=1000000)，

第二行输入n个整数  0<=ai<=1e9

输出所有区间的美丽度和  (由于输出结果太大，答案取模1e9+7)

推荐使用scanf&printf

Author  Mr.Lee