Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

def solve(H, N, AB):
    INF = 10e10
    dp = [[INF] * (H+1) for i in range(N+1)]
    dp[0][0] = 0
    A, B = AB[0]
    for j in range(H+1):
        dp[0][j] = min(dp[0][j], dp[0][max(0, j-A)]+B)
    for i in range(1,N):
        A, B = AB[i]
        for h in range(H+1):
            dp[i][h] = min(dp[i-1][h], dp[i][max(0, h-A)]+B)
        #print(i, *dp[i], sep="\t")
    
    return(dp[N-1][H])


def main():
    H, N = map(int, input().split())
    AB = []
    for i in range(N):
        A, B = map(int, input().split())
        AB.append((A, B))
    print(solve(H, N, AB))
main()


### FIXED CODE ###

def solve(H, N, AB):
    INF = 10e10
    dp = [[INF] * (H+1) for i in range(N+1)]
    dp[0][0] = 0
    A, B = AB[0]
    for j in range(H+1):
        dp[0][j] = min(dp[0][j], dp[0][max(0, j-A)]+B)
    for i in range(1,N):
        A, B = AB[i]
        for h in range(H+1):
            dp[i][h] = min(dp[i-1][h], dp[i][max(0, h-A)]+B)
        #print(i, *dp[i], sep="\t")
    
    return(dp[N-1][H])


def main():
    H, N = map(int, input().split())
    AB = []
    for i in range(N):
        A, B = map(int, input().split())
        AB.append((A, B))
    print(solve(H, N, AB))
main()
### BUGGY CODE ###

import itertools

N=int(input())
lst=list(map(int, input().split()))

#max wo erabu

lst=sorted(lst, reverse=True)
count=0
for i in range(N-2):
    for pair in itertools.combinations(lst[i+1:], 2):
        if sum(pair)>lst[i]:
            count+=1

print(count)



### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))

L.sort()
#print(L)

ans=0
for i in range(0, N-2):
    for j in range(i+1, N-1):


        left, right = j, N

        while right-left > 1:
            mid=(left+right) // 2
            if L[i]+L[j] <= L[mid]:
                right=mid
            else:
                left=mid
        ans += left - j
        #print(i,j,left)
print(ans)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def other_members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root and i != x]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return [self.members(r) for r in self.roots()]

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    n, m = map(int, input().split())
    uf = UnionFind(n)
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        uf.union(a, b)
    ans = 0
    for g in uf.all_group_members():
        ans = max(ans, len(g))
    print(ans)



if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    uf = UnionFind(n)
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        uf.union(a, b)
    ans = max(-uf.parents[uf.find(x)] for x in uf.roots())
    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
def pixel_input(H,W,border="."):
    pixel = [[border]*(W+2)] + \
    [[border] + list(input()) + [border] for _ in range(H)] + \
    [[border]*(W+2)]
    return pixel
  
H,W=map(int,input().split())
A=pixel_input(H,W)
 
cnt=0
q,r=[],[]
for i in range(1,H+1):
    for j in range(1,W+1):
        if A[i][j]=="#":
            q.append((i,j))
if len(q)==H*W:
    print(0)
    sys.exit()
while(q):
    while(q):
        i,j=q.pop()
        if A[i-1][j]==".":
            if i-1!=0:
                A[i-1][j]="#"
                r.append((i-1,j))
        if A[i+1][j]==".":
            if i+1!=H+1:
                A[i+1][j]="#"
                r.append((i+1,j))
        if A[i][j-1]==".":
            if j-1!=0:
                A[i][j-1]="#"
                r.append((i,j-1))
        if A[i][j+1]==".":
            if j+1!=W+1:
                A[i][j+1]="#"
                r.append((i,j+1))
    q=[i for i in r]
    r=[]
    cnt+=1
print(cnt-1)

### FIXED CODE ###

H,W = list(map(int,input().split()))
A = [list(str(input())) for i in range(H)]
 
black = []
 
cnt = 0
 
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            black.append([i,j])
 
length = len(black)
            
