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

H,N=map(int,input().split())
dp=[10**12 for _ in range(H+1)]
dp[0]=0
for i in range(N):
  h,n=map(int,input().split())
  for j in range(H+1):
    dp[j]=min(dp[j],dp[max(0,j-h)]+n)
print(dp[H])

### FIXED CODE ###

H,N=map(int,input().split())
a=[]
max_x=-10**10
for i in range(N):
  x,y=map(int,input().split())
  if x>max_x:
    max_x=x
  a.append([x,y])
  
dp = [0] * (H+max_x)
for i in range(0,H+max_x):
    if i==0:
        dp[i]=0
    else:
        dp[i]=min(dp[i-l[0]]+l[1] for l in a )
print(dp[H])
### BUGGY CODE ###

N=int(input())
A=[]
for i in range(N):
    h,p=map(int,input().split())
    A.append((h+p,h,p))
A.sort()


dp=[[10**23]*(N+1) for i in range(N+1)]
for i in range(N+1):
    dp[i][0]=0
for i in range(1,N+1):
    for j in range(1,N+1):
        #print(A[i-1])
        if dp[i-1][j-1]>A[i-1][1]:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=min(dp[i-1][j],dp[i-1][j-1]+A[i-1][2])
for j in range(N,-1,-1):
    if dp[N][j]<10**23:
        print(j)
        break

### FIXED CODE ###

N=int(input())
A=[]
for i in range(N):
    h,p=map(int,input().split())
    A.append((h+p,h,p))
A.sort()
dp=[[10**13]*(N+1) for i in range(N+1)]
for i in range(N+1):
    dp[i][0]=0
for i in range(1,N+1):
    s=A[i-1][1]
    t=A[i-1][2]
    for j in range(1,i+1):
        #print(A[i-1])
        if dp[i-1][j-1]>s:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=min(dp[i-1][j],dp[i-1][j-1]+t)
for j in range(N,-1,-1):
    if dp[N][j]<10**13:
        print(j)
        break
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]

answer = N

for i in range(N):
    a = A[i]
    for j in range(i+1, N):
        finish = False
        for k in range(min(len(bin(a)), len(bin(A[j])))-2):
            if int(bin(a)[-k-1]) & int(bin(A[j])[-k-1]) == 1:
                finish = True
                break
        if finish:
            break
        answer += 1
        a += A[j]

print(answer)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]

right = 0
answer = 0
now = 0

for left in range(N):
    while right < N and now + A[right] == now ^ A[right]:
        now += A[right]
        right += 1

    answer += right - left

    if right == left:
        right += 1
    else:
        now -= A[left]


print(answer)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()

for _ in range(Q):
    l, r = map(int, input().split())
    s = S[l-1:r]
    ans = 0
    for i in range(len(s)-1):
        if s[i:i+2] == 'AC':
            ans += 1
    print(ans)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()

t = [0] * (N+1)
for i in range(N):
    t[i+1] = t[i] + (1 if S[i:i+2] == 'AC' else 0)

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

num = int(input())
dic = [input() for i in range(num)]

sdic = []
ans = 0
for i in range(num):
    dic[i] = "".join(sorted(dic[i]))
while len(dic) > 0:
    now = dic[0]
    cnt = dic.count(now)
    ans += int((cnt * (cnt - 1)) / 2)
    for i in range(cnt):
        dic.remove(now)
print(ans)

### FIXED CODE ###

num = int(input())
li = [input() for i in range(num)]

dic = {}
ans = 0
for i in range(num):
    now = "".join(sorted(li[i]))
    if now in dic:
        dic[now] += 1
    else:
        dic[now] = 1
for i in dic:
    n = dic[i]
    ans += int((n*(n-1))/2)

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

N,K = map(int,input().split())
P = list(map(int,input().split()))
Q = list()
for i in range(N-K+1):
  Q.append(sum(P[i:i+K])+K)
print(max(Q)/2)

### FIXED CODE ###

N,K = map(int,input().split())
P = list(map(int,input().split()))
Q = list()
for i in range(N-K+1):
  if i == 0:
    Q.append(sum(P[i:i+K]))
  else:
    Q.append(Q[i-1]-P[i-1]+P[i+K-1])
print((max(Q)+K)/2)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

