← 返回题目列表

AtCoder · nyc2015_13

M. 绘图

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

问题陈述

狸猫君决定要画一幅画。 首先,狸猫君准备了一张细长的白纸,并将其划分为1 \times N 个方格。 接下来,狸猫君进行K 次操作。 i 在第 a_i 选择这个方格,并将其全部涂黑。 在此操作中,被选中的方格中原本为白色的会变为黑色,原本为黑色的方格保持不变。

求出小骏君能够画出多少种图画,\rm{mod}\ 1,000,000,007 。 当某个方格的最终颜色不同时,认为两幅图画不同。 即使旋转后相同,也认为是不同的图画。


约束

  • 1 \leq N \leq 10^9
  • 1 \leq K \leq 4
  • 1 \leq a_i \leq N

输入格式

输入是按以下格式从标准输入给出的。
N K
a_1
:
a_K

输出格式

将答案输出到一行中。

示例输入 1

10 2
1
1

示例输出 1

55
可以画出 10 个方格中有 1 个或 2 个为黑色的所有图画。

示例输入 2

1000000000 4
2015
2015
123456789
27

示例输出 2

782767239