← 返回题目列表

Codeforces · 294/C

C. 沙斯和灯

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

有 n 个灯排成一排。这些灯从左到右编号为 1 到 n。最初,一些灯打开。沙斯想要打开所有的灯。在每一步中,如果至少有一个相邻的灯已经打开,他可以打开一盏灯(该灯应该在那一刻关闭)。

他知道灯的初始状态,并且想知道有多少种不同的方法可以打开所有灯。请以 1000000007 (109 + 7) 为模找出所需的路数。

输入

输入的第一行包含两个整数 n 和 m,其中 n 是序列中的灯数量,m 是最初打开的灯数量,(1 ≤ n ≤ 1000, 1 ≤ m ≤ n)。第二行包含 m 个不同的整数,每个整数在 1 到 n 之间(含),表示最初打开的灯的索引。

输出

在输出的唯一一行中打印打开所有灯的不同可能方式的数量,模 1000000007 (109 + 7)。

示例

输入 #1

3 1
1

输出 #1

1

输入 #2

4 2
1 4

输出 #2

2

输入 #3

11 2
4 8

输出 #3

6720