N, M = map(int, raw_input().split())
line = []   # 定期便
for i in range(M):
    a, b = map(int, raw_input().split())
    line.append([a, b])
line.sort()

for l in line:
    if l[0] > 1:
        break
    else:
        for k in line:
            if k[0] == l[1] and k[1] == N:
                print 'POSSIBLE'
                exit()

print 'IMPOSSIBLE'


### FIXED CODE ###

# -*- coding: utf-8 -*-

N, M = map(int, raw_input().split())
start, finish = [], []
for i in range(M):
    a, b = map(int, raw_input().split())
    if a == 1:
        start.append(b)
    elif b == N:
        finish.append(a)

if set(start) & set(finish):
    print 'POSSIBLE'
else:
    print 'IMPOSSIBLE'
### BUGGY CODE ###

N, W = map(int, input().split(' '))
pair = [tuple(map(int, input().split(' '))) for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
    for sum_w in range(W+1):
        if sum_w >= pair[i][0]:
            dp[i+1][sum_w] = max(dp[i][sum_w], dp[i][sum_w-pair[i][0]] + pair[i][1])
        else:
            dp[i+1][sum_w] = dp[i][sum_w]
print(dp[-1][-1])

### FIXED CODE ###

N, W = map(int, input().split(' '))
pair = [tuple(map(int, input().split(' '))) for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
    for sum_w in range(W+1):
        if sum_w >= pair[i][0]:
            dp[i+1][sum_w] = max(dp[i][sum_w], dp[i][sum_w-pair[i][0]] + pair[i][1])
        else:
            dp[i+1][sum_w] = dp[i][sum_w]
print(dp[-1][-1])
### BUGGY CODE ###

h,w,m=map(int, input().split())
from collections import defaultdict
hd=defaultdict(int)
wd=defaultdict(int)
hw=defaultdict(int)

for i in range(m):
    h0,w0=map(int, input().split())
    hd[h0]+=1
    hw[(h0,w0)]+=1
    wd[w0]+=1

max_h_list = [kv[0] for kv in hd.items() if kv[1] == max(hd.values())]
max_w_list = [kv[0] for kv in wd.items() if kv[1] == max(wd.values())]

ans=float('inf')
for x in max_h_list:
    for y in max_w_list:
        if hw[(x,y)]==1:
            ans=min(ans,1)
        else:
            ans=min(ans,0)
            break

print(hd[max_h_list[0]]+wd[max_w_list[0]]-ans)


### FIXED CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline
h,w,m=map(int, input().split())
hd=[0 for i in range(h+1)]
wd=[0 for i in range(w+1)]
hw=defaultdict(int)
hmax=0
wmax=0
for i in range(m):
    h0,w0=map(int, input().split())
    hd[h0]+=1
    hmax=max(hmax,hd[h0])
    wd[w0]+=1
    wmax=max(wmax,wd[w0])
    hw[(h0,w0)]+=1

max_h_list=[]
max_w_list=[]
for k in range(h+1):
    if hd[k]==hmax:
        max_h_list.append(k)

for k in range(w+1):
    if wd[k]==wmax:
        max_w_list.append(k)

ans=float('inf')

for x in max_h_list:
    for y in max_w_list:
        if hw[(x,y)]==1:
            ans=min(ans,1)
        else:
            ans=min(ans,0)
            break
print(hmax+wmax-ans)
### BUGGY CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
l = [0,2,5,5,4,5,6,3,7,6]

dp = [0]*(n+1)
for i in range(n):
    for j in range(m):
        if dp[i] == 0 and i != 0:
            continue
        x = a[j]
        t = l[x]
        if i+t > n:
            continue
        if dp[i] == 0:
            s0 = x
            s1 = x
        else:
            s0 = str(x)+str(dp[i])
            s1 = str(dp[i])+str(x)
        dp[i+t] = max(dp[i+t],int(s0),int(s1))
print(dp[-1])

### FIXED CODE ###

from math import log10
n,m = map(int,input().split())
a = list(map(int,input().split()))
l = [0,2,5,5,4,5,6,3,7,6]

dp = [0]*(n+1)
for i in range(n):
    for j in range(m):
        if dp[i] == 0 and i != 0:
            continue
        x = a[j]
        t = l[x]
        if i+t > n:
            continue
        if dp[i] == 0:
            s0 = x
            s1 = x
        else:
            k = int(log10(dp[i]))
            s0 = x*10**(k)+dp[i]
            s1 = 10*dp[i]+x
        dp[i+t] = max(dp[i+t],s0,s1)
print(dp[-1])
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC113 C

n,m = map(int,input().split())
py = [list(map(int,input().split())) for _ in range(m)]
x = sorted(py, key = lambda x:(x[0],x[1]))

rank = [[] for _ in range(n)]
for p,y in x:
    rank[p-1].append([p,y])
for p,y in py:
    front = '00000'+str(p)
    back = '00000'+str(rank[p-1].index([p,y])+1)
    print(front[-6:]+back[-6:])


### FIXED CODE ###

#!/usr/bin/env python3
#ABC113 C

from operator import itemgetter
n,m = map(int,input().split())
py = [list(map(int,input().split())) for _ in range(m)]
for i in range(m):
    py[i].append(i)
py.sort(key = itemgetter(1))
py.sort(key = itemgetter(0))

x = py[0][0]
c = 0
for i in range(m):
    if x != py[i][0]:
        c = 1
        x = py[i][0]
    else:
        c += 1
    py[i].append(c)
py.sort(key = itemgetter(2))
for i in range(m):
    front = '00000'+str(py[i][0])
    back = '00000'+str(py[i][3])
    print(front[-6:]+back[-6:])
### BUGGY CODE ###

import numpy as np
import sys
input = sys.stdin.readline

INF = 10 ** 15

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

LRCs = [tuple(map(int, input().split())) for _ in range(M)]
LRCs.sort(key = lambda t: (t[1], t[0]))

dp = np.full(N, INF, np.int64)
dp[0] = 0
for L, R, C in LRCs:
    while dp[R-1] > dp[L-1] + C:
        dp[R-1] = dp[L-1] + C
        R -= 1

if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline

INF = 10 ** 15

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

LRCs = [tuple(map(int, input().split())) for _ in range(M)]
LRCs.sort(key = lambda t: (t[1], t[0]))

dp = [INF] * N
dp[0] = 0
for L, R, C in LRCs:
    while dp[R-1] > dp[L-1] + C:
        dp[R-1] = dp[L-1] + C
        R -= 1

if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import numpy as np

N = int(input())
A = [int(input()) for _ in range(N)]

p1 = 0
p2 = 0
P1 = np.zeros(N+1, dtype=int)
P2 = np.zeros(N+1, dtype=int)
for i, a in enumerate(A):
    if a == 0:
        p1 -= 2
        p2 += 1
    elif a % 2 == 0:
        p2 -= 1
    elif a % 2 == 1:
        p1 -= 1
        p2 += 1
    p1 += a
    P1[N-1-i] = p1
    P2[N-1-i] = p2

S = sum(A)
"""
dp = [[0, 0, 0, 0] for _ in range(N+1)]

dp[N] = [P1[N], P1[N]+P2[N], -P1[N], 0]

for i in reversed(range(N)):
    dp[i][0] = max(dp[i+1][0], P1[i])
    dp[i][1] = max(dp[i+1][1], P2[i]+dp[i][0])
    dp[i][2] = min(dp[i+1][2], P2[i]-dp[i][1])
    dp[i][3] = min(dp[i+1][3], P1[i]+dp[i][2])
"""

dp = np.zeros((N+1, 4), dtype=int)
dp[0, :] = np.array([P1[0], P1[0]+P2[0], -P1[0], 0])
for i, (p1, p2) in enumerate(zip(P1, P2)):
    if i == 0: continue
    dp[i, 0] = np.maximum(dp[i-1, 0], p1)
    dp[i, 1] = np.maximum(dp[i-1, 1], p2+dp[i, 0])
    dp[i, 2] = np.minimum(dp[i-1, 2], p2-dp[i, 1])
    dp[i, 3] = np.minimum(dp[i-1, 3], p1+dp[i, 2])

print(dp[N, 3]+S)


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
A = [int(input()) for _ in range(N)]

p1 = 0
p2 = 0
P1 = [0]
P2 = [0]
for a in A:
    if a == 0:
        p1 -= 2
        p2 += 1
    elif a % 2 == 0:
        p2 -= 1
    elif a % 2 == 1:
        p1 -= 1
        p2 += 1
    p1 += a
    P1.append(p1)
    P2.append(p2)

S = sum(A)
dp = [[0, 0, 0, 0] for _ in range(N+1)]

dp[N] = [P1[N], P1[N]+P2[N], -P1[N], 0]

for i in reversed(range(N)):
    dp[i][0] = max(dp[i+1][0], P1[i])
    dp[i][1] = max(dp[i+1][1], P2[i]+dp[i][0])
    dp[i][2] = min(dp[i+1][2], P2[i]-dp[i][1])
    dp[i][3] = min(dp[i+1][3], P1[i]+dp[i][2])

print(dp[0][3]+S)
### BUGGY CODE ###

import itertools

N, P = [int(i) for i in input().split()]
biscuits = [int(i) for i in input().split()]
even = []
odd = []

for i in biscuits:
    if i % 2 == 0:
        even.append(i)
    elif i % 2 == 1:
        odd.append(i)

if P == 0:
    # even
    answer = 1
    for i in range(1, len(even)+1):
        c = list(itertools.combinations(even,i))
        answer += len(c)
    for i in range(2, len(odd)+1, 2):
        c = list(itertools.combinations(odd,i))
        answer += len(c)
    print(answer)
elif P == 1:
    # odd
    answer = 0
    even_c = 1
    odd_c = 0
    for i in range(1, len(even)+1):
        c = list(itertools.combinations(even,i))
        even_c += len(c)
    for i in range(1, len(odd)+1, 2):
        c = list(itertools.combinations(odd,i))
        odd_c += len(c)
    print(even_c * odd_c)

### FIXED CODE ###

import itertools

N, P = [int(i) for i in input().split()]
biscuits = [int(i) for i in input().split()]
even = 0
odd = 0
buffer_count = 1
even_c = 1

for i in biscuits:
    if i % 2 == 0:
        even += 1
    elif i % 2 == 1:
        odd += 1

if P == 0:
    # even
    odd_c = 1
elif P == 1:
    # odd
    odd_c = 0

if even > odd:
    for i in range(1, even+1):
        even_c += 2 ** (i-1)
        if i == odd:
            buffer_count = even_c
elif odd >= even:
    for i in range(1, odd+1):
        buffer_count += 2 ** (i-1)
        if i == even:
            even_c = buffer_count

if P == 0:
    # even
    if buffer_count > 2:
        odd_c = (buffer_count / 2)
elif P == 1:
    # odd
    if buffer_count > 1:
        odd_c = (buffer_count / 2)

print(int(even_c * odd_c))
### BUGGY CODE ###

h, w, m = map(int, input().split())
bord_x, bord_y = [0 for i in range(h)], [0 for i in range(w)]
bord = [[] for _i in range(h)]

for _i in range(m):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    bord_x[s] += 1
    bord_y[t] += 1
    bord[s].append(t)

x_max, y_max = max(bord_x), max(bord_y)
a = [x for x, p in enumerate(bord_x) if x_max==p]
b = [y for y, p in enumerate(bord_y) if y_max==p]

checker = 0
for i in a:
    for j in b:
        if not(j in bord[i]):
            import sys
            print(x_max+y_max)
            sys.exit()
        else:
            checker += 1
            if checker >= m:
                break

print(x_max+y_max-1)

### FIXED CODE ###

h, w, m = map(int, input().split())
bord_x, bord_y = [0]*h, [0]*w
 
hw = []
for _i in range(m):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    bord_x[s] += 1
    bord_y[t] += 1
    hw.append([s, t])
 
x_max, y_max = max(bord_x), max(bord_y)
 
cnt = 0
for i, j in hw:
    if bord_x[i] == x_max and bord_y[j] == y_max:
        cnt += 1
 
if cnt == bord_x.count(x_max)*bord_y.count(y_max):
    x_max -= 1
 
print(x_max+y_max)
### BUGGY CODE ###

def grid2graph(grid):
    # .が道で#が壁のグリッドをグラフに変換する
    H, W = len(grid), len(grid[0])
    f = {}
    cnt = 0
    for h in range(H):
        for w in range(W):
            if grid[h][w] == '.':
                f[(h, w)] = cnt
                cnt += 1
    G = [[] for i in range(cnt)]
    for h in range(H):
        for w in range(W):
            if grid[h][w] == '#':
                continue
            i = f[(h, w)]
            if 0 <= h-1 and grid[h-1][w] == '.':
                j = f[(h-1, w)]
                G[i].append(j)
            if 0 <= w-1 and grid[h][w-1] == '.':
                j = f[(h, w-1)]
                G[i].append(j)
            if h+1 < H and grid[h+1][w] == '.':
                j = f[(h+1, w)]
                G[i].append(j)
            if w+1 < W and grid[h][w+1] == '.':
                j = f[(h, w+1)]
                G[i].append(j)
    return G


def warshall_floyd(G):
    inf = 10**18
    n = len(G)
    d = [[inf for i in range(n)] for j in range(n)]
    for i in range(n):
        d[i][i] = 0
        for j in G[i]:
            d[i][j] = 1
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])
    return d


