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: interview

Starter code:

Solutions:
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)

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)


from math import factorial
n, m = list(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))


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




#!/usr/bin/env python3


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)


#!/usr/bin/env python3

from itertools import accumulate

mod = 10 ** 9 + 7

f = [1] + list(accumulate(list(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)


M,N = 1000000007, 2000
f = [1]*N
for i in range(1,N):
	f[i] = f[i-1]*i%M

n,m = list(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)


def fac(n):
#    print('fac('+str(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)
#print(type(ans))
ans //= fac(v[0]-1)
for i in range(1,len(v)):
#    print('#')
    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(1e9)+7)))


def fac(n):
#    print('fac('+str(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)
#print(type(ans))
ans //= fac(v[0]-1)
for i in range(1,len(v)):
#    print('#')
    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(1e9)+7)))


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)
#print(type(ans))
ans //= fac(v[0]-1)
for i in range(1,len(v)):
#    print('#')
    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(1e9)+7)))


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)
#print(type(ans))
ans //= fac(v[0]-1)
for i in range(1,len(v)):
#    print('#')
    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(1e9)+7)))

n, m = list(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)



# Made By Mostafa_Khaled


#from itertools import permutations
#from operator import itemgetter, attrgetter
#from functools import reduce
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
MOD = int(1e9 + 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)


# https://codeforces.com/problemset/problem/294/C

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():
    # sys.stdin = open('E:\\Sublime\\in.txt', 'r')
    # sys.stdout = open('E:\\Sublime\\out.txt', 'w')
    # sys.stderr = open('E:\\Sublime\\err.txt', 'w')

    # n = int(sys.stdin.readline().strip())
    # a, b = map(int, sys.stdin.readline().strip().split()[:2])

    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)


def __starting_point():
    main()

# hajj
#  　　　　　　 ＿＿
# 　　　　　／＞　　フ
# 　　　　　| 　_　 _ l
# 　 　　　／` ミ＿xノ
# 　　 　 /　　　 　 |
# 　　　 /　 ヽ　　 ﾉ
# 　 　 │　　|　|　|
# 　／￣|　　 |　|　|
# 　| (￣ヽ＿_ヽ_)__)
# 　＼二つ

__starting_point()

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


M= 1000000007
f = [1]*2000
for i in range(1,2000):
    f[i]=f[i-1]*i%M
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)
#print(b)
count = pow(2,sum(b)-len(b),M)*f[n-m]%M
#print(count)
b = [a[0]-1]+b+[n-a[-1]]
#print(b)
#print(f[3])
for i in b:
	count = count*pow(f[i],M-2,M)%M
	#print(pow(f[i],M-2,M))
	#print(i)
print(count)


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)



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



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)



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)

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=list(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()))
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)

    
    
    




import math


def solve( n, list1):
    list1.sort()
    inf = int(1e9 + 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))

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)