分数: 1600 点
问题陈述
Joisino 有一个长度条 N,其中有 上面有 M 标记。 从条形左端到 i- 第一个标记是 X_i.
她将在此栏上放置几个方块。 这里,必须满足以下条件:
- 只能放置边长为整数的正方形。
- 每个方块的放置必须使其底边接触条形。
- 该条必须完全被方块覆盖。 也就是说,没有任何方块可以伸出条形,并且条形的任何部分都不能被覆盖。
- 两个正方形的边界线不能位于标记的正上方。
满足/违反条件的安排示例 正方形排列的
的 美女 长度为 $$$m$$$(其中 $$$m \ge 2$$$)的数组 $$$b$$$ 的 被定义为 产品 放置的所有方块的面积。 Joisino 感兴趣的是满足条件的所有可能排列的美感总和。 编写一个程序来找到它。 由于它可能非常大,因此打印模数之和 10^9+7.
约束
- 所有输入值均为整数。
- 1 \leq N \leq 10^9
- 0 \leq M \leq 10^5
- 1 \leq X_1 < X_2 < ... < X_{M-1} < X_M \leq N-1
输入
输入由标准输入按以下格式给出:
N M
X_1 X_2 ... X_{M-1} X_M
输出
打印满足条件的所有可能排列的美度总和,模 10^9+7.
示例输入 1
3 1 2
示例输出 1
13
有两种可能的安排:
- 放置一个边长为正方形的正方形 1 向左放置另一个边长的正方形 2 向右
- 放置一个边长为正方形的正方形 3
这些安排的美妙之处在于 (1 \times 1 \times 2 \times 2) + (3 \times 3) = 13.
示例输入 2
5 2 2 3
示例输出 2
66
示例输入 3
10 9 1 2 3 4 5 6 7 8 9
示例输出 3
100
示例输入 4
1000000000 0
示例输出 4
693316425