H, W = map(int, input().split())
S = []
for h in range(H):
    S.append(list(input()))
G = grid2graph(S)
d = warshall_floyd(G)
n = len(d)
ans = 0
for i in range(n-1):
    for j in range(n):
        ans = max(ans, d[i][j])
print(ans)


### FIXED CODE ###

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
import numpy as np
H, W = map(int, input().split())
S = []
for h in range(H):
    Sh = list(input())
    S.append(Sh)
G = [[0 for _ in range(H*W)] for _ in range(H*W)]
for h in range(H):
    for w in range(W):
        if S[h][w] == '.':
            if h > 0 and S[h-1][w] == '.':
                G[h * W + w][(h - 1) * W + w] = 1
                G[(h - 1) * W + w][h * W + w] = 1
            if w > 0 and S[h][w-1] == '.':
                G[h * W + w][h * W + (w - 1)] = 1
                G[h * W + (w - 1)][h * W + w] = 1
            if h < H - 1 and S[h+1][w] == '.':
                G[h * W + w][(h + 1) * W + w] = 1
                G[(h + 1) * W + w][h * W + w] = 1
            if w < W - 1 and S[h][w+1] == '.':
                G[h * W + w][h * W + (w + 1)] = 1
                G[h * W + (w + 1)][h * W + w] = 1
