#CW24. 覆盖(cover)

覆盖(cover)

题目描述

现在有一根长度为 nn 的线段。这根线段上有 mm 个标记。第 ii 个标记位于线段左端向右第 xix_i 的位置。

你要沿着这根线段,放置若干个木棒。放置木棒需要满足以下条件:

  • 所有木棒长度必须为整数。
  • 所有木棒不能互相重叠。
  • 所有木棒需要将线段完全覆盖。也就是说,木棒不能超出线段的边界,即 [0,n][0,n],也不能有线段的部分没有被木棒覆盖。
  • 线段上有标记的地方,不能正好在两个木棒的边界处。

例如,对于一个长度为 99 的线段,如果在 1,3,71,3,7 处有标记,那么,你可以依次放置长度为 5,1,35,1,3 的木棒。因为它们完全覆盖了线段,并且在 5,65,6 处存在边界,这两个位置没有被标记。

对于一种木棒的摆放方案,它的价值定义为所有木棒长度的平方的乘积。

你需要求,满足上述条件的所有木棒摆放方案的价值之和是多少。你只需要输出这个价值和对 109+710^9+7 取模后的结果。

输入格式

第一行包含两个整数 n,mn,m。

接下来一行,包含 mm 个整数表示 xix_i。

输出格式

输出一个整数,表示价值和对 109+710^9+7 取模后的结果。

样例 1 输入

3 1
2

样例 1 输出

13

样例 1 解释

可能的方案有以下两种:

  • 左边放一个长为 11 的木棒,右边放一个长为 22 的木棒,价值为 44;
  • 放一个长为 33 的木棒,价值为 99。

样例 2 输入

10 9
1 2 3 4 5 6 7 8 9

样例 2 输出

100

数据范围

对于所有测试数据,保证:1≤n≤1091 \le n \le 10^9,0≤m≤1050 \le m \le 10^5,1≤x1<x2<⋯<xm<n1 \le x_1<x_2<\cdots<x_m<n。

测试点 n≤n \le m≤m \le
1∼41 \sim 4 1010 55
5∼85 \sim 8 10001000 800800
9∼139 \sim 13 10610^6 10510^5
14∼1514 \sim 15 10910^9 00
16∼2016 \sim 20 10510^5