#P18163. Bus Analysis

Bus Analysis

Bus Analysis

Adam 将乘公交车进行一段很长的旅行。他可以买 20 分钟票,每张 2 PLN;也可以买 75 分钟票,每张 6 PLN。车票可以在任意整数分钟购买,购买时立即生效。例如,9:14:00 购买的 20 分钟票有效至 9:33:59。他可以在已有车票仍然有效时购买新票。

公交车停靠 NN 个车站,第 ii 站的停靠时间为第 tit_i 分钟。每站都可能有检票员等候。他们上车后立即检查所有乘客,然后在该站下车;这一过程仅需几秒。

旅行开始前,Adam 会获知哪些车站有检票员,然后安排购票,使每次检查时都有有效车票,并使总费用最小。

考虑每站是否有检票员的全部 2N2^N 种安排,分别求出 Adam 的最少费用,再将这些费用相加。输出总和对 109+710^9+7 取模的结果。

输入格式

第一行一个整数 NN,满足 1≤N≤10001\le N\le1000。

第二行 NN 个整数 t1,t2,…,tNt_1,t_2,\ldots,t_N,满足 1≤ti≤1091\le t_i\le10^9,且 ti<ti+1t_i<t_{i+1}。

输出格式

输出一个整数,表示费用总和对 109+710^9+7 取模的结果。

样例 1

输入:

3
1 8 20

输出:

14

没有检票员的安排费用为 0,其余七种安排都只需一张 20 分钟票,总费用为 0+7×2=140+7\times2=14。

样例 2

输入:

5
25 45 65 85 1000000000

输出:

156

例如,五站都有检票员时,最少费用为 8:在第 25 分钟买一张 75 分钟票,再在第 10910^9 分钟买一张 20 分钟票。若只有第 25、45 分钟两站有检票员,最少费用为 4,可以在这两站分别买短票,也可以在第 17、26 分钟购买。

车票有效时间按左闭右开区间计算:第 tt 分钟买的 LL 分钟票,覆盖整数分钟 t,t+1,…,t+L−1t,t+1,\ldots,t+L-1。