graph = csr_matrix(G)
dist_matrix = floyd_warshall(csgraph=graph, directed=False)
max_dist = 0
for i in range(H * W):
    for j in range(H * W):
        d = dist_matrix[i][j]
        if d != np.inf and d > max_dist:
            max_dist = d
print(int(max_dist))
### BUGGY CODE ###

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

for i in range(k):
    if a > 0:
        a-=1
    else:
        if b > 0:
            b-=1
        else:
            break

print(a,b)


### FIXED CODE ###

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

if a > k:
    print(a-k,b)
elif a+b> k:
    print(0,b-(k-a))
else:
    print(0,0)
### BUGGY CODE ###

import bisect
def main():
    N = int(input())
    L = list(map(int,input().split()))
    L.sort()
    Lind = []
    count = 0
    for i in reversed(range(2,N)):
        for j in reversed(range(1,i)):
            if L[i] < 2*L[j]:
                Lind.append([i,j])
    for l in Lind:
        cind = bisect.bisect_left(L,L[l[0]]-L[l[1]])
        for k in range(cind,l[1]):
            if L[l[0]]<L[l[1]]+L[k]:
                count += 1
    print(count)
main()

### FIXED CODE ###

import bisect
def main():
    N = int(input())
    L = list(map(int,input().split()))
    L.sort()
    
    count = 0
    for i in range(N-2):
        for j in range(i+1,N-1):
            c = bisect.bisect_left(L,L[i]+L[j])
            
            count += max(0,c-1 - j)
    
    print(count)
