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

def sr(f):
    for i in range(len(A)):
            for j in range(len(A[i])):
                if A[i][j] == f:
                    return i, j

H, W, D = list(map(int, input().split()))
A = []
for i in range(H):
    A.append(list(map(int, input().split())))
Q = int(input())
LR = []
for i in range(Q):
    LR.append(list(map(int, input().split())))

for lr in LR:
    mp = 0
    l, r = lr[0], lr[1]
    li, lj = sr(l)
    while l != r:
        nextLi, nextLj = sr(l+D)
        mp += abs(nextLi-li) + abs(nextLj-lj)
        l += D
        li, lj = nextLi, nextLj
    print(mp)


### FIXED CODE ###

H, W, D = list(map(int, input().split()))
A = []
for i in range(H):
    A.append(list(map(int, input().split())))
Q = int(input())
LR = []
for i in range(Q):
    LR.append(list(map(int, input().split())))

d = [0 for i in range(H*W+1)]
sA = [0 for i in range(H*W+1)]

for i in range(len(A)):
        for j in range(len(A[i])):
            sA[A[i][j]] = [i, j]

for i in range(D+1, H*W+1):
    d[i] = d[i-D] + abs(sA[i][0]-sA[i-D][0]) + abs(sA[i][1]-sA[i-D][1])

for lr in LR:
    l, r = lr[0], lr[1]
    print(d[r] - d[l])
### BUGGY CODE ###

from collections import defaultdict

MOD = 1000000007
iist = lambda: map(int,input().split())

N,M = iist()
Q = defaultdict(list)
for i in range(M):
  l,r,x = iist()
  Q[r].append((l,x))

if any(x != 1 for l,x in Q[1]):
  print(0)
  exit(0)

dp = defaultdict(int)
dp[0,0] = 3

x_sum = [3]
y_sum = [3]
s = 3

for pk in range(1,N):
  k = pk+1

  dp.update(((i,pk),s%MOD) for i,s in enumerate(map(sum, zip(x_sum,y_sum))))

  for i in range(pk):
    x_sum[i] += dp[i,pk]
  x_sum.append(0)
  y_sum.append((2*s)%MOD)
  s *= 3

  removes = [(i,j) for i,j in dp.keys()
            if any(x != (l<=i)+(l<=j)+1 for l,x in Q[k])]

  for i,j in removes:
    c = dp[i,j]
    del dp[i,j]
    x_sum[i] -= c
    y_sum[j] -= c
    s -= c

  for i in range(pk):
    x_sum[i] %= MOD
    y_sum[i] %= MOD
  s %= MOD

print(s)

### FIXED CODE ###

from collections import defaultdict

MOD = 1000000007
iist = lambda: map(int,input().split())

N,M = iist()
Q = defaultdict(list)
for i in range(M):
  l,r,x = iist()
  Q[r].append((l,x))

if any(x != 1 for l,x in Q[1]):
  print(0)
  exit(0)

dp = defaultdict(int)
dp[0,0] = 3

x_sum = [3]
y_sum = [3]
s = 3

for pk in range(1,N):
  k = pk+1

  for i,(a,b) in enumerate(zip(x_sum,y_sum)):
    c = (a+b)%MOD
    dp[i,pk] = c
    x_sum[i] += c

  x_sum.append(0)
  y_sum.append((2*s)%MOD)
  s *= 3
  subQ = Q[k]

  for i,j in list(dp.keys()):
    for l,x in subQ:
      if x != (l<=i)+(l<=j)+1:
        c = dp[i,j]
        x_sum[i] -= c
        y_sum[j] -= c
        s -= c
        del dp[i,j]
        break

  for i in range(pk):
    x_sum[i] %= MOD
    y_sum[i] %= MOD
  s %= MOD

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

n,m,r = map(int,input().split())
R = tuple(map(int,input().split()))
ABC = [list(map(int,input().split())) for _ in range(m)]
inf = 1000000000

edge = [[inf]*(n+1) for _ in range(n+1)]

for a,b,c in ABC:
    edge[a][b] = c
    edge[b][a] = c

def wf(e,n):
    for s in range(1,n+1):
        for g in range(1,n+1):
            for k in range(1,n+1):
                e[s][g] = min(e[s][g],e[s][k] + e[k][g])
                e[g][s] = e[s][g]
    return e
    


