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).


-----Input-----

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.


-----Output-----

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).


-----Examples-----
Input
3 1
1

Output
1

Input
4 2
1 4

Output
2

Input
11 2
4 8

Output
6720

Difficulty: HARD
Tags: Number theory

Combinatorics

Starter code:

Solutions:
from math import factorial
(n, m) = map(int, input().split())
lights = list(map(int, input().split(' ')))
lights.sort()
lights = [0] + lights
lights.append(n + 1)
x = [lights[i + 1] - lights[i] - 1 for i in range(len(lights) - 1)]
s = sum(x)
prod = factorial(s)
for i in x:
	prod //= factorial(i)
prod %= 10 ** 9 + 7
if len(x) >= 3:
	for i in range(1, len(x) - 1):
		if x[i] > 0:
			prod *= pow(2, x[i] - 1, 10 ** 9 + 7)
print(prod % (10 ** 9 + 7))


from itertools import accumulate
mod = 10 ** 9 + 7
f = [1] + list(accumulate(range(1, 1001), lambda x, y: x * y % mod))

def C(n, k):
	return f[n] * pow(f[k], mod - 2, mod) * pow(f[n - k], mod - 2, mod) % mod
(n, m) = [int(x) for x in input().split()]
b = [-1] + [int(x) - 1 for x in input().split()] + [n]
b.sort()
ans = 1
cur = n - m
for i in range(1, len(b)):
	l = b[i] - b[i - 1] - 1
	ans = ans * C(cur, l) % mod
	if l > 0 and i > 1 and (i < len(b) - 1):
		ans = ans * pow(2, l - 1, mod) % mod
	cur -= l
print(ans)


def fac(n):
	if n == 0:
		return 1
	ans = 1
	for i in range(2, n + 1):
		ans *= i
	return ans