main()
### BUGGY CODE ###

import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


if __name__ == '__main__':
    S = input()

    que = queue.Queue()
    que.put("")
    ans = False
    while not que.empty():
        t = que.get()
        if len(S) == len(t):
            if S == t:
                ans = True
                break
        elif len(S) > len(t):
            que.put(t + "dreamer")
            que.put(t + "dream")
            que.put(t + "erase")
            que.put(t + "eraser")

    if ans:
        print("YES")
    else:
        print("NO")


### FIXED CODE ###

import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


if __name__ == '__main__':
    S = input()

    i = 0
    ans = False
    while True:
        res = S[i:i + 5]
        if res == "dream":
            i = i + 5
            if S[i:i + 5] == "dream":
                continue
            elif S[i:i + 7] == "erdream":
                i = i + 2
                continue
            elif S[i:i + 5] == "erase":
                continue
            elif S[i:i + 7] == "ererase":
                i = i + 2
                continue
            elif i == len(S):
                ans = True
                break
            elif i == len(S) - 2:
                if S[i:] == "er":
                    ans = True
                    break
                else:
                    ans = False
                    break
            else:
                ans = False
                break
        elif res == "erase":
            i = i + 5
            if S[i:i + 5] == "dream":
                continue
            elif S[i:i + 6] == "rdream":
                i = i + 1
                continue
            elif S[i:i + 5] == "erase":
                continue
            elif S[i:i + 6] == "rerase":
                i = i + 1
                continue
            elif i == len(S):
                ans = True
                break
            elif i == len(S) - 1:
                if S[i:] == "r":
                    ans = True
                    break
                else:
                    ans = False
                    break
            else:
                ans = False
                break

    if ans:
        print("YES")
    else:
        print("NO")
