问题陈述
狸猫君决定要画一幅画。 首先,狸猫君准备了一张细长的白纸,并将其划分为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
示例输入 2
1000000000 4 2015 2015 123456789 27
示例输出 2
782767239