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

# WA出そう
INF = 10**18


def main():
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    N = int(input())
    T = [[int(i) for i in input().split()] for j in range(N)]
    pow_2 = [pow(2, i) for i in range(N+1)]
    X_dist = [[0]*N for _ in range(1 << N)]
    Y_dist = [[0]*N for _ in range(1 << N)]

    # bitという道路群を建設したときの，各集落の評価距離
    for bit in range(1 << N):
        cur_x = [0]
        cur_y = [0]
        for i in range(N):
            if bit & (1 << i):
                cur_x.append(T[i][0])
                cur_y.append(T[i][1])
        for i, (x, y, p) in enumerate(T):
            X_dist[bit][i] = p*min(abs(cx - x) for cx in cur_x)
            Y_dist[bit][i] = p*min(abs(cy - y) for cy in cur_y)

    answer = [INF] * (N+1)
    for bit in range(3**15):
        x_bit = 0
        y_bit = 0
        cnt = 0
        b = bit
        for i in range(N):
            d = b % 3
            b //= 3
            if d == 2:
                # x = a
                x_bit += pow_2[i]
                cnt += 1
            elif d == 1:
                # y = a
                y_bit += pow_2[i]
                cnt += 1
        # 距離の評価
        cur_d = 0
        for i in range(N):
            cur_d += min(X_dist[x_bit][i], Y_dist[y_bit][i])
        answer[cnt] = min(answer[cnt], cur_d)

    for ans in answer:
        print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# writer解(c++)を写経した．answerのfor文のところ何やってるかさっぱりわかりませんが…
# https://atcoder.jp/contests/m-solutions2020/submissions/15122924
import sys
input = sys.stdin.readline
INF = 10**13


def main():
    N = int(input())
    X = []
    Y = []
    P = []
    for _ in range(N):
        a, b, c = (int(i) for i in input().split())
        X.append(a)
        Y.append(b)
        P.append(c)
    X_dist = [[0]*N for _ in range(1 << N)]
    Y_dist = [[0]*N for _ in range(1 << N)]

    # bitという道路群を建設したときの，各集落の評価距離
    # bit 001001 とかの1が立っている集落に道を作る
    for bit in range(1 << N):
        for i in range(N):
            X_dist[bit][i] = P[i]*abs(X[i])
            Y_dist[bit][i] = P[i]*abs(Y[i])
            for k in range(N):
                if bit & (1 << k):
                    X_dist[bit][i] = \
                        min(X_dist[bit][i], P[i]*abs(X[i] - X[k]))
                    Y_dist[bit][i] = \
                        min(Y_dist[bit][i], P[i]*abs(Y[i] - Y[k]))

    # これはなに？
    answer = [INF] * (N+1)
    for i in range(1 << N):
        cnt = 0
        for j in range(N):
            if (i >> j) & 1:
                cnt += 1
        j = i
        while j >= 0:
            j &= i
            cost = 0
            for k in range(N):
                if not((i >> k) & 1):
                    cost += min(X_dist[j][k], Y_dist[i - j][k])
            answer[cnt] = min(answer[cnt], cost)
            j -= 1

    for ans in answer:
        print(ans)


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

N,M=(int(i) for i in input().split())
gate=[]
for i in range(M):
    gate.append([int(i) for i in input().split()])

answer=0
for i in range(N+1):
    ok=1
    for l,r in gate:
        if l<=i and i<=r:
            pass
        else:
            ok=0
            break
    if ok==1:
        answer+=1
print(answer)
        

### FIXED CODE ###

N,M=(int(i) for i in input().split())
gate=[]
for i in range(M):
    gate.append([int(i) for i in input().split()])
    
maxl=max(gate,key=lambda x:x[0])[0]
minr=min(gate,key=lambda x:x[1])[1]
if maxl<=minr:
    print(minr-maxl+1)
else:
    print(0)
### BUGGY CODE ###

N , T = map(int,input().split())
AB = []
for _ in range(N):
    AB.append(list(map(int,input().split())))