while (length < H*W):
    gray = []
    for l in black:
        if l[1] != 0:
            c1 = (l[0],l[1]-1)
            if A[c1[0]][c1[1]] == ".":
                gray.append(c1)
                A[c1[0]][c1[1]] = "#"
        if l[1] != W-1:
            c2 = (l[0],l[1]+1)
            if  A[c2[0]][c2[1]] == ".":
                gray.append(c2)
                A[c2[0]][c2[1]] = "#"
        if l[0] != 0:
            c3 = (l[0]-1,l[1])
            if  A[c3[0]][c3[1]] == ".":
                gray.append(c3)
                A[c3[0]][c3[1]] = "#"
        if l[0] != H-1:
            c4 = (l[0]+1,l[1])
            if  A[c4[0]][c4[1]] == ".":
                gray.append(c4)
                A[c4[0]][c4[1]] = "#"
    
    gray = list(set(gray))
    black = [l for l in gray]
    
    cnt += 1
    length += len(black)
    
print(cnt)
### BUGGY CODE ###

k,s = map(int, input().split())

res = 0

for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z == s:
                res += 1

print(res)


### FIXED CODE ###

k,s = map(int, input().split())

res = 0

for x in range(k+1):
    for y in range(k+1):
        z = s-x-y 
        if 0<=z and z<=k:
            res += 1

print(res)
### BUGGY CODE ###

mod = pow(10,9)+7
N,M = map(int,input().split())
A = [int(input()) for i in range(M)]+[mod]
DP = [1]
for i in range(1,N+1):
    if i==A[0]:
        DP.append(0)
        A = A[1:]
    else:
        a = DP[i-1]
        b = DP[i-2] if i>1 else 0
        DP.append((a+b)%mod)
print(DP[N]%mod)

### FIXED CODE ###

import bisect
def f(x,a):
  global M
  b = bisect.bisect_left(a,x)
  if x==a[min(b,M)]:
    return True
  else:
    return False
MOD = 10**9+7
N,M = map(int,input().split())
a = [-1]+[int(input()) for _ in range(M)]
a.sort()
x = 0
y = 1
for i in range(N):
  if f(i,a) and f(i+1,a):
    print(0)
    exit()
  elif f(i+1,a):
    z = 0
  else:
    z = x + y
  x = y
  y = z
print(z%MOD)
### BUGGY CODE ###

n=int(input())
member = [0]*(10**5+1)

li = list(map(int,input().split()))
for i in range(n):
  member[li[i]] +=1

q = int(input())
for j in range(q):
  x,y = map(int,input().split())
  member[y]+=member[x]
  member[x]=0
  total = 0
  for k in range(10**5+1):
    total += k*member[k]
  print(total)

### FIXED CODE ###

n=int(input())
member = [0]*(10**5+1)
 
li = list(map(int,input().split()))
total = sum(li)
for i in range(n):
  member[li[i]] +=1
 
q = int(input())
for j in range(q):
  x,y = input().split()
  x=int(x)
  y=int(y)
  total += (y-x)*member[x]
  print(total)
  member[y]+=member[x]
  member[x]=0
### BUGGY CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

N,Q = II()
a = [0]*(N-1)
b = [0]*(N-1)
p = [0]*Q
x = [0]*Q

for i in range(N-1):
    a1,b1 = II()
    a[i] = a1-1
    b[i] = b1-1

for i in range(Q):
    p1,x1 = II()
    p[i] = p1-1
    x[i] = x1


def bfs(pt,v):
    n=len(pt)
    d=[-1]*n
    d[v]=0
    q=[v]
    c=1
    while q:
        q1=[]
        for i in q:
            for j in pt[i]:
                if d[j]==-1:
                    d[j]=c
                    q1.append(j)
        q=q1
        c+=1
    return d


pt = [[] for _ in range(N)]
for i in range(N-1):
    pt[a[i]].append(b[i])
    pt[b[i]].append(a[i])
d = bfs(pt,0)

