题目描述

在古老的魔法图书馆中，隐藏着无数珍贵的宝藏。这些宝藏被分散在图书馆的各个角落，而找到它们的线索则隐藏在一串神秘的数字序列中。作为图书馆的新晋探险家，你需要解读这个序列，找到所有宝藏的线索，并计算出它们的总价值。图书馆的管理员给了你一个由 n 个非负整数组成的序列 a，这个序列代表了图书馆中各个宝藏的线索。你需要定义一个寻宝规则：对于序列 a 的任意子区间 [l, r]，你只能选择其中不相邻的线索（因为相邻的线索之间会互相干扰，无法同时获取）。你的目标是找到所有可能的子区间 [l, r]，并计算出在每个子区间中根据寻宝规则能够获取的最大线索价值之和。

具体来说，你需要按照以下步骤操作：

（1）遍历序列 a 的所有可能子区间 [l, r]。

（2）对于每个子区间 [l, r]，根据寻宝规则（只能选择不相邻的线索），计算出能够获取的最大线索价值。

（3）将所有子区间的最大线索价值相加，得到总价值。

（4）由于总价值可能非常大，你需要对结果取模 (10^9 + 7)，以确保结果在一个合理的范围内。

输入格式

第一行一个整数n，表示序列a的长度

第二行n个非负整数a[1],a[2],...a[n],表示序列 a 中的每个元素，即每个宝藏线索的价值。

输出格式

一行一个整数，表示答案

10%的数据保证：n<=500

20%的数据保证：n<=5000

20%的数据保证：a[i]=0或a[i]=1

20%的数据保证：a[i]=1或a[i]=x，x为大于1的整数

30%的数据保证：无限制

100%的数据保证：1<=n<=100000,0<=a[i]<=1e9

输入/输出例子1

3
1 2 4

18

样例解释

根据题目要求，我们可以计算出以下结果：

对于子区间 [1, 1]，最大线索价值为 1。

对于子区间 [1, 2]，最大线索价值为 2。

对于子区间 [1, 3]，最大线索价值为 5（选择线索 1 和 4）。

对于子区间 [2, 2]，最大线索价值为 2。

对于子区间 [2, 3]，最大线索价值为 4（选择线索 2 或 4，但不能同时选择）。

对于子区间 [3, 3]，最大线索价值为 4。

将所有子区间的最大线索价值相加，得到 1 + 2 + 5 + 2 + 4 + 4 = 18。然后对 18 取模 (1e9 + 7)，所以结果仍为 18。