有 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