parent = defaultdict(list)
for i in range(N-1):
    if d[a[i]]>d[b[i]]:
        parent[a[i]].append(b[i])
    else:
        parent[b[i]].append(a[i])

val = [0]*N
for i in range(Q):
    val[p[i]] += x[i]

for i in range(N):
    now = i
    ans = 0
    while now != 0:
        ans += val[now]
        now = parent[now][0]
    print(val[0]+ans)

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

N,Q = II()
a = [0]*(N-1)
b = [0]*(N-1)
p = [0]*Q
x = [0]*Q

for i in range(N-1):
    a1,b1 = II()
    a[i] = a1-1
    b[i] = b1-1

for i in range(Q):
    p1,x1 = II()
    p[i] = p1-1
    x[i] = x1


parent = defaultdict(list)
for i in range(N-1):
    parent[b[i]].append(a[i])

val = [0]*N
for i in range(Q):
    val[p[i]] += x[i]

for i in range(1,N):
    val[i] += val[parent[i][0]]

print(*val)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split(" ")))

d = {}
for a in A:
    d[A.index(a) + 1] = a

ans = [str(k) for k, _ in sorted(d.items(), key=lambda x: x[1])]
print(" ".join(ans))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split(" ")))

d = dict(zip(range(N), A))

ans = [str(k + 1) for k, _ in sorted(d.items(), key=lambda x: x[1])]
print(" ".join(ans))
### BUGGY CODE ###

A, B, C = list(map(int,input().split()))
K = int(input())

ans = 0
while True:
    if B < A:
        B *= 2
        ans += 1
    if ans == K:
        break
    if B > C:
        C *= 2
        ans += 1
    if ans == K:
        break    
if A < B < C:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

A, B, C = list(map(int,input().split()))
K = int(input())

ans = 0
if A < B < C:
    a = "Yes"
else:    
    while True:
        if B <= A:
            B *= 2
            ans += 1
        if ans == K:
            break
        if A < B < C:
            a = "Yes"
            break
        if B >= C:
            C *= 2
            ans += 1
        if ans == K:
            break
        if A < B < C:
            a = "Yes"
            break
if A < B < C:
    a = "Yes"
else:
    a = "No"
print(a)
### BUGGY CODE ###

from collections import Counter
from copy import deepcopy
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    a_c= Counter(A)
    values = a_c.values()
    val_cnt = Counter(values)
    cnt = 0
    for a in A:
        val_cnt_c = deepcopy(val_cnt)
        val_cnt_c[a_c[a]] -= 1
        val_cnt_c[a_c[a]-1] += 1
        cnt = {int(k*(k-1)/2*v) if k > 1 else 0 for k, v in val_cnt_c.items()}
        print(sum(cnt))
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import Counter
 
def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    a_c = Counter(A)
    res = [int(v*(v-1)/2) for v in a_c.values()]
    cnt = sum(res)
    for a in A:
        ans = (cnt - (a_c[a]-1))
        print(ans)
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

S = input()
Q = int(input())
query = [input().split() for _ in range(Q)]

rev = False
for i in range(Q):
  if query[i][0] == "1":
    rev = not rev
    pass
  else:
    if (not rev and query[i][1] == "1") or (rev and query[i][1] == "2"):
      S = query[i][2] + S
    else:
      S += query[i][2]
  
if rev:
  S = S[::-1]
print(S)

### FIXED CODE ###

S = input()
Q = int(input())
#query = [input().split() for _ in range(Q)]

rev = False
forw = ""
back = ""
for i in range(Q):
  query = input().split()
  if query[0] == "1":
    rev = not rev
  else:
    if (not rev and query[1] == "1") or (rev and query[1] == "2"):
      forw = query[2] + forw
    else:
      back += query[2]
#S = forw + S + back
if rev:
  S = back[::-1] + S[::-1] + forw[::-1]
else:
  S = forw + S + back
print(S)
### BUGGY CODE ###

primes = {2}
for i in range(1, 50000):
    i = 2 * i + 1
    for j in primes:
        if i % j == 0:
            break
    else:
        primes.add(i)

