#H1049. 数学还是简单一点好

数学还是简单一点好

题目描述

在一个遥远的地方,住着一位老者,自称知道从古至今所有的事物和答案。

每天有无数的人去向老者祈求答案,而善良的老者总是逐一解答。

smilke 是一个 ZJ 菜鸡,碰到了困难。


在一天早晨,smilke 上前去询问老者一个问题:

给定一个序列:a1,a2,,an1,ana_1,a_2,\dots,a_{n-1},a_n

每次操作对这个序列的相邻两个数合并。

例如一次操作后的序列为:a1×a2,a2×a3,,an1×ana_1 \times a_2,a_2 \times a_3,\dots,a_{n-1} \times a_n,之后的操作同理。

显然在 n1n-1 次操作后数列变为一个数,现在 smilke 想要知道这最后的一个数对 109+710^9+7 取膜后的结果。

然而老者并不会做这道题,所以他现在需要你的帮助。

输入格式

第一行一个整数 nn,表示序列的长度。
接下来一行 nn 个整数,表示序列 aa

输出格式

一行一个整数,表示 n1n-1 次操作后序列中的那个数对 1e9+71e9+7 取膜后的结果。

3
2 1 3
6

样例说明 1

初始序列为 [2,1,3][2,1,3]

  • 11 步操作后: [2,3][2,3]
  • 22 步操作后: [6][6]

所以答案为 66

5
2 3 2 1 5
51840

样例解释 2

初始序列为 [2,3,2,1,5][2,3,2,1,5]

  • 11 步操作后: [6,6,2,5][6,6,2,5]
  • 22 步操作后: [36,12,10][36,12,10]
  • 33 步操作后: [432,120][432,120]
  • 44 步操作后: [51840][51840]

所以答案为 5184051840

数据规模与约定

Subtask 1(30 pts): 1n500\texttt{Subtask 1(30 pts): }1 \le n \le 500
Subtask 2(30 pts): 1n3×103\texttt{Subtask 2(30 pts): }1 \le n \le 3 \times 10^3
Subtask 3(40 pts): 1n2×105\texttt{Subtask 3(40 pts): }1 \le n \le 2 \times 10^5

对于 100%100\% 的数据保证 0ai1090 \le a_i \le 10^9