← 返回题目列表

AtCoder · agc013_e

E. 放置方块

中文机器翻译题面 查看原题

分数: 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