ret = set()
for i in primes:
    if (i + 1) // 2 in primes:
        ret.add(i)
ret = sorted(ret)


def binary(i):
    low = 0
    high = len(ret) - 1
    mid = 0
    while high - low > 1:
        mid = (high + low) // 2
        if ret[mid] < i:
            low = mid
        else:
            high = mid
    return low if ret[low] < i else -1


q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    low = binary(l)
    high = binary(r)
    high += 1 if ret[high+1] == r else 0
    print(high-low)


### FIXED CODE ###

work = [True] * 100001
work[0] = False
work[1] = False
primes = []
for i in range(100001):
    if work[i]:
        for j in range(2* i, 100001, i):
            work[j] = False


csum = [0] * 100001
index = 0
for i in range(1, 100001):
    if work[i] and work[(i+1)//2]:
        csum[i] = csum[i - 1] + 1
    else:
        csum[i] = csum[i - 1]

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    low = csum[l-1]
    high = csum[r]
    print(high-low)
### BUGGY CODE ###

L, R = map(int,input().split())
mod = 2019

ans = 2*pow(10,9)+7
for i in range(L,R):
  for j in range(i+1,R+1):
    val = ((i%mod) * (j%mod))%mod
    ans = min(ans, val)
    if ans == 0:
      break

print(ans)

### FIXED CODE ###

L, R = map(int,input().split())
mod = 2019

ans = pow(10,9)+7
for i in range(L,R):
  for j in range(i+1,R+1):
    val = ((i%mod) * (j%mod))%mod
    ans = min(ans, val)
    if ans == 0:
      break
  if ans == 0:
    break

print(ans)
### BUGGY CODE ###

def get_prime(x):
    if x <= 1:
        return []
    prime = [2]
    limit = int(x**0.5)
    
    data = [i + 1 for i in range(2, x, 2)]
    while limit > data[0]:
        prime.append(data[0])
        data = [j for j in data if j%data[0] != 0]
    
    return prime + data
    

q=int(input())
table = get_prime(100000)
for i in range(q):
    l,r = map(int,input().split())
    ans = 0
    for p in range(l,r+1,2):
        if p in table and (p+1)//2 in table:
            ans +=1
    print(ans)          

### FIXED CODE ###

def get_prime(x):
    l = [True] * (x + 1)
    l[0] = False
    l[1] = False
    for i in range(2,int(x**0.5) + 1):
        if not l[i]:
            continue
        for j in range(i * 2, x + 1, i):
            l[j] = False
    return l        
q=int(input())
table = get_prime(100000)
s=[0]*(100001)

for i in range(100000):
    if table[i] and table[(i+1)//2]:
        s[i] = 1

for i in range(100000):        
    s[i+1] += s[i]

for i in range(q):
    l,r=map(int,input().split())
    print(s[r]-s[l-1])
### BUGGY CODE ###

inf = float('inf')
n = int(input())
g = []
for i in range(n):
    line = list(map(int, input().split()[2:]))
    g.append(zip(line[0::2], line[1::2]))

distance = [inf] * n
distance[0] = 0
visited = [False] * n
current = 0

while not all(visited):
    visited[current] = True
    for v, c in g[current]:
        if not visited[v] and distance[current] + c < distance[v]:
            distance[v] = distance[current] + c
    min_i = 0
    min_d = inf
    for i in range(n):
        if not visited[i] and distance[i] < min_d:
            min_i = i
            min_d = distance[i]
    current = min_i

for i in range(n):
    print(i, distance[i])

### FIXED CODE ###

from heapq import heappush, heappop

inf = float('inf')
n = int(input())
g = []
for i in range(n):
    line = list(map(int, input().split()[2:]))
    g.append(zip(line[0::2], line[1::2]))

dist = [inf] * n
dist[0] = 0
heap = [(0, 0)]

while heap:
    current = heappop(heap)[1]
    for v, c in g[current]:
        new_dist = dist[current] + c
        if new_dist < dist[v]:
            dist[v] = new_dist
            heappush(heap, (new_dist, v))

for i in range(n):
    print(i, dist[i])
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
A = [[0] * (W + 2)] + [[0] + [H * W] * W + [0] for _ in range(H)] + [[0] * (W + 2)]
que = deque()
for i in range(1, H+1):
    for j, a in enumerate(list(input())):
        if a == '#':
            A[i][j+1] = 0
            que.append((i, j + 1))

step = [(1, 0), (-1, 0), (0, 1), (0, -1)]
res = 0
while que:
    h, w = que.popleft()
    for dh, dw in step:
        nh = h + dh
        nw = w + dw
        if A[h][w] + 1 < A[nh][nw]:
            A[nh][nw] = A[h][w] + 1
            res = max(res, A[nh][nw])
            que.append((nh, nw))
print(res)

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
B = deque()
check = [[H*W for _ in range(W)] for _ in range(H)]
for h in range(H):
    a = input()
    if a.count("#") > 0:
        b = [(h, w) for w, e in enumerate(a) if e == "#"]
        B += b
        for bx, bw in b:
            check[bx][bw] = 0

move = [(1, 0), (-1, 0), (0, 1), (0, -1)]

while B:
    x, y = B.pop()
    for dx, dy in move:
        nx, ny = x + dx, y + dy
        if -1 < nx < H and -1 < ny < W:
            if check[nx][ny] > check[x][y] + 1:
                check[nx][ny] = check[x][y] + 1
                B.appendleft((nx, ny))
print(max(max(c) for c in check))
### BUGGY CODE ###

n, k = map(int, input().split())
arr = list(map(int, input().split()))
cnt = 0
while True:
    cnt += 1
    new = [0 for _ in range(n)]
    for i in range(n):
        # for j in range(n):
        #     if abs(i-j) < arr[j]:
        #         # print(arr[i], arr[j], i, j)
        #         new[i] += 1
        new[max(0, i-arr[i])] += 1

        tmp = i+arr[i]+1
        # print(max(0, i-arr[i]), tmp, i)
        if tmp < n:
            new[tmp] -= 1

    for i in range(1, n):
        new[i] += new[i-1]
    # print(new)
    arr = new
    # print(arr)
    if min(arr) >= n or cnt >= k:
        # print(min(arr), cnt)
        break

for i in arr:
    print(i, end=" ")

### FIXED CODE ###

n, k = map(int, input().split())
arr = list(map(int, input().split()))
cnt = 0
# n = int(input())
# arr = [0 for _ in range(n)]
while True:
    cnt += 1
    new = [0 for _ in range(n)]
    for i in range(n):
        new[max(0, i-arr[i])] += 1

        tmp = i+arr[i]+1
        if tmp < n:
            new[tmp] -= 1

    flag = 1
    for i in range(1, n):
        new[i] += new[i-1]
        if new[i] < n:
            flag = 0

    arr = new
    # print(arr)
    if flag or cnt >= k:
        break
# print(cnt)
for i in arr:
    print(i, end=" ")
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))

