老虎和蒜头是好朋友。

这一天在森林中是历史性的一天：在多方面的不懈努力下，森林终于能够接收到外界传输的网络信号了。在这一天，森林中的所有居民都在体验网络信号给生活带来的新的变化。

老虎是一名音乐爱好者，因此他决定收听音乐电台。老虎收听的电台的曲库中一共有 $ n $ 首歌曲，第 $ i $ 首歌的时长为 $ t_i $ 。电台会按照歌曲的顺序逐一播放所有歌曲，在播放过程中歌曲的切换所需的时间可以忽略不计，当第 $ n $ 首歌播放完后，电台会重新从第 $ 1 $ 首歌开始播放。在 $ 0 $ 时刻时，电台刚好开始播放第 $ 1 ​$ 首歌曲。

老虎会在某个时刻开始收听音乐电台。为了不出现错过歌曲的精彩部分的情况，老虎决定在收听电台时，从头开始播放电台当前播放的歌（显然这只是老虎的自发行为，不会影响到电台正在播放的歌曲）。一曲终了，老虎会将电台当前时刻正在播放的歌，再从头开始播放。老虎收听音乐电台的过程，实际上就是不断这样播放的过程。

显然，老虎在收听电台的过程中可能会跳过若干首歌曲：在老虎还在听上一首歌的时候，新的一首歌已经播放完成。在听音乐的过程中，一首歌可能被跳过多次，对每一次我们都将其计入一次跳过。现在，老虎想要知道，在他从某个未知时刻开始收听电台，并收听歌曲 $ 10^{100} ​$ 首的情况下，期望会跳过多少首歌曲。

老虎开始收听电台的时间在 $ R^{+} ​$ 上均匀分布，因此老虎从某个整时刻开始收听电台的概率是 $ 0 ​$ ，因此我们不会讨论在一首歌恰好被播放完的时刻，老虎会认为电台正在播放哪首歌。

你只需要输出答案对 $ 10^9 + 7 ​$ 取模的结果。

输入格式

输入的第一行包括一个正整数 $ n ​$ ，表示歌曲的数目。

接下来一行 $ n ​$ 个数表示 $ t_i ​$ 。

输出格式

对每组询问，输出一行一个数表示答案。

样例一

input

4
3 1 3 2

output

666666672

样例二

input

2
1 10

output

818181828

限制与约定

Subtask 1(14 分): $ 1 \le n, t_i \le 50 $

Subtask 2(19 分): $ 1 \le n \le 200, 1 \le t \le 10^4 $

Subtask 3(17 分): $ 1 \le n \le 300, 1\le t_i \le 10^9 $

Subtask 4(16 分): $ 1 \le n \le 3000, 1\le t_i \le 10^9 $

Subtask 5(23 分): $ 1 \le n \le 2 \times 10^4, 1\le t_i \le 10^9 ​$

Subtask 6(11 分): $ 1 \le n \le 10^5, 1\le t_i \le 10^9 $

时间限制: 3s

空间限制: 512MB