from itertools import permutations as pm

temp = list(pm(R))

ans = 10000000000
Edge = wf(edge,n)

for RR in temp:
    cost = 0
    for i in range(r-1):
        cost += Edge[RR[i]][RR[i+1]]
    if cost < ans:
        ans = cost

print(ans)

### FIXED CODE ###

n,m,rrr = map(int,input().split())
R = tuple(map(int,input().split()))
ABC = [list(map(int,input().split())) for _ in range(m)]
inf = 1000000000

edge = [[inf]*(n+1) for _ in range(n+1)]

for a,b,c in ABC:
    edge[a][b] = c
    edge[b][a] = c
    
def dijkstra(start,e,N):
    for _ in range(3):
        for v in range(1,N+1):#中間
            for g in range(1,N+1):#ゴール
                e[start][g] = min(e[start][g],e[start][v] + e[v][g])
                e[g][start] = e[start][g]
    return e[start]

dic = {}
for rr in R:
    dic[rr] = dijkstra(rr,edge,n)

from itertools import permutations as pm

temp = list(pm(R))

ans = 10000000000
for RR in temp:
    cost = 0
    for i in range(rrr-1):
        cost += dic[RR[i]][RR[i+1]]
    if cost < ans:
        ans = cost
print(ans)
### BUGGY CODE ###

import sys
N=int(input())
S=input()

def z_alg(S):
  N=len(S)
  Z=[N]+[0]*(N-1)
  i,j=1,0
  while i<N:
    while i+j<N and S[j]==S[i+j]:
      j+=1
    if not j:
      i+=1
      continue
    Z[i]=j
    k=1
    while N-i>k and k<j-Z[k]:
      Z[i+k]=Z[k]
      k+=1
    i+=k
    j-=k
  return Z

answer=0
for i in range(N):
  zlist=z_alg(S[i:])
  #print(i,S[i:],zlist)
  for j in range(N-i):
    if j>=zlist[j] and answer<zlist[j]:
      answer=zlist[j]
      
print(answer)

### FIXED CODE ###

import sys
N=int(input())
S=input()

def z_alg(S):
  N=len(S)
  Z=[N]+[0]*(N-1)
  i,j=1,0
  while i<N:
    while i+j<N and S[j]==S[i+j]:
      j+=1
    if not j:
      i+=1
      continue
    Z[i]=j
    k=1
    while N-i>k and k<j-Z[k]:
      Z[i+k]=Z[k]
      k+=1
    i+=k
    j-=k
  return Z

answer=0
for i in range(N):
  zlist=z_alg(S[i:])
  #print(i,S[i:],zlist)
  for j in range(N-i):
    if j>=zlist[j] and answer<zlist[j]:
      answer=zlist[j]
      
print(answer)
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
a=0
for i in range(n-k+1):
    a=max(sum(p[i:i+k]),a)
print(a/2+k/2)


### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
a=0
pp=[0]
for i in p:
    a+=i
    pp.append(a)
a=0
for i in range(k,n+1):
    a=max(a,pp[i]-pp[i-k])

print(a/2+k/2)
### BUGGY CODE ###

import math
import bisect
import collections

N = int(input())
A = list(map(int,input().split()))
C = collections.Counter(A)
A = sorted(list(C.keys()))
#print(C)
#print(A)

ans = 0
for i in range(len(A)-1,-1,-1):
  a = A[i]
  b = (1<<(int(math.log(a,2))+1))-a
  if a == b:
    ans += C[a]//2
    C[a] -= C[a]//2*2
  else:
    r = bisect.bisect_left(A[:i], b)
    if r < i and A[r] == b:
      mn = min(C[a],C[A[r]])
      ans += mn
      C[a] -=  mn
      C[A[r]] -= mn
print(ans)


### FIXED CODE ###

import math
import bisect
import collections

N = int(input())
A = list(map(int,input().split()))
C = collections.Counter(A)
A = sorted(list(C.keys()))
#print(C)
#print(A)

ans = 0
for i in range(len(A)-1,-1,-1):
  a = A[i]
  b = (1<<(int(math.log(a,2))+1))-a
  if a == b:
    ans += C[a]//2
    C[a] -= C[a]//2*2
  else:
    r = bisect.bisect_left(A, b)
    if r < i and A[r] == b:
      mn = min(C[a],C[A[r]])
      ans += mn
      C[a] -=  mn
      C[A[r]] -= mn
print(ans)
### BUGGY CODE ###

from math import gcd
from functools import reduce


def lcm(x, y):
    return x * y // gcd(x, y)


def main():
    _ = int(input())
    a = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    a_lcm = reduce(lcm, a)
    print(sum([(a_lcm // aa) % mod for aa in a]) % mod)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from math import gcd
from functools import reduce


def main():
    _ = int(input())
    a = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    def lcm(x, y):
        return x * y // gcd(x, y)

    a_lcm = reduce(lcm, a)
    print(sum([a_lcm * pow(aa, mod - 2, mod) % mod for aa in a]) % mod)


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

n = int(input())
a = list(map(int,input().split()))

ans=1
for i in a:
    ans*=i
if(ans>10**18):
    ans=-1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
if 0 in a:
    print(0)
    exit()

ans=1
for i in a:
    ans*=i
    if ans>10**18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

import collections
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.dist = [0] * n
 
    def root(self, i, d):
        if self.parent[i] == i:
            return i, d
        else:
            self.parent[i], d2 = self.root(self.parent[i], d + self.dist[i])
            return self.parent[i], d2
    
    def find(self, x, y):
        return self.root(x) == self.root(y)
 
    def union(self, i, j, d):
        i2, d1 = self.root(i, 0)
        j2, d2 = self.root(j, 0)
        if i2 < j2 :
            self.parent[j2] = i2
            self.dist[j] = d1 + d
        else:
            self.parent[i2] = j2
            self.dist[i] = d2 + d
            
N = int(input())
ps = [list(map(int, input().split())) for _ in range(N-1)]
ps.sort()
ps = collections.deque(ps)
tree = UnionFind(N)
prv = set([1])
while ps:
    i, j, d = ps.popleft()
    if i in prv or j in prv:
        tree.union(i-1, j-1, d)
        prv.add(i)
        prv.add(j)
    else:
        ps.append([i, j, d])

for d in tree.dist:
    if d % 2 == 0:
        print(1)
    else:
        print(0)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
n=int(input())
G=[[]for i in range(n+1)]
for i in range(n-1):
    a, b, c = map(int,input().split())
    G[a] += (b,c),
    G[b] += (a,c),
    
d = [0]*(n+1) #1から各点への距離
def f(v,p,u): #v:今見ているとこ p:一つ前に見たとこ u:1からの距離
    d[v] = u
    for t, c in G[v]:
        if p != t:
            f(t,v,u+c)
f(1,0,0)
for i in range(n):
    if d[i+1] % 2 == 0:
        print(1)
    else:
        print(0)
### BUGGY CODE ###

from collections import deque

n, m = map(int, input().split())
a = [0] * m
b = [0] * m
for i in range(m):
    aa, bb = map(int, input().split())
    a[i], b[i] = aa, bb

path = [[] for _ in range(n+1)]
for i in range(m):
    aa, bb = a[i], b[i]
    path[bb].append(aa)
    path[aa].append(bb)

ans = [0] * (n+1)
que = deque([[1, 1]])
while len(que) > 0:
    idx = que.popleft()
    if ans[idx[0]] == 0:
        ans[idx[0]] = idx[1]
    for i in path[idx[0]]:
        if ans[i] == 0:
            deque.append(que, [i, idx[0]])

print('Yes')
for i in range(2, n+1):
    print(ans[i])

### FIXED CODE ###

import sys
from collections import deque
import time
input = sys.stdin.readline

n, m = map(int, input().split())

path = [[] for _ in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    path[a].append(b)
    path[b].append(a)

ans = [0] * (n+1)
alr = [0] * (n+1)
que = deque([1])
while len(que) > 0:
    idx = que.popleft()
    for i in path[idx]:
        if alr[i] == 0:
            que.append(i)
            ans[i] = idx
            alr[i] = 1
        else:
            pass

print('Yes')
for i in range(2, n+1):
    print(ans[i])
### BUGGY CODE ###

# coding: utf-8

N, M = (int(x) for x in input().split())

pass_ids = []
for i in range(M):
	L, R = (int(x) - 1 for x in input().split())

	for j in range(L, R + 1):
		pass_ids.append(j)

print(int(len([x for x in pass_ids if pass_ids.count(x) == M]) / M))

### FIXED CODE ###

# coding: utf-8

N, M = (int(x) for x in input().split())

pass_ids = [x for x in range(N)]

L_max, R_min = 0, N
for i in range(M):
	L, R = (int(x) - 1 for x in input().split())
	
	if L_max < L:
		L_max = L
	if R_min > R:
		R_min = R


if L_max < R_min + 1:
	print(len(list(range(L_max, R_min + 1))))
else:
	print("0")
### BUGGY CODE ###

import bisect
import copy
import heapq
import sys
import itertools
import queue

input = sys.stdin.readline
sys.setrecursionlimit(100000)
# mod = 10 ** 9 + 7
mod = 998244353


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: int(x) - 1, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n)


def main():
    N, S = read_values()
    A = read_list()

    dp = [[0 for _ in range(3)] for _ in range(S + 1)]
    dp[0][0] = 1

    for a in A:
        for s in range(S, -1, -1):
            dp[s] = [
                dp[s][0] % mod,
                (
                    (dp[s][1] + dp[s][0]) % mod
                    + (0 if s - a < 0 else dp[s - a][0] + dp[s - a][1]) % mod
                )
                % mod,
                (
                    sum(dp[s]) % mod
                    + (0 if s - a < 0 else dp[s - a][1] + dp[s - a][0]) % mod
                )
                % mod,
            ]

    print(dp[S][2])


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline
sys.setrecursionlimit(100000)
# mod = 10 ** 9 + 7
mod = 998244353


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: int(x) - 1, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n)


def main():
    N, S = read_values()
    A = read_list()

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

    for a in A:
        for s in range(S, -1, -1):
            d1 = dp[s][0]
            d2 = (dp[s][1] + (0 if s - a < 0 else dp[s - a][1]) + d1) % mod
            d3 = (dp[s][2] + (0 if s - a < 0 else dp[s - a][1]) + d2) % mod
            dp[s] = (d1, d2, d3)

    print((dp[S][2] - dp[S][1]) % mod)


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


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

xy = []
xlis = []
ylis = []

for i in range(N):

    x,y = map(int,input().split())

    xy.append([x,y])

    if x not in xlis:
        xlis.append(x)
    if y not in ylis:
        ylis.append(y)

ans = float("inf")
xlis.sort()
ylis.sort()

for rp in range(len(xlis)):

    right = xlis[rp]

    for lp in range(rp+1):

        left = xlis[lp]

        for upp in range(len(ylis)):

            up = ylis[upp]

            for dp in range(upp+1):

                down = ylis[dp]

                able = 0
                nable = 0
                for i in range(N):

                    nx = xy[i][0]
                    ny = xy[i][1]
                    if left <= nx and nx <= right and down <= ny and ny <= up:
                        able += 1
                    else:
                        nable += 1

                    if able >= K or nable > N-K:
                        break

                if able >= K:
                    now = max(1,right-left) * max(1,up-down)
                    ans = min(ans,now)

print (ans)


### FIXED CODE ###


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

xy = []
xlis = []
ylis = []

for i in range(N):

    x,y = map(int,input().split())

    xy.append([x,y])

    if x not in xlis:
        xlis.append(x)
    if y not in ylis:
        ylis.append(y)

ans = float("inf")
xlis.sort()
ylis.sort()

for rp in range(len(xlis)):

    right = xlis[rp]

    for lp in range(rp+1):

        left = xlis[lp]

        for upp in range(len(ylis)):

            up = ylis[upp]

            for dp in range(upp+1):

                down = ylis[dp]

                able = 0
                nable = 0
                for i in range(N):

                    nx = xy[i][0]
                    ny = xy[i][1]
                    if left <= nx and nx <= right and down <= ny and ny <= up:
                        able += 1
                    else:
                        nable += 1

                    if able >= K or nable > N-K:
                        break

                if able >= K:
                    now = max(1,right-left) * max(1,up-down)
                    ans = min(ans,now)

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

import sys
sys.setrecursionlimit(4100000)

N, Q = map(int,input().split())
edge = [[] for i in range(N+1)]

for _ in range(N-1):
    a, b = map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)

children = [[] for i in range(N+1)]

def dfs(parent,i):
    for k in edge[i]:
        if parent != k:
            children[i].append(k)
            dfs(i,k)
        
dfs(-1,1)

cnt = [0 for i in range(N+1)]

for i in range(Q):
    p, x = map(int,input().split())
    cnt[p] += x

def dfs_solve(i):
    for k in children[i]:
        cnt[k] += cnt[i]
        dfs_solve(k)

dfs_solve(1)

ans = cnt[1:]

print(*ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]
 
graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
 
value = [0] * (N+1)
for p,x in PX:
    value[p] += x

def dfs(parent,i,add):
    for k in graph[i]:
        if k != parent:
            value[k] += add
            dfs(i,k,value[k])
    

dfs(0,1,value[1])

ans = value[1:]

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

from math import sqrt
from itertools import combinations


def is_prime(x):
    if x < 2:
        return False
    for i in range(2, int(sqrt(x)) + 1):
        if x % i == 0:
            return False

    return True


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

a_li = [1]
b_li = [1]
div = 2

while a != 1 or b != 1:
    if is_prime(div):
        cnt = 0
        while a % div == 0:
            a //= div
            cnt += 1
        a_li.append(cnt)

        cnt = 0
        while b % div == 0:
            b //= div
            cnt += 1
        b_li.append(cnt)

    if div == 2:
        div += 1
    else:
        div += 2

ans = 0
for ae, be in zip(a_li, b_li):
    if ae and be:
        ans += 1

print(ans)


### FIXED CODE ###

from math import sqrt


def is_prime(x):
    if x < 2:
        return False
    for i in range(2, int(sqrt(x)) + 1):
        if x % i == 0:
            return False

    return True


def f(x):
    st = set()
    for i in range(1, int(sqrt(x)) + 1):
        if x % i == 0:
            st.add(i)
            st.add(x // i)

    return st


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

a_set = f(a)
b_set = f(b)

ans = 0
for e in a_set:
    if is_prime(e) or e == 1:
        if e in b_set:
            ans += 1

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

n = int(input())
a = list(map(int,input().split()))
mod = 10**9 + 7
bits = [0]*60
for x in a:
    i = 0
    while x > 0:
        if x % 2 == 1:
            bits[i] += 1
        x //= 2
        i += 1
ans = 0
for i in range(60):
    ans += (bits[i] * (n-bits[i])) * pow(2, i, mod)
    ans %= mod
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
mod = 10**9 + 7
bits = [0]*60
for x in a:
    i = 0
    while x > 0:
        if x % 2 == 1:
            bits[i] += 1
        x //= 2
        i += 1
ans = 0
for i in range(60):
    ans += (bits[i] * (n-bits[i])) * pow(2, i, mod)
    ans %= mod
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
a=  list(map(int,input().split()))

for i in range(m):
    a[a.index(max(a))]=a[a.index(max(a))] //2

print(sum(a))

### FIXED CODE ###

import heapq
n,m = map(int,input().split())
a=  list(map(int,input().split()))
h = list(map(lambda x:-1*x,a))
heapq.heapify(h)
for i in range(m):
    heapq.heapreplace(h,-(-h[0]//2))
print(-1*sum(h))
### BUGGY CODE ###

def solve(n, q, a, b, p, x):
    E = [[] for i in range(n+1)]
    for a_i, b_i in zip(a, b):
        E[a_i].append(b_i)
        E[b_i].append(a_i)
    res = {i: 0 for i in range(1, n+1)}
    for j in range(q):
        res[p[j]] += x[j]
    used = [False] * (n+1)
    used[1] = True
    que = [1]
    while que:
        u = que.pop(0)
        for v in E[u]:
            if not used[v]:
                used[v] = True
                res[v] += res[u]
                que.append(v)
    return " ".join(map(str, [res[i] for i in range(1,n+1)]))

n, q = map(int, input().split())
a = [0] * (n-1)
b = [0] * (n-1)
for i in range(n-1):
    a[i], b[i] = map(int, input().split())
p = [0] * q
x = [0] * q
for j in range(q):
    p[j], x[j] = map(int, input().split())
print(solve(n, q, a, b, p, x))

### FIXED CODE ###

from collections import deque

def solve(n, q, a, b, p, x):
    E = [[] for i in range(n+1)]
    for a_i, b_i in zip(a, b):
        E[a_i].append(b_i)
        E[b_i].append(a_i)
    res = {i: 0 for i in range(1, n+1)}
    for j in range(q):
        res[p[j]] += x[j]
    used = [False] * (n+1)
    used[1] = True
    que = deque([1])
    while que:
        u = que.popleft()
        for v in E[u]:
            if not used[v]:
                used[v] = True
                res[v] += res[u]
                que.append(v)
    return " ".join(map(str, [res[i] for i in range(1,n+1)]))

n, q = map(int, input().split())
a = [0] * (n-1)
b = [0] * (n-1)
for i in range(n-1):
    a[i], b[i] = map(int, input().split())
p = [0] * q
x = [0] * q
for j in range(q):
    p[j], x[j] = map(int, input().split())
print(solve(n, q, a, b, p, x))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

def solve(N: int):
    n = str(N)
    pay = ""
    kuriage = 0
    LEN = len(n)
    pay_count = 0

    for i in range(LEN-1,-1,-1):
        if i != 0:
            if int(n[i-1]) >= 5:
                if int(n[i])+kuriage <= 4:
                    pay += str(int(n[i])+kuriage)
                    pay_count += int(n[i])+kuriage
                    kuriage = 0
                else:
                    pay += "0" 
                    kuriage = 1
            else:
                if int(n[i])+kuriage <= 5:
                    pay += str(int(n[i])+kuriage)
                    pay_count += int(n[i])+kuriage
                    kuriage = 0
                else:
                    pay += "0" 
                    kuriage = 1
        else:
            if int(n[i])+kuriage <= 5:
                pay += str(int(n[i])+kuriage)
                pay_count += int(n[i])+kuriage
                kuriage = 0
            else:
                pay += "0" 
                kuriage = 1

    if kuriage == 1:
        pay += "1"
        pay_count += 1
    
    pay = pay[::-1]
    oturi = int(pay)-N
    # pay_count = 0
    oturi_count = 0
    
    for i in str(oturi):
        oturi_count += int(i)

    print(pay_count+oturi_count)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

def solve(N: str):
    n = list(map(int,list(N)))
    kuriage = 0
    LEN = len(n)
    pay_count = 0

    for i in range(LEN-1,-1,-1):
        if i != 0:
            if n[i-1] >= 5:
                if n[i]+kuriage <= 4:
                    pay_count += n[i]+kuriage
                    kuriage = 0
                else:
                    pay_count += 10-(n[i]+kuriage)
                    kuriage = 1
            else:
                if n[i]+kuriage <= 5:
                    pay_count += n[i]+kuriage
                    kuriage = 0
                else:
                    pay_count += 10-(n[i]+kuriage)
                    kuriage = 1
        else:
            if n[i]+kuriage <= 5:
                pay_count += n[i]+kuriage
                kuriage = 0
            else:
                pay_count += 10-(n[i]+kuriage)
                kuriage = 1

    if kuriage == 1:
        pay_count += 1
    print(pay_count)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = next(tokens)
    solve(N)

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

n,m = map(int,input().split())
para = [int(input()) for i in range(m)]
mod = 10**9+7
dp = [0]*(n+1)
for i in range(n+1):
    if  i not in para :
        if i == 1 or i==0:
            dp[i] = 1
        else:
            dp[i] = (dp[i-1] + dp[i-2])%mod
    else :
        dp[i] = 0


print("{}".format(dp[-1]))

### FIXED CODE ###

n,m = map(int,input().split())
para = [int(input()) for i in range(m)]
mod = 10**9+7
dp = [-1]*(n+1)
for i in para:
    dp[i] = 0
for i in range(n+1):
    if  dp[i] != 0 :
        if i == 1 or i==0:
            dp[i] = 1
        else:
            dp[i] = (dp[i-1] + dp[i-2])%mod



print("{}".format(dp[-1]))