ans = 0

for index, p in enumerate(P):
  flag = 0

  for i in range(index):
    if p > P[i]:
      flag = 1

  if flag == 0:
    ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))

ans = 0
min = 10000000

for p in P:
  if min > p:
    ans += 1
    min = p

print(ans)
### BUGGY CODE ###

import math
n=int(input())

a=int(math.sqrt(n))

if n%2 != 0:
    if a%2==0: a+=1
    while n%a != 0:a+=2
else:
    while n%a != 0:a+=1

b=int(n/a)

a_dig = len(str(a))
b_dig = len(str(b))

ans=max(a_dig,b_dig)

print(ans)

### FIXED CODE ###

import math
n = int(input())
nn = int(math.sqrt(n))
while n%nn != 0: nn-=1
ans = len(str(n//nn))
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
a_list = sorted(map(int, input().split()))
for _ in range(M):
    a_list[-1] //= 2
    a_list.sort()
print(sum(a_list))


### FIXED CODE ###

import heapq

N, M = map(int, input().split())
a_list = list(map(lambda x: int(x) * (-1), input().split()))
heapq.heapify(a_list)
for _ in range(M):
    min_num = heapq.heappop(a_list)
    heapq.heappush(a_list, (-1) * (-min_num // 2))
print(-sum(a_list))
### BUGGY CODE ###

N, M= map(int, input().split())

A = list(map(int, input().split()))

for i in range(M):
    A.sort()
    A[-1] = A[-1] // 2
print(sum(A))

### FIXED CODE ###

import heapq
N, M = map(int, input().split())

a = list(map(lambda x: -int(x), input().split()))
heapq.heapify(a)

for i in range(M):
    heapq.heappush(a, int(heapq.heappop(a)/2))

print(-sum(a))
### BUGGY CODE ###

import math

def move(n):
	twonum = n // 2
	com = 0
	for i in range(twonum + 1):
		up = n - i
		com += math.factorial(up) // (math.factorial(up - i) * math.factorial(i))
	return com

N, M = map(int, input().split())
a = []
a.append(0)
for i in range(M):
	a.append(int(input()))
a.append(N+1)

s = 1
for i in range(M+1):
	step = a[i+1] - a[i] - 1
	if step > 1000000007:
		step = step % 1000000007
	m = move(step)
	s = s * m
	a[i+1] += 1

print(s % 1000000007)


### FIXED CODE ###

MOD = 1000000007

fact = [0 for i in range(100001)] # fact[i] = i! mod MOD
inv_fact = [0 for i in range(100001)] # inv_fact[i] = i!のmod MODでの逆元
 
# aのn乗をPで割った余りを求めるよ
def mod_pow(a, n, P):
	if n == 0: # aの0乗は1（それはそう）
		return 1
	if n%2 == 0: # aの4乗は（aの2乗）の2乗、みたいなノリ
		x = mod_pow(a, n/2, P)
		return (x*x)%P
	# aの5乗はa×（aの4乗）、みたいなノリ
	return (a*mod_pow(a, n-1, P))%P
 
# nCk mod MODを求める！！
def comb(n, k):
	if n < k:
		return 0
	ans = fact[n]
	ans = (ans * inv_fact[k])%MOD
	ans = (ans * inv_fact[n-k])%MOD
	return ans

def move(n):
	twonum = n // 2
	com = 0
	for i in range(twonum + 1):
		up = n - i
		com += comb(up, i)
	return com

# fact,inv_factを初期化
fact[0] = inv_fact[0] = 1
for i in range(100000):
	# (i+1)!ってi!に(i+1)をかけたものだよね
	fact[i+1] = (fact[i]*(i+1))%MOD
	# (i+1)!の逆元って、i!の逆元に(i+1)の逆元をかけたものだよね
	inv_fact[i+1] = (inv_fact[i]*mod_pow(i+1, MOD-2, MOD))%MOD

N, M = map(int, input().split())
a = []
a.append(0)
for i in range(M):
	a.append(int(input()))
a.append(N+1)

s = 1
for i in range(M+1):
	step = a[i+1] - a[i] - 1
	if step > MOD:
		step = step % MOD
	m = move(step)
	s = (s * m) % MOD
	a[i+1] += 1

print(s)
### BUGGY CODE ###

a,b = map(int,input().split())

if a == b:
    print(a)
    exit()

c = 0
d = a

e = ((b - a) // 4)*4

while True:
    if d >= b:
        break
    d += 4

d = a + e + 1
while True:
    if d > b:
        break
    a ^= d
    d += 1
print(a)


### FIXED CODE ###

A,B = map(int,input().split())
 
aa,bb = 0,0
if (A-1) % 2 == 0:
    if ((A-1) //2) % 2 == 0:
        aa = (A-1)^1
    else:
        aa = (A-1)
else:
    if ((A+1) //2) % 2 == 0:
        aa = 1
 
if B % 2 == 0:
    if (B//2) % 2 == 0:
        bb = B^1
    else:
        bb = B
else:
    if ((B+1) //2) % 2 == 0:
        bb = 1
 
print(aa^bb)