CF294C.Shaass and Lights

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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
```

首页