dp = [-1] * (T+3000)
dp[0] = 0
for a,b in sorted(AB):
    for i in range(T-1,-1,-1):
        if dp[i] == -1:
            continue
        if dp[i+a] < dp[i] + b:
            dp[i+a] = dp[i] +b 
print(max(dp))

### FIXED CODE ###

import numpy as np
 
N, T = map(int, input().split())
data = []
for i in range(N):
  a, b = map(int, input().split())
  data.append((a,b))
data.sort()
data = np.array(data)

dp = np.zeros(T)
ans = 0
for a, b in data:
    ans = max(ans,dp[-1]+b)
    if a< T:
        newtable = dp[:T-a] + b
        dp[a:] = np.maximum(dp[a:], newtable)

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

import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, M = MI()
adj = [list() for _ in range(N)]
for _ in range(M):
    u, v = map(lambda s: int(s) - 1, input().split())
    adj[u].append(v)
S, T = map(lambda s: int(s) - 1, input().split())

st = [(0, S, 0)]
seen = {(0, S)}
while len(st) > 0:
    dim, v, cnt = st.pop()
    if dim == 0 and v == T:
        print(cnt // 3)
        exit(0)
    ndim = (dim + 1) % 3
    for nxt in adj[v]:
        if (ndim, nxt) not in seen:
            st.append((ndim, nxt, cnt + 1))
print(-1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(300000)
from collections import deque

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, M = MI()
adj = [list() for _ in range(N)]
for _ in range(M):
    u, v = map(lambda s: int(s) - 1, sys.stdin.readline().split())
    adj[u].append(v)
S, T = map(lambda s: int(s) - 1, sys.stdin.readline().split())

q = deque([(0, S, 0)])
seen = {S}
while len(q) > 0:
    dim, v, cnt = q.popleft()
    if v == T and dim == 0:
        print(cnt // 3)
        exit(0)
    ndim = (dim + 1) % 3
    for nxt in adj[v]:
        if (ndim * N + nxt) not in seen:
            q.append((ndim, nxt, cnt + 1))
            seen.add(ndim * N + nxt)
print(-1)
### BUGGY CODE ###

import numpy as np
import itertools
def p(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
n=int(input())
p=p(n)
if len(p)==1:
    print(p[0]-1)
    exit()
a=10**12
b=1
for i in p:
    b*=i
for k in range(1,len(p)):    
    for i in itertools.combinations(p, k):
        c=np.prod(np.asarray(i))
        a=min(a,c+b//c)
print(a-2)
    

### FIXED CODE ###

n=int(input())
a=10**12
for i in range(1,int(n**0.5)+2):
    if n%i==0:
        a=min(a,i+n//i-2)
print(a)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
maze = [list(input()) for _ in range(H)]

import numpy as np
dp = np.array([[INF]*W*H for _ in range(W*H)])

for i in range(H*W):
	for j in range(H*W):
		if maze[i//W][i%W] == "#":
			continue
		if maze[j//W][j%W] == "#":
			continue
		if i == j:
			dp[i][j] = 0
		if i + W == j:
			dp[i][j] = 1
		if i + 1 == j:
			if i%W == W - 1:
				continue
			dp[i][j] = 1
		if i - W == j:
			dp[i][j] = 1
		if i - 1 == j:
			if i%W == 0:
				continue
			dp[i][j] = 1

for i in range(W*H):
	for s in range(W*H):
		for e in range(W*H):
			if maze[i//W][i%W] == "#":
				continue
			if maze[s//W][s%W] == "#":
				continue
			if maze[e//W][e%W] == "#":
				continue
			dp[s][e] = min(dp[s][e], dp[s][i] + dp[i][e]);

ma = 0
for i in range(len(dp)):
	for j in range(len(dp[i])):
		if dp[i][j] == INF:
			continue
		ma = max(ma, dp[i][j])

print(int(ma))

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	H, W = MAP()
	maze = [list(input()) for _ in range(H)]
	dp = [[INF]*W*H for _ in range(W*H)]

	for i in range(H*W):
		for j in range(H*W):
			if maze[i//W][i%W] == "#":
				continue
			if maze[j//W][j%W] == "#":
				continue
			if i == j:
				dp[i][j] = 0
			if i + W == j:
				dp[i][j] = 1
			if i + 1 == j:
				if i%W == W - 1:
					continue
				dp[i][j] = 1
			if i - W == j:
				dp[i][j] = 1
			if i - 1 == j:
				if i%W == 0:
					continue
				dp[i][j] = 1

	for i in range(W*H):
	    for j, c2 in enumerate(row[i] for row in dp):
	           for k, (c1, c3) in enumerate(zip(dp[j], dp[i])):
	               if c1 > c2+c3:
	                   dp[j][k] = c2+c3

	ma = 0
	for i in range(len(dp)):
		for j in range(len(dp[i])):
			if dp[i][j] == INF:
				continue
			ma = ma if ma > dp[i][j] else dp[i][j]

	print(int(ma))

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

from collections import defaultdict

def answer():
    n, p = map(int, input().split())
    s = input()
    m = defaultdict(int)
    ans = 0
    if p == 2 or p == 5:
        for i, ss in enumerate(s):
            if int(ss) % p == 0:
                ans += i + 1
        return ans
    for i in range(1, len(s)+1):
        m[int(s[-i:]) % p] += 1
    m[0] += 1
    for i in range(p):
        if m[i] >= 2:
            ans += m[i] * (m[i] - 1) // 2
    return ans

print(answer())




### FIXED CODE ###

from collections import defaultdict

def answer():
    n, p = map(int, input().split())
    s = input()
    m = defaultdict(int)
    ans = 0
    if p == 2 or p == 5:
        for i, ss in enumerate(s):
            if int(ss) % p == 0:
                ans += i + 1
        return ans
    sss = 0
    for i, ss in enumerate(s[::-1]):
        sss = (sss + pow(10, i, p) * int(ss)) % p
        m[sss] += 1
    m[0] += 1
    for i in range(p):
        if m[i] >= 2:
            ans += m[i] * (m[i] - 1) // 2
    return ans

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

s = list(input())
s.reverse()
n = len(s)
mod = 10**9+7
#dp[i][j] := 下からi桁目まで決めたとき、13で割った余りがjの個数
dp = [[0 for i in range(13)] for j in range(n+1)]
dp[0][0] = 1
for i in range(n):
    for j in range(13):
        char = s[i]
        if char == '?':
            for k in range(10):
                #i+1桁目をkにする
                tmp = (k * pow(10, i)) % 13
                dp[i+1][(j + tmp) % 13] += dp[i][j]
                dp[i+1][(j + tmp) % 13] %= mod
        else:
            x = int(char)
            tmp = (x * pow(10, i)) % 13
            dp[i+1][(j + tmp) % 13] += dp[i][j]
            dp[i+1][(j + tmp) % 13] %= mod
print(dp[n][5])



### FIXED CODE ###

s = input()
#文字の昇順に処理していきたいため、逆順にしておく
s = s[::-1]
mod = 7 + 10**9
keta = 1
dp = [[0 for i in range(13)] for j in range(len(s) + 1)]
dp[0][0] = 1
for i in range(len(s)):
    if s[i] != "?":
        k = (int(s[i]) * keta) % 13
        for j in range(13):
            dp[i + 1][(j + k) % 13] = dp[i][j]
    else:
        for j in range(13):
            for k in range(10):
                l = ( k * keta ) % 13
                dp[i + 1][(j + l) % 13] += dp[i][j] % mod
    keta = keta *10 % 13 
print(dp[-1][5] % mod)
### BUGGY CODE ###

d = []
while True:
    s = input()
    if s[2] == "d":
        break
    elif s[0] == "i":
        d.append(int(s[7:]))
    else:
        print(d.pop(d.index(max(d))))


### FIXED CODE ###

from heapq import *
a = []
while True:
    s = input()
    if s[2] == "d":break
    elif s[0] == "i":heappush(a, -int(s[7:]))
    else:print(-heappop(a))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
h,w=map(int,input().split())
a=[list(map(int,input().split())) for i in range(h)]
b=[list(map(int,input().split())) for i in range(h)]

c=[[0]*w for i in range(h)]
for i in range(h):
  for j in range(w):
    c[i][j]=abs(a[i][j]-b[i][j])

dp=[[[0 for k in range(80*(h+w)+1)] for i in range(w)] for j in range(h)]
dp[0][0][c[0][0]]=1
for i in range(h):
  for j in range(w):
    for k in range(80*(i+j)+1):
      if dp[i-1][j][abs(k-c[i][j])]==1 or dp[i][j-1][abs(k-c[i][j])]==1 or dp[i-1][j][k+c[i][j]]==1 or dp[i][j-1][k+c[i][j]]:
        dp[i][j][k]=1

for i in range(80*(h+w)+1):
  if dp[h-1][w-1][i]==1:
    print(i)
    break

### FIXED CODE ###

import sys
input=sys.stdin.readline

def main():
  h,w=map(int,input().split())
  a=[list(map(int,input().split())) for i in range(h)]
  b=[list(map(int,input().split())) for i in range(h)]
  dp=[[[0]*(80*(h+w+1)+1) for i in range(w)] for j in range(h)]
  dp[0][0][abs(a[0][0]-b[0][0])]=1
  for i in range(h):
    for j in range(w):
      c=abs(a[i][j]-b[i][j])
      if i!=0 or j!=0:
        for k in range(80*(i+j+1)+1):
          dp[i][j][k]=dp[i-1][j][abs(k-c)]|dp[i-1][j][k+c]|dp[i][j-1][abs(k-c)]|dp[i][j-1][k+c]
  for i in range(80*(h+w+1)+1):
    if dp[h-1][w-1][i]==1:
      print(i)
      break

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

n = int(input())
v = [int(i) for i in input().split()]
v_even = v[::2]
v_odd = v[1::2]
e_max = 0
e_max_ele = 0
for e in set(v_even):
    tmp = v_even.count(e)
    if e_max < tmp:
        e_max = tmp
        e_max_ele = e
ans1 = len(v_even) - e_max

o_max = 0
o_max_ele = 0
for o in set(v_odd):
    tmp = v_odd.count(o)
    if o_max < tmp:
        o_max = tmp
        o_max_ele = o
ans2 = len(v_odd) - o_max

if e_max_ele == o_max_ele:
    if e_max < o_max:
        ban = e_max_ele
        e_max = 0
        e_max_ele = 0
        for e in set(v_even):
            if e == ban:
                continue
            tmp = v_even.count(e)
            if e_max < tmp:
                e_max = tmp
                e_max_ele = e
        ans1 = len(v_even) - e_max
    else:
        ban = o_max_ele
        o_max = 0
        o_max_ele = 0
        for o in set(v_odd):
            if o == ban:
                continue
            tmp = v_odd.count(o)
            if o_max < tmp:
                o_max = tmp
                o_max_ele = o
        ans2 = len(v_odd) - o_max

print(ans1+ans2)

### FIXED CODE ###

def main():
    n = int(input())
    v = [int(i) for i in input().split()]
    v_even = v[::2]
    v_odd = v[1::2]
    from collections import Counter
    v_even_cnt = sorted(list(Counter(v_even).items()),key=lambda x:x[1],reverse=True)
    v_odd_cnt = sorted(list(Counter(v_odd).items()),key=lambda x:x[1],reverse=True)
    ans = 0
    if v_even_cnt[0][0] != v_odd_cnt[0][0]:
        ans = len(v_even) - v_even_cnt[0][1] + len(v_odd) - v_odd_cnt[0][1]
    else:
        if len(v_even_cnt) == 1:
            ans = len(v_even)
        else:
            ans1 = len(v_even) - v_even_cnt[0][1] + len(v_odd) - v_odd_cnt[1][1]
            ans2 = len(v_even) - v_even_cnt[1][1] + len(v_odd) - v_odd_cnt[0][1]
            ans = min(ans1,ans2)
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

a, b, x = [int(i) for i in input().split()]
count = 0

for i in range(a, b + 1):
  if i % x == 0:
    count += 1

print(count)

### FIXED CODE ###

a, b, x = [int(i) for i in input().split()]

if a % x == 0:
  print(b // x - a // x + 1)
else:
  print(b // x - a // x)
### BUGGY CODE ###

import bisect
def bisect_left_reverse(a, x):
    if a[0] <= x:
        return 0
    if x < a[-1]:
        return len(a)
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] <= x:
            ok = mid
        else:
            ng = mid
    return ok
X,Y,A,B,C = map(int,input().split())
p = list(map(int,input().split()))
q = list(map(int,input().split()))
r = list(map(int,input().split()))
p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)
A = p[:X]+q[:Y]
A.sort(reverse=True)
for i in range(len(r)):
    n = r[i]
    if A[-1] < n:
        index = bisect_left_reverse(A,n)
        A.insert(index,n)
        A[-1-i] = 0
    else:
        break
print(sum(A))

### FIXED CODE ###

import bisect
def bisect_left_reverse(a, x):
    if a[0] <= x:
        return 0
    if x < a[-1]:
        return len(a)
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] <= x:
            ok = mid
        else:
            ng = mid
    return ok
X,Y,A,B,C = map(int,input().split())
p = list(map(int,input().split()))
q = list(map(int,input().split()))
r = list(map(int,input().split()))
p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)
A = p[:X]+q[:Y]
B = []
A.sort(reverse=True)
for i in range(len(r)):
    n = r[i]
    if A[0] == 0:
      break
    if A[-1] < n:
        index = bisect_left_reverse(A,n)
        A.pop(-1)
        B.append(n)
    else:
        break
print(sum(A)+sum(B))
### BUGGY CODE ###

#from pprint import pprint
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from copy import deepcopy
#from itertools
#import sys 
#sys.setrecursionlimit(N) #N回まで再起を許可する。
 
# = map(int,input().split())
 
# = list(map(int,input().split()))
 
# = [list(map(int,input().split())) for _ in range(XXXX)]
from sys import stdin
input = stdin.readline
 
h,n = map(int,input().split())
 
ab= [list(map(int,input().split())) for _ in range(n)]
 
dp = [[float("inf") for _ in range(h+1)] for _ in range(n+1)]
#dp[i][j]はi番目のものを選んだ時かつダメージ送料がjだったときの最小MP、
 
 
for i in range(1,n+1):
    dp[i][0] = 0
    for j in range(h+1):
        a = ab[i-1][0]
        b = ab[i-1][1]
        dp[i][j] = min(dp[i][j],dp[i-1][j])
        if j+a <= h:
            dp[i][j+a] = min(dp[i][j] + b, dp[i-1][j+a], dp[i][j+a])
        elif j+a > h:
            dp[i][h] = min(dp[i][j] + b, dp[i-1][h], dp[i][h])

 
print(dp[-1][-1])

#print(dp[-1])

### FIXED CODE ###

#from pprint import pprint
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from copy import deepcopy
#from itertools
#import sys 
#sys.setrecursionlimit(N) #N回まで再起を許可する。
 
# = map(int,input().split())
 
# = list(map(int,input().split()))
 
# = [list(map(int,input().split())) for _ in range(XXXX)]
from sys import stdin


def main():
    input = stdin.readline
    
    h,n = map(int,input().split())
    
    ab= [list(map(int,input().split())) for _ in range(n)]
    
    dp = [[float("inf") for _ in range(h+1)] for _ in range(n+1)]
    #dp[i][j]はi番目のものを選んだ時かつダメージ送料がjだったときの最小MP、
    
    
    for i in range(1,n+1):
        dp[i][0] = 0
        for j in range(h+1):
            a = ab[i-1][0]
            b = ab[i-1][1]
            dp[i][j] = min(dp[i][j],dp[i-1][j])
            if j+a <= h:
                dp[i][j+a] = min(dp[i][j] + b, dp[i-1][j+a], dp[i][j+a])
            elif j+a > h:
                dp[i][h] = min(dp[i][j] + b, dp[i-1][h], dp[i][h])

    
    print(dp[-1][-1])

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

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

adj = {}
val = [0 for i in range(N+1)]
ans = [0 for i in range(N+1)]
check = [False for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    if a not in adj:
        adj[a] = []
    if b not in adj:
        adj[b] = []
    adj[a].append(b)
    adj[b].append(a)

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

queue = [(1,0)]

while len(queue):
    q, c = queue.pop()
    check[q]=True
    ans[q] = val[q] + c
    for nq in adj[q]:
        if check[nq] == False:
            queue.append((nq,ans[q]))

print(*ans[1::])

### FIXED CODE ###

from collections import deque

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

adj = {}
val = [0 for i in range(N+1)]
ans = [0 for i in range(N+1)]
check = [False for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    if a not in adj:
        adj[a] = []
    if b not in adj:
        adj[b] = []
    adj[a].append(b)
    adj[b].append(a)

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

queue = deque([(1,0)])

while len(queue):
    q, c = queue.pop()
    check[q]=True
    ans[q] = val[q] + c
    for nq in adj[q]:
        if check[nq] == False:
            queue.append((nq,ans[q]))
print(*ans[1::])
### BUGGY CODE ###

#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！

def main():
    n,m,*a=map(int,open(0).read().split())
    dp=[0]*(n+1)
    dp[0]=1
    mod=10**9+7
#    dp[1]=dp[0]%mod
    for i in range(1,n+1):
        if i in a:
            continue
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
    print(dp[n]%mod)
#    print(dp)
if __name__ == '__main__':
    main()

### FIXED CODE ###

#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！

def main():
    n,m,*a=map(int,open(0).read().split())
    dp=[0]*(n+1)
    a=set(a)
    dp[0]=1
    mod=10**9+7
#    dp[1]=dp[0]%mod
    for i in range(1,n+1):
        if i in a:
            continue
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
    print(dp[n]%mod)
#    print(dp)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import numpy as np

n,a,b = map(int,input().split())
h = [int(input()) for _ in range(n)]
h = np.array(h)

gap = a-b
count = 0

while True:
    if np.count_nonzero(h<=0) == n:
        break
    h -= b
    h[np.argmax(h)] -= gap
    count += 1

print(count)

### FIXED CODE ###

import numpy as np

n,a,b = map(int,input().split())
h = [int(input()) for _ in range(n)]
h = np.array(h)

hi = 10**10
low = -1

def calc(x):
    y = h-x*b
    y[y<0] = 0
    f = np.ceil(y/(a-b)).sum()
    return f

while hi-low > 1:
    ave = (hi+low)//2
    if calc(ave) <= ave:
        hi = ave
    else:
        low = ave
    
print(hi)
### BUGGY CODE ###

N,M = map(int, input().split())
A = sorted(list(map(int, input().split())),reverse=True)
value = sum(A)

for i in range(M):
    value = value-max(A)+max(A)//2
    for j in range(N):
        if A[j] == max(A):
            A[j] //= 2
            break

print(value)

### FIXED CODE ###

import heapq
N, M = [int(_) for _ in input().split()]
A = [-int(_) for _ in input().split()]

heapq.heapify(A)

for _ in range(M):
    a = heapq.heappop(A)
    heapq.heappush(A, -(-a//2))

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

def main():
    N = int(input())
    ans = 1
    mod = 10**9 + 7
    for i in range(1, N + 1):
        ans *= i
    print(ans % mod)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import math


def main():
    N = int(input())
    ans = math.factorial(N)
    mod = 10**9 + 7
    print(ans % mod)


if __name__ == "__main__":
    main()