Shaass and Lights

题意翻译

有 $n$ 盏灯，(0<=n<=1000),有 $m$盏已经点亮，每次只能点亮与已经点亮的灯相邻的灯，求点亮所有灯的总方案数，答案对1e9+7取模 第一行：两个整数 $n,m$ 表示灯的总数和已点亮的灯的数目 第二行m个数，表示已点亮的灯的编号 感谢@ztz11 提供的翻译

题目描述

There are $ n $ lights aligned in a row. These lights are numbered $ 1 $ to $ n $ from left to right. Initially some of the lights are switched on. Shaass wants to switch all the lights on. At each step he can switch a light on (this light should be switched off at that moment) if there's at least one adjacent light which is already switched on. He knows the initial state of lights and he's wondering how many different ways there exist to switch all the lights on. Please find the required number of ways modulo $ 1000000007 (10^{9}+7) $ .

输入输出格式

输入格式

The first line of the input contains two integers $ n $ and $ m $ where $ n $ is the number of lights in the sequence and $ m $ is the number of lights which are initially switched on, $ (1<=n<=1000,1<=m<=n) $ . The second line contains $ m $ distinct integers, each between $ 1 $ to $ n $ inclusive, denoting the indices of lights which are initially switched on.

输出格式

In the only line of the output print the number of different possible ways to switch on all the lights modulo $ 1000000007 (10^{9}+7) $ .

输入输出样例

输入样例 #1

3 1
1

输出样例 #1

1

输入样例 #2

4 2
1 4

输出样例 #2

2

输入样例 #3

11 2
4 8

输出样例 #3

6720