### BUGGY CODE ###

n=int(input())
res=0
for i in range(1,n+1):
  for j in range(i,n+1,i):
    res+=j
print(res)


### FIXED CODE ###

n=int(input())
res=0
for i in range(1,n+1):
  ahaha=n//i
  res+=(i+ahaha*i)*ahaha//2
print(res)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np
import statistics
from statistics import mean, median,variance,stdev
import math

def main():
	N, M = map(int, input().split(" "))
	N += 1
	a = []
	for i in range(M):
		tmp = int(input())
		tmp += 1
		a.append(tmp)
		if i != 0 and tmp == a[-1]+1:
			print(0)
			sys.exit()
			
	DP = [0 for i in range(N)]
	for i in range(N):
		if i == 0:
			DP[0] = 1
			continue
		if N-i in a:
			continue
		tmp = 0
		if i-1 >= 0:
			tmp = (tmp + (DP[i-1] % 1000000007)) % 1000000007
		if i-2 >= 0:
			tmp = (tmp + (DP[i-2] % 1000000007)) % 1000000007
		DP[i] = tmp
		
	#print(DP)
	print(DP[-1])
	
	
if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys
import numpy as np
MOD = 1000000007
def main():
    n, m = [int(x) for x in input().split()]
    pattern = [1]
    broken = -1
    brokencnt = 0
    if brokencnt < m:
        broken = int(input())
        brokencnt += 1
    for i in range(1, n + 1):
        if i == broken:
            pattern.append(0)
            if brokencnt < m:
                broken = int(input())
                brokencnt += 1
            continue
        if i == 1:
            pattern.append(pattern[i - 1])
        if i > 1:
            pattern.append((pattern[i - 1] + pattern[i - 2]) % MOD)
    print(pattern[n])
main()
### BUGGY CODE ###

l = input()
mod = 10 ** 9 + 7
ans = 1
for key, i in enumerate(reversed(l)):
    if i == "1":
        ans =  (3 ** key + 2 * ans) % mod
print(ans)


### FIXED CODE ###

l = reversed(list(input()))
mod = 10 ** 9 + 7
ans = 1
for key, i in enumerate(l):
    if i == "1":
        ans = (pow(3,key,mod) % mod + 2 * ans) % mod
print(ans)
### BUGGY CODE ###

# -*- conding: utf-8 -*-
import itertools
import math
K = int(input())

def gcd(a, b):
  if a > b:
    x = a
    y = b
  else:
    x = b
    y = a
    
  if y == 0:
    return x
  else:
    return gcd(y, x % y)

ans = 0
for x in list(itertools.product(range(1, K+1), repeat=3)):
  # xに対して最大公約数を求める
  ans += gcd(gcd(x[0], x[1]), x[2])
print(ans)

### FIXED CODE ###

# -*- conding: utf-8 -*-
import math
K = int(input())

ans = 0
for a in range(1, K+1):
  for b in range(1, K+1):
    x = math.gcd(a, b)  
    for c in range(1, K+1):
      ans += math.gcd(x, c)
print(ans)