(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
ans = fac(n - m)
ans //= fac(a[0] - 1)
for i in range(1, m):
	ans //= fac(a[i] - a[i - 1] - 1)
	if a[i] - a[i - 1] - 1 != 0:
		ans *= 2 ** (a[i] - a[i - 1] - 2)
ans //= fac(n - a[m - 1])
print(ans % 1000000007)


mod = 10 ** 9 + 7

def factorial(n):
	x = 1
	for i in range(n):
		yield x
		x = x * (i + 1) % mod
f = list(factorial(1001))

def C(n, k):
	return f[n] * pow(f[k], mod - 2, mod) * pow(f[n - k], mod - 2, mod) % mod
(n, m) = [int(x) for x in input().split()]
b = [-1] + [int(x) - 1 for x in input().split()] + [n]
b.sort()
ans = 1
cur = n - m
for i in range(1, len(b)):
	l = b[i] - b[i - 1] - 1
	ans = ans * C(cur, l) % mod
	if l > 0 and i > 1 and (i < len(b) - 1):
		ans = ans * pow(2, l - 1, mod) % mod
	cur -= l
print(ans)


(M, N) = (1000000007, 2000)
f = [1] * N
for i in range(1, N):
	f[i] = f[i - 1] * i % M
(n, m) = map(int, input().split())
ar = sorted(map(int, input().split()))
br = []
for i in range(1, m):
	d = ar[i] - ar[i - 1] - 1
	if d > 0:
		br.append(d)
res = pow(2, sum(br) - len(br), M) * f[n - m] % M
br = [ar[0] - 1] + br + [n - ar[-1]]
for b in br:
	res = res * pow(f[b], M - 2, M) % M
print(res)


(x, y) = map(int, input().split())
fa = [0] * (x + 1)
fa[0] = 1
md = 10 ** 9 + 7
for n in range(1, x + 1):
	fa[n] = fa[n - 1] * n % md

def bnp(bs, pw):
	res = 1
	while pw:
		if pw & 1:
			res *= bs
			res %= md
		bs *= bs
		bs %= md
		pw //= 2
	return res
s = sorted(list(map(int, input().split())))
res = fa[x - y]
res *= bnp(fa[s[0] - 1], md - 2)
res %= md
for n in range(1, y):
	v = s[n] - s[n - 1] - 1
	if v:
		res *= bnp(fa[v], md - 2)
		res %= md
u = x - s[-1]
if u:
	res *= bnp(fa[u], md - 2)
	res %= md
for n in range(1, y):
	u = s[n] - s[n - 1] - 1
	if u:
		res *= bnp(2, u - 1)
		res %= md
print(res % md)


M = 1000000007
f = [1] * 2000
for i in range(1, 2000):
	f[i] = f[i - 1] * i % M
(n, m) = map(int, input().split())
a = sorted(map(int, input().split()))
b = []
for i in range(1, m):
	x = a[i] - a[i - 1] - 1
	if x > 0:
		b.append(x)
count = pow(2, sum(b) - len(b), M) * f[n - m] % M
b = [a[0] - 1] + b + [n - a[-1]]
for i in b:
	count = count * pow(f[i], M - 2, M) % M
print(count)


from math import factorial

def N3():
	modi = 10 ** 9 + 7
	(n, m) = [int(x) for x in input().split()]
	on = [int(x) for x in input().split()]
	on.sort()
	on = [0] + on + [n + 1]
	off = [on[i + 1] - on[i] - 1 for i in range(len(on) - 1)]
	s = sum(off)
	total = factorial(s)
	for i in off:
		total //= factorial(i)
	total %= modi
	if len(off) >= 3:
		for i in range(1, len(off) - 1):
			if off[i] > 0:
				total *= pow(2, off[i] - 1, modi)
	print(total % modi)
N3()


pri = pow(10, 9) + 7
p = pri
fac = [1 for i in range(10 ** 6 + 1)]
for i in range(2, len(fac)):
	fac[i] = fac[i - 1] * (i % pri) % pri

def modi(x):
	return pow(x, p - 2, p) % p

def ncr(n, r):
	x = fac[n] * (modi(fac[r]) % p * (modi(fac[n - r]) % p)) % p % p
	return x
(n, m) = map(int, input().split())
z = list(map(int, input().split()))
z.sort()
ans = []
for i in range(len(z)):
	if i == 0:
		ans.append(z[0] - 1)
	else:
		ans.append(z[i] - z[i - 1] - 1)
ans.append(n - z[-1])
temp = []
for i in range(len(ans)):
	if i == 0 or i == len(ans) - 1:
		temp.append(1)
	else:
		temp.append(pow(2, max(0, ans[i] - 1), pri))
seats = n - m
count = 1
for i in range(len(ans)):
	count = count * ncr(seats, ans[i])
	seats -= ans[i]
	count %= pri
for i in range(len(temp)):
	count = count * temp[i]
	count %= pri
print(count)


(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
MOD = int(1000000000.0 + 7)
f = [1]
for i in range(1, 1000):
	f.append(f[-1] * i % MOD)

def bigmod(a, e, m):
	ret = 1
	while e:
		if e % 2 == 1:
			ret *= a
			if ret > m:
				ret %= m
			e -= 1
		a *= a
		e /= 2
		if a > m:
			a %= m
	return ret

def invmod(a, p):
	return bigmod(a, p - 2, p)
ans = f[n - m]
for i in range(1, m):
	mid = a[i] - a[i - 1] - 1
	if mid > 0:
		ans *= invmod(f[mid], MOD)
		ans %= MOD
	if mid > 1:
		ans *= bigmod(2, mid - 1, MOD)
		ans %= MOD
if a[0] > 1:
	ans *= invmod(f[a[0] - 1], MOD)
	ans %= MOD
if a[m - 1] < n:
	ans *= invmod(f[n - a[m - 1]], MOD)
	ans %= MOD
print(ans)


(n, m) = map(int, input().split())
t = sorted(map(int, input().split()))
(f, d) = ([1] * (n + 1), 1000000007)
for i in range(2, n + 1):
	f[i] = f[i - 1] * i % d
(p, q) = (0, f[t[0] - 1] * f[n - t[-1]] % d)
for i in range(m - 1):
	l = t[i + 1] - t[i] - 1
	q = q * f[l] % d
	if l > 1:
		p += l - 1
print(pow(2, p, d) * f[n - m] * pow(q, d - 2, d) % d)


from sys import stdin, stdout

def main():
	(n, p) = (2000, 1000000007)
	factorial = [1] * (n + 1)
	for i in range(2, n + 1):
		factorial[i] = i * factorial[i - 1] % p
	while True:
		try:
			(n, m) = readline()
		except:
			break
		on = sorted(readline())
		off = []
		for i in range(1, m):
			c = on[i] - on[i - 1] - 1
			if c > 0:
				off.append(c)
		answer = pow(2, sum(off) - len(off), p) * factorial[n - m] % p
		off = [on[0] - 1] + off + [n - on[m - 1]]
		for x in off:
			answer = answer * pow(factorial[x], p - 2, p) % p
		stdout.write(str(answer) + '\n')

def readline():
	return map(int, stdin.readline().strip().split())
main()


def bpow(a, b):
	if b == 0 or a == 1:
		return 1
	if b % 2 != 0:
		return a * bpow(a, b - 1) % mod
	else:
		c = bpow(a, b / 2) % mod
		return c * c % mod
(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
a = [0] + a + [n + 1]
a = sorted(a)
fa = list()
fa.append(1)
mod = 1000000007
for i in range(1, 2010):
	fa.append(fa[i - 1] * i)
	fa[i] %= mod
ans1 = 1
ans2 = 1
s = 0
for i in range(0, m + 1):
	ans1 *= fa[a[i + 1] - a[i] - 1]
	s += a[i + 1] - a[i] - 1
	ans1 %= mod
	if i > 0 and i < m and (a[i + 1] - a[i] > 1):
		ans2 *= pow(2, a[i + 1] - a[i] - 2, mod)
		ans2 %= mod
print(fa[s] * pow(ans1, mod - 2, mod) * ans2 % mod)


def fac(n):
	if n == 0:
		return 1
	mul = 1
	for i in range(2, n + 1):
		mul *= i
	return mul
(n, m) = (int(t) for t in input().split(' '))
gen = (int(t) for t in input().split(' '))
v = []
for i in gen:
	v.append(i)
v.sort()
ans = fac(n - m)
ans //= fac(v[0] - 1)
for i in range(1, len(v)):
	ans //= fac(v[i] - v[i - 1] - 1)
	if v[i] - v[i - 1] - 1 != 0:
		ans *= 2 ** (v[i] - v[i - 1] - 2)
ans //= fac(n - v[len(v) - 1])
print('%d' % (ans % (int(1000000000.0) + 7)))


import sys
sys.setrecursionlimit(1000000)

def solve():
	MOD = 1000000007
	(n, m) = rv()
	(on,) = rl(1)
	on.sort()
	res = 1
	distances = list()
	for i in range(0, m + 1):
		first = on[i - 1] - 1 if i > 0 else 0
		second = on[i] - 1 if i < m else n - 1
		val = second - first - (1 if i > 0 and i < m else 0)
		distances.append(val)
	for i in range(1, n - m + 1):
		res *= i
	for val in distances:
		for i in range(1, val + 1):
			res //= i
	res %= MOD
	for i in range(1, len(distances) - 1):
		for j in range(distances[i] - 1):
			res *= 2
			res %= MOD
	print(res)

def rv():
	return list(map(int, input().split()))

def rl(n):
	return [list(map(int, input().split())) for _ in range(n)]
if sys.hexversion == 50594544:
	sys.stdin = open('test.txt')
solve()


def f(p):
	d = 1
	for i in range(2, p + 1):
		d *= i
	return d
(n, m) = map(int, input().split())
l = list(map(int, input().split()))
if n == m:
	print(1)
else:
	l.sort()
	for i in range(m):
		l[i] -= 1
	k = []
	sm = n - m
	if l[0] > 1:
		k.append([l[0], 1])
	for i in range(1, len(l)):
		k.append([l[i] - l[i - 1] - 1, 2 ** max(0, l[i] - l[i - 1] - 2)])
	if l[-1] < n - 1:
		k.append([n - 1 - l[-1], 1])
	ans = f(sm)
	for c in k:
		ans //= f(c[0])
	for c in k:
		ans *= c[1]
	print(ans % 1000000007)


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
l1 = []
l1.append(l[0] - 1)
for i in range(m - 1):
	l1.append(l[i + 1] - l[i] - 1)
f1 = [1] * 1001
f2 = [1] * 1001
mod = 10 ** 9 + 7
a = 1
b = 1
for i in range(1, 1001):
	a *= i
	a %= mod
	f1[i] = a
	b *= pow(i, mod - 2, mod)
	b %= mod
	f2[i] = b
ans = 1
n -= m
ans *= f1[n] * f2[l1[0]] * f2[n - l1[0]]
ans %= mod
n -= l1[0]
for i in range(1, len(l1)):
	if l1[i] > 0:
		ans *= f1[n] * f2[l1[i]] * f2[n - l1[i]] * pow(2, l1[i] - 1, mod)
		ans %= mod
		n -= l1[i]
print(ans)


from sys import stdin, stdout

def main():
	(n, p) = (1000, 1000000007)
	factorial = [1] * (n + 1)
	for i in range(2, n + 1):
		factorial[i] = i * factorial[i - 1] % p
	(n, m) = readline()
	on = sorted(readline())
	off = []
	for i in range(1, m):
		c = on[i] - on[i - 1] - 1
		if c > 0:
			off.append(c)
	answer = pow(2, sum(off) - len(off), p) * factorial[n - m] % p
	off = [on[0] - 1] + off + [n - on[m - 1]]
	for x in off:
		answer = answer * pow(factorial[x], p - 2, p) % p
	return answer

def readline():
	return map(int, stdin.readline().strip().split())
stdout.write(str(main()) + '\n')


MOD = 10 ** 9 + 7
fact = [1]
rfact = [1]
p2 = [1]
for i in range(1, 1010):
	fact.append(fact[-1] * i % MOD)
	rfact.append(rfact[-1] * pow(i, MOD - 2, MOD) % MOD)
	p2.append(p2[-1] * 2 % MOD)

def C(n, k):
	return fact[n] * rfact[k] * rfact[n - k] % MOD
(n, m) = list(map(int, input().split()))
pos = sorted(list(map(int, input().split()))) + [n + 1]
last = 1
ans = 1
n -= m
for x in pos:
	v = x - last
	ans = ans * C(n, v) % MOD
	if last > 1 and x < pos[-1] and (v > 0):
		ans = ans * p2[v - 1] % MOD
	last = x + 1
	n -= v
print(ans)


import itertools
import math

def countEndgames(grid):
	ls = []
	for (elt, gp) in itertools.groupby(grid):
		if elt == '.':
			ls.append(len(list(gp)))
	tot = 1
	for (i, g) in enumerate(ls):
		if i == 0 and grid[0] == '.' or (i == len(ls) - 1 and grid[-1] == '.'):
			continue
		tot *= 2 ** (g - 1)
	tot *= math.factorial(sum(ls))
	for g in ls:
		tot //= math.factorial(g)
	return tot % (10 ** 9 + 7)
(n, x) = list(map(int, input().split()))
ls = list(map(int, input().split()))
grid = ['.' for i in range(n)]
for x in ls:
	grid[x - 1] = '#'
print(countEndgames(grid))


MOD = 1000000007

def facts(m):
	fact = [0] * (m + 1)
	fact[0] = 1
	for i in range(1, m + 1):
		fact[i] = fact[i - 1] * i % MOD
	fact_inv = [0] * (m + 1)
	fact_inv[m] = pow(fact[m], MOD - 2, MOD)
	for i in reversed(range(m)):
		fact_inv[i] = fact_inv[i + 1] * (i + 1) % MOD
	return (fact, fact_inv)

def main():
	(n, m) = map(int, input().split())
	lights = sorted(map(int, input().split()))
	(fact, fact_inv) = facts(n)
	ans = fact[n - m]
	ans *= fact_inv[lights[0] - 1]
	ans *= fact_inv[n - lights[len(lights) - 1]]
	for i in range(1, len(lights)):
		ans *= fact_inv[lights[i] - lights[i - 1] - 1]
		if lights[i] - lights[i - 1] - 1 != 0:
			ans *= 2 ** (lights[i] - lights[i - 1] - 2)
	print(ans % MOD)
main()


import sys
import math
mod = 10 ** 9 + 7

def factorial(n):
	x = 1
	for i in range(n):
		yield x
		x = x * (i + 1) % mod
f = list(factorial(1001))

def C(n, k):
	return f[n] * pow(f[k], mod - 2, mod) * pow(f[n - k], mod - 2, mod) % mod

def main():
	(n, m) = [int(x) for x in sys.stdin.readline().strip().split()]
	b = [-1] + [int(x) - 1 for x in sys.stdin.readline().strip().split()] + [n]
	b.sort()
	ans = 1
	cur = n - m
	for i in range(1, len(b)):
		l = b[i] - b[i - 1] - 1
		ans = ans * C(cur, l) % mod
		if l > 0 and i > 1 and (i < len(b) - 1):
			ans = ans * pow(2, l - 1, mod) % mod
		cur -= l
	print(ans)
main()


def f(n):
	if n == 0:
		return 1
	ans = 1
	for i in range(2, n + 1):
		ans *= i
	return ans
(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
a = sorted(a)
ans = f(n - m) // f(a[0] - 1)
for i in range(1, m):
	ans //= f(a[i] - a[i - 1] - 1)
	if a[i] - a[i - 1] != 1:
		ans *= 2 ** (a[i] - a[i - 1] - 2)
ans //= f(n - a[m - 1])
print(ans % 1000000007)


import math

def myfunc(value):
	if value == 0:
		return 1
	total = 1
	for num in range(2, value + 1):
		total = total * num
	return total
(n, m) = map(int, input().split())
mylist = sorted(list(map(int, input().split())))
value = myfunc(n - m)
temp = myfunc(mylist[0] - 1)
total = value // temp
for i in range(1, m):
	values = mylist[i] - mylist[i - 1]
	temp = myfunc(values - 1)
	total = total // temp
	if mylist[i] - mylist[i - 1] != 1:
		values = mylist[i] - mylist[i - 1]
		temp = values - 2
		total = total * 2 ** temp
temp = myfunc(n - mylist[m - 1])
total = total // temp
print(total % 1000000007)


import math

def solve(n, list1):
	list1.sort()
	inf = int(1000000000.0 + 7)
	t1 = [list1[0] - 1, n - list1[-1]]
	t2 = []
	for i in range(1, len(list1)):
		t2.append(list1[i] - list1[i - 1] - 1)
	num1 = 1
	for i in range(n - len(list1)):
		num1 = num1 * (i + 1)
		num1 = num1 % inf
	num2 = 1
	num2 = math.factorial(t1[0]) % inf
	num2 = num2 % inf
	num2 = num2 * math.factorial(t1[1]) % inf
	num2 = num2 % inf
	for i in range(len(t2)):
		num2 = num2 * math.factorial(t2[i])
		num2 = num2 % inf
	num2 = pow(num2, inf - 2, inf)
	num3 = 1
	for i in range(len(t2)):
		if t2[i] - 1 < 0:
			continue
		num3 = num3 * pow(2, t2[i] - 1, inf) % inf
	num1 = num1 * num2
	num1 = num1 % inf
	num1 = num1 * num3
	num1 = num1 % inf
	return int(num1)
(n, m) = map(int, input().split())
list1 = list(map(int, input().split()))
print(solve(n, list1))


MOD = int(1000000000.0 + 7)
(n, m) = map(int, input().split())
arr = sorted(list(map(int, input().split())))
fact = [1]
for i in range(1, 1000):
	fact.append(fact[-1] * i % MOD)

def fast_power(b, e):
	res = 1
	while e > 0:
		if e % 2 == 1:
			res = res * b % MOD
		b = b * b % MOD
		e //= 2
	return res

def inv_mod(b):
	return fast_power(b, MOD - 2)
res = fact[n - m]
for i in range(1, m):
	mid = arr[i] - arr[i - 1] - 1
	if mid > 0:
		res = res * inv_mod(fact[mid]) % MOD
	if mid > 1:
		res = res * fast_power(2, mid - 1) % MOD
if arr[0] > 1:
	res = res * inv_mod(fact[arr[0] - 1]) % MOD
if arr[m - 1] < n:
	res = res * inv_mod(fact[n - arr[m - 1]]) % MOD
print(res)


mod = 1000000007
fact = [1] * 2000
for i in range(1, 2000):
	fact[i] = fact[i - 1] * i % mod
(n, m) = list(map(int, input().split()))
a = sorted(map(int, input().split()))
b = []
for i in range(1, m):
	x = a[i] - a[i - 1] - 1
	if x > 0:
		b.append(x)
count = pow(2, sum(b) - len(b), mod) * fact[n - m] % mod
b = [a[0] - 1] + b + [n - a[-1]]
for i in b:
	count = count * pow(fact[i], mod - 2, mod) % mod
print(count)


M = 1000000007

def fac(n):
	if n == 0 or n == 1:
		return 1
	fact = 1
	for i in range(2, n + 1):
		fact *= i
	return fact

def main():
	(n, m) = map(int, input().split())
	lights = sorted(map(int, input().split()))
	ans = fac(n - m)
	ans //= fac(lights[0] - 1)
	ans //= fac(n - lights[len(lights) - 1])
	for i in range(1, len(lights)):
		ans //= fac(lights[i] - lights[i - 1] - 1)
		if lights[i] - lights[i - 1] - 1 != 0:
			ans *= 2 ** (lights[i] - lights[i - 1] - 2)
	print(ans % M)
main()


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))
twodList = [[0 for _ in range(1005)] for _ in range(1005)]
powTee = [0 for _ in range(1005)]
powTee[0] = 1
twodList[0][0] = 1
for i in range(1, 1005):
	twodList[i][0] = 1
	for j in range(1, i + 1):
		twodList[i][j] = (twodList[i - 1][j] + twodList[i - 1][j - 1]) % 1000000007
	twodList[i][i] = 1
	powTee[i] = powTee[i - 1] * 2 % 1000000007
(n, m) = get_ints()
inputListy = get_list()
inputListy.sort()
numby = n - m
roubles = twodList[numby][inputListy[0] - 1]
numby -= inputListy[0] - 1
for i in range(1, m):
	x = inputListy[i] - inputListy[i - 1] - 1
	if x > 0:
		roubles = roubles * twodList[numby][x] % 1000000007 * powTee[x - 1]
	else:
		roubles = roubles * twodList[numby][x] % 1000000007
	numby -= x
roubles = roubles * twodList[numby][n - inputListy[m - 1]] % 1000000007
print(roubles)


mod = 1000000007
(n, m) = [int(i) for i in input().split()]
arr = [int(i) for i in input().split()]
fact = [0 for _ in range(n + 1)]
fact[0] = 1
for i in range(1, n + 1):
	fact[i] = fact[i - 1] * i % mod
arr.sort()
s = n - m
ans = fact[s]
if arr[0] > 1:
	ans = ans * pow(fact[arr[0] - 1], mod - 2, mod) % mod
for i in range(1, m):
	t = arr[i] - arr[i - 1] - 1
	if t > 0:
		ans = ans * pow(fact[t], mod - 2, mod) % mod
		ans = ans * pow(2, t - 1, mod) % mod
if arr[-1] != n:
	t = n - arr[-1]
	ans = ans * pow(fact[t], mod - 2, mod) % mod
print(ans)


from math import factorial
import re
in1 = [int(x) for x in re.split('\\s', input())]
in2 = [int(x) for x in re.split('\\s', input())]
in2.append(0)
in2.append(in1[0] + 1)
in2.sort()
lights = []
for x in range(len(in2) - 1):
	lights.append(in2[x + 1] - in2[x] - 1)
lightsTotal = sum(lights)
possTotal = factorial(lightsTotal)
for x in lights:
	possTotal //= factorial(x)
for x in range(1, len(lights) - 1):
	if lights[x] > 0:
		possTotal *= pow(2, lights[x] - 1)
possTotal %= 1000000007
print(possTotal)


mod = 10 ** 9 + 7
(n, m) = [int(x) for x in input().split()]
light = [False for x in range(n + 1)]
marr = [int(x) for x in input().split()]
for i in range(m):
	light[marr[i]] = True
counta = 0
countb = 0
for i in range(1, n + 1):
	if light[i] == False:
		counta += 1
	else:
		break
for i in reversed(range(1, n + 1)):
	if light[i] == False:
		countb += 1
	else:
		break
else:
	countb = 0
arr = []
start = False
count = 0
for i in range(1, n + 1):
	if start == False:
		if light[i] == True:
			start = True
	elif light[i] == False:
		count += 1
	elif count > 0:
		arr.append(count)
		count = 0
fact = [None for x in range(n + 1)]
fact[0] = 1
for i in range(1, n + 1):
	fact[i] = i * fact[i - 1]
ans = fact[n - m] // (fact[counta] * fact[countb])
ans = int(ans)
for item in arr:
	ans = ans // fact[item]
for item in arr:
	ans = ans * pow(2, item - 1, mod) % mod
print(ans % mod)