题目描述
在一个遥远的地方,住着一位老者,自称知道从古至今所有的事物和答案。
每天有无数的人去向老者祈求答案,而善良的老者总是逐一解答。
smilke 是一个 ZJ 菜鸡,碰到了困难。
在一天早晨,smilke 上前去询问老者一个问题:
给定一个序列:a1,a2,…,an−1,an。
每次操作对这个序列的相邻两个数合并。
例如一次操作后的序列为:a1×a2,a2×a3,…,an−1×an,之后的操作同理。
显然在 n−1 次操作后数列变为一个数,现在 smilke 想要知道这最后的一个数对 109+7 取膜后的结果。
然而老者并不会做这道题,所以他现在需要你的帮助。
输入格式
第一行一个整数 n,表示序列的长度。
接下来一行 n 个整数,表示序列 a。
输出格式
一行一个整数,表示 n−1 次操作后序列中的那个数对 1e9+7 取膜后的结果。
3
2 1 3
6
样例说明 1
初始序列为 [2,1,3]。
- 1 步操作后: [2,3]。
- 2 步操作后: [6]。
所以答案为 6。
5
2 3 2 1 5
51840
样例解释 2
初始序列为 [2,3,2,1,5]。
- 1 步操作后: [6,6,2,5]。
- 2 步操作后: [36,12,10]。
- 3 步操作后: [432,120]。
- 4 步操作后: [51840]。
所以答案为 51840。
数据规模与约定
Subtask 1(30 pts): 1≤n≤500。
Subtask 2(30 pts): 1≤n≤3×103。
Subtask 3(40 pts): 1≤n≤2×105。
对于 100% 的数据保证 0≤ai≤109。