题目描述

Joisino 有一根长度为 $N$ 的条形物体，上面有 $M$ 个标记。从条形物体的左端到第 $i$ 个标记的距离为 $X_i$。

她将在这个条形物体上放置一些正方形。在此，必须满足以下条件：

• 只能放置边长为整数的正方形。
• 每个正方形必须放置在底部与条形物体接触的位置。
• 条形物体必须完全被正方形覆盖。也就是说，没有正方形可以超出条形物体的边界，且不能留下任何未被覆盖的部分。
• 两个正方形的边界线不能直接位于一个标记的上方。

美丽的排列方式被定义为所有放置的正方形面积的乘积。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