Harryxun/stf_run huggingface dataset:
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, M, D = list(map(int, sys.stdin.readline().split()))


# 数列の 1 つ目の要素が決まれば数も決まりそう
# 差が D となる数が上にだけある・下にだけある・上にも下にもある・どっちにもない
# 1 <= a <= N-D までは上にある
# D < a <= N までは下にある

def solve(n, m, d):
    arr = list(itertools.product(range(n), repeat=m))
    ans = 0
    for a in arr:
        for i in range(m - 1):
            if abs(a[i] - a[i + 1]) == d:
                ans += 1
    return ans


# 隣り合う要素を 2 つ決めたときに差が D となる組み合わせの数
if D == 0:
    c = N
else:
    c = (N - D) * 2

# 全部の合計
# pow(N, M - 2): ある 2 つの要素を決めたときにその位置にそれらを使う数列の数
s = c * pow(N, M - 2) * (M - 1)
# 個々の美しさがわからなくても合計がわかれば組み合わせ数で割れば平均になる
ans = s / pow(N, M)
print(ans)


### FIXED CODE ###

import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, M, D = list(map(int, sys.stdin.readline().split()))


# 数列の 1 つ目の要素が決まれば数も決まりそう
# 差が D となる数が上にだけある・下にだけある・上にも下にもある・どっちにもない
# 1 <= a <= N-D までは上にある
# D < a <= N までは下にある

def solve(n, m, d):
    arr = list(itertools.product(range(n), repeat=m))
    ans = 0
    for a in arr:
        for i in range(m - 1):
            if abs(a[i] - a[i + 1]) == d:
                ans += 1
    return ans


# 隣り合う要素を 2 つ決めたときに差が D となる組み合わせの数
if D == 0:
    c = N
else:
    c = (N - D) * 2

# # 全部の合計
# # pow(N, M - 2): ある 2 つの要素を決めたときにその位置にそれらを使う数列の数
# s = c * pow(N, M - 2) * (M - 1)
# # 個々の美しさがわからなくても合計がわかれば組み合わせ数で割れば平均になる
# ans = s / pow(N, M)

# ans = c * (M - 1) * pow(N, M - 2) / pow(N, M)
ans = c * (M - 1) / N ** 2
print(ans)
nmq=list(map(int, input().split()))
N=nmq[0]
M=nmq[1]
Q=nmq[2]
ablist=[list(map(int, input().split())) for i in range(Q)]
sumlist=[]
alist=[i for i in range(1,M+1)]
import itertools as ite
case=list(ite.combinations_with_replacement(alist,N))
for nowcase in case:
    sumd=0
    for i in range(Q):
        a=ablist[i][0]
        b=ablist[i][1]
        c=ablist[i][2]
        d=ablist[i][3]
        aa=nowcase[a-1]
        ab=nowcase[b-1]
        if ab-aa==c:
            sumd+=d
    sumlist.append(sumd)
sumlist.sort(reverse=True)
print(sumlist[0])


### FIXED CODE ###

K=int(input())
ab=list(map(int, input().split()))
A=ab[0]
B=ab[1]
flg=False
for i in range(A,B+1):
    if i%K==0:
        flg=True
if flg:
    print('OK')
else:
    print('NG')
def main():
    a, b = map(int, input().split())
    if a-2 < 0:
        a = 14

    if b-2 < 0:
        b = 14i

    if a-2 > b-2:
        print('Alice')
    elif a-2 < b-2:
        print('Bob')
    else:
        print('Draw')


if __name__ == "__main__":
    main()



### FIXED CODE ###


def main():
    a, b = map(int, input().split())
    if a-2 < 0:
        a = 14

    if b-2 < 0:
        b = 14

    if a-2 > b-2:
        print('Alice')
    elif a-2 < b-2:
        print('Bob')
    else:
        print('Draw')


if __name__ == "__main__":
    main()
import sys
import itertools

input = sys.stdin.readline

def main():
    l, r = [int(i) for i in input().split()] 

    mod = 0
    mod_min = 2019

    for i, j in itertools.combinations(range(l, r+1), 2):
        mod = (i*j % 2019)
        if mod == 0:
            print(mod)
            exit()
        elif mod < mod_min:
            mod_min = mod
            
    print(mod_min)

# main関数呼び出し
if __name__ == "__main__":
    main() 

### FIXED CODE ###

import sys
import itertools

input = sys.stdin.readline

def func(l, r):
    mod_min = float('inf')

    for i in range(l, r):
        for j in range(i+1, r+1):
            mod = (i*j % 2019)

            if mod == 0:
                print(mod)
                exit()     

            elif mod < mod_min:
                mod_min = mod

    print(mod_min)

def main():
    l, r = [int(i) for i in input().split()] 
    func(l, r)
    
# main関数呼び出し
if __name__ == "__main__":
    main()
h, w = map(int, input().split())
a = []
for _ in range(h):
    _a = list(input())
    if '#' in _a:
        a += [_a]
    else:
        pass

import numpy as np

a = np.array(a)
ans_col = []

for i in range(w):
    if '#' in a[:,i]:
        ans_col += [i]
    else:
        pass

ans = a[:, ans_col]

for j in range(a.shape[0]):
    print(''.join(map(str, ans[j, :])))


### FIXED CODE ###

h, w = map(int, input().split())
a = []
for _ in range(h):
    _a = list(input())
    if '#' in _a:
        a += [_a]
    else:
        pass

import numpy as np

a = np.array(a)
ans_col = []

for i in range(w):
    if '#' in a[:,i]:
        ans_col += [i]
    else:
        pass

ans = a[:, ans_col]

for j in range(a.shape[0]):
    print(''.join(map(str, ans[j, :])))
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)


def solve(X: int):
    a = 0
    b = 0
    while True:
        tmp = X + b ** 5
        t = int(tmp ** (1 / 5))
        if t ** 5 == tmp:
            a = t
            print(a, b)
            break
        tmp = X + (-b) ** 5
        t = int(tmp ** (1 / 5))
        if t ** 5 == tmp:
            a = t
            print(a, -b)
            break
        b += 1
    return

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

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)


def solve(X: int):
    a = 0
    b = 0
    while True:
        for x in [1, -1]:
            tmp = X + (x * b) ** 5
            if tmp < 0:
                continue
            t = int(tmp ** (1 / 5))
            if t ** 5 == tmp:
                print(t, x * b)
                return
        b += 1
    return

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

if __name__ == '__main__':
    main()
x=map(int, input().split())
x.sort()
print(x[0],x[1],x[2])

### FIXED CODE ###

x=list(map(int, input().split()))
x.sort()
print(x[0],x[1],x[2])
def hoge(n, cnt=0):
    if n == 0:
        return cnt
    else:
        return hoge(int(n/2), 2 * cnt + 1)
      
def one_int():
    return int(input())
  
  
print(hoge(one_int()))

### FIXED CODE ###

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

N,M = two_int()

temp = N/M

if temp.is_integer():
    print(int(temp))
else:
    print(int(temp)+1)
w, h, x, y = map(int, input().split())

judge = (w == 2 * x and h == 2 * y)
s = w * h / 2
print(area, 1 if judge else 0)


### FIXED CODE ###

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

s = w * h / 2
if w == 2 * x and h == 2 * y:
    print(s, 1)
else:
    print(s, 0)
a=[]
while 1:
 n=input()
 if n=='0 0':break
 a.append(n)
for s in a:
 print(*sorted(map(int,a.split())))

### FIXED CODE ###

import sys
for s in sys.stdin:
 if'0 0\n'==s:break
 print(*sorted(map(int,s.split())))
# ALC 005 D

N = int(input())
list_p = list(map(int, input().split()))
swapCount = 0

for i in range(N):
    if list_p[i] == i+1:
        temp = list_p[i]
        list_p[i] = list_p[i+1]
        list_p[i+1] = temp
        swapCount += 1

print(swapCount)

### FIXED CODE ###

# ALC 005 D

N = int(input())
list_p = list(map(int, input().split()))
swapCount = 0

for i in range(N):
    if list_p[i] == i+1:
        temp = list_p[i]
        
        if i == len(list_p)-1:
            list_p[i] = list_p[i-1]
            list_p[i-1] = temp
        else:
            list_p[i] = list_p[i+1]
            list_p[i+1] = temp
        
        swapCount += 1

print(swapCount)
N,L=map(int,input().split())
s=[]
for i in range(1,N+1):
  s.append(L+i-1)
t=s.remove(min(abs(s)))
print(sum(t))

### FIXED CODE ###

N,L=map(int,input().split())
s=[]
for i in range(1,N+1):
  s.append(L+i-1)
s.sort(key=lambda x: abs(x))
del s[0]
print(sum(s))
import itertools
from collections import Counter
from collections import defaultdict

d = defaultdict(lambda:-1)
N = int(input())
X = [0]*N
Y = [0]*N
for i in range(N):
    X[i],Y[i] = map(int,input().split())
    d[(X[i],Y[i])] = i

o = []
for i,j in itertools.product(range(N),range(N)):
    if i == j:
        continue
    x = X[i] - X[j]
    y = Y[i] - Y[j]
    o.append((x,y))

p,q = Counter(o).most_common()[0][0]
o = []
for i in range(N):
    a = i
    while True:
        b = d[(X[a]+p,Y[a]+q)]
        if b == -1:
            o.append(a)
            break
        a = b

print(len(set(o)))

### FIXED CODE ###

import itertools
from collections import Counter
from collections import defaultdict

d = defaultdict(lambda:-1)
N = int(input())
X = [0]*N
Y = [0]*N
for i in range(N):
    X[i],Y[i] = map(int,input().split())
    d[(X[i],Y[i])] = i

if N == 1:
    print(1)
    exit()

o = []
for i,j in itertools.product(range(N),range(N)):
    if i == j:
        continue
    x = X[i] - X[j]
    y = Y[i] - Y[j]
    o.append((x,y))

p,q = Counter(o).most_common()[0][0]
o = []
for i in range(N):
    a = i
    while True:
        b = d[(X[a]+p,Y[a]+q)]
        if b == -1:
            o.append(a)
            break
        a = b

print(len(set(o)))
import sympy
a,b,c=map(int,input().split())
if a+b+sympy.sqrt(4*a*b)<c:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

from decimal import *
import math
a,b,c=map(int,input().split())
if a+b+(4*Decimal(a)*Decimal(b))**Decimal("0.5")<c:
    print("Yes")
else:
    print("No")
W, H, x, y = map(int, input().split())

if (W==0)or(H==0):
    print(float(0))
    print(1)
else:
    if ((y*W-x*H)/W==float(0))or((y*W+x*H)/W==float(H)):
        print(H*W/2)
        print(1)
    else:
        print(H*W/2)
        print(0)

### FIXED CODE ###

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

if X<A:
    print(0)
else:
    print(10)
n=int(input())
ans=""
for i in range(1, n+1)
  if i%3==0 or i%10==3:
    ans += str(i)
print(ans)


### FIXED CODE ###

n=int(input())
d=[]
for i in range(1,n+1):
    if i%3==0 or "3" in str(i):
        d.append(i)
print(" ",end="")
print(*d)
import math

while True
 a,b=map(int,input().split())
 print(math.gcd(a,b),a*b//math.gcd(a,b))
 print()

### FIXED CODE ###

def gcd(x,y):
    while y:
        x, y = y, x % y
    return x


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


while True:
    try:
        a = list(map(int,input().split()))
        print(gcd(a[0],a[1]),lcm(a[0],a[1]))
    except:
        break
MOD = 10**9+7
N, K = map(int, input().split())
*A, = map(int, input().split())

allm = True
for a in A:
    if a > 0:
        allm = False
        break

if N == K:
    ans = 1
    for a in A:
        ans = (ans*a) % MOD
    print(ans)
elif allm and K % 2 == 1:
    A.sort()
    A.reverse()
    ans = 1
    for a in A[:K]:
        ans = (ans*a) % MOD
    print(ans)
else:
    p, m = [], []
    for a in A:
        if a > 0:
            p.append(a)
        if a < 0:
            m.append(-a)
    p.sort(key=lambda k: -k)
    m.sort(key=lambda k: -k)

    pi, mi = 0, 0
    ans = 1
    while K > 0:
        if K == 1:
            ans = (ans*p[pi]) % MOD
            break
        elif pi < len(p)-1 or mi < len(m)-1:
            pv, mv = 0, 0
            if pi < len(p)-1:
                pv = p[pi]*p[pi+1]
            if mv < len(m)-1:
                mv = m[mi]*m[mi+1]
            print(pv, mv)
            if pv > mv:
                ans = (ans*pv) % MOD
                pi += 2
            else:
                ans = (ans*mv) % MOD
                mi += 2
            K -= 2
        else:
            ans = 0
            break
    print(ans)


### FIXED CODE ###

MOD = 10**9+7
N, K = map(int, input().split())
*A, = map(int, input().split())

allm = True
for a in A:
    if a > 0:
        allm = False
        break

if N == K:
    ans = 1
    for a in A:
        ans = (ans*a) % MOD
    print(ans)
elif allm and K % 2 == 1:
    A.sort()
    A.reverse()
    ans = 1
    for a in A[:K]:
        ans = (ans*a) % MOD
    print(ans)
else:
    p, m = [], []
    for a in A:
        if a > 0:
            p.append(a)
        if a < 0:
            m.append(-a)
    p.sort(key=lambda k: -k)
    m.sort(key=lambda k: -k)

    pi, mi = 0, 0
    ans = 1
    while K > 0:
        if K == 1:
            ans = (ans*p[pi]) % MOD
            break
        elif pi < len(p)-1 or mi < len(m)-1:
            pv, mv = 0, 0
            if pi < len(p)-1:
                pv = p[pi]*p[pi+1]
            if mi < len(m)-1:
                mv = m[mi]*m[mi+1]

            if pv > mv:
                ans = (ans*pv) % MOD
                pi += 2
            else:
                ans = (ans*mv) % MOD
                mi += 2
            K -= 2
        else:
            ans = 0
            break
    print(ans)
stuck = ""
while True:
    a = raw_input().split()
    if a == "quit":
        break
    if a[0] == "push":
        stuck += a[1]
    elif a[0] == "pop":
        l = len(stuck) - 1
        print stuck[l]
        stuck = stuck[:l]

### FIXED CODE ###

stuck = ""
while True:
    a = raw_input().split()
    if a[0] == "quit":
        break
    if a[0] == "push":
        stuck += a[1]
    elif a[0] == "pop":
        l = len(stuck) - 1
        print stuck[l]
        stuck = stuck[:l]
a,b,c = map(int,input())

if a==c:
  print(b)
elif a==b:
  print(c)
else:
  print(a)

### FIXED CODE ###

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

if a==c:
  print(b)
elif a==b:
  print(c)
else:
  print(a)
a = list(map(int, input().split()))

print(min(a[0]+ a[1], a[1] + a[2], a[2]+ a[0])

### FIXED CODE ###

a = list(map(int, input().split()))
 
print(min(a[0]+ a[1], a[1] + a[2], a[2]+ a[0]))
#coding utf-8
N,M=map(int,input().split())
A=list(map(int,input().split())) 
BC=[[int(i) for i in input().split()] for i in range(M)]
A.sort()
BC.sort(key=lambda x:x[1])
BC.reverse()

k=0
t=0
for i in range(M):
  if t==1:
    break
  for j in range(BC[i][0]):
    if BC[i][1]>A[k]:
      A[k]=BC[i][1]
      k+=1
    else:
      t=1
      break
      
      
print(sum(A))    

### FIXED CODE ###

#coding utf-8
N,M=map(int,input().split())
A=list(map(int,input().split())) 
BC=[[int(i) for i in input().split()] for i in range(M)]
A.sort()
BC.sort(key=lambda x:x[1])
BC.reverse()

k=0
t=0
for i in range(M):
  if t==1 or k==N:
    break
  for j in range(BC[i][0]):
    if BC[i][1]>A[k]:
      A[k]=BC[i][1]
      k+=1
      if k==N:
        break
    else:
      t=1
      break
      
      
print(sum(A))
n = int(input())
lists = list(map(int, input().split()))

sets = set(lists)
ans = len(sets)

print(ans)

### FIXED CODE ###

n = int(input())
lists = input().split()

sets = set(lists)
if len(sets) == 3:
    ans = 'Three'
else:
    ans = 'Four'

print(ans)
s=input()
if s=="ABC":
  print("ARC")
else:
  print("ABC)

### FIXED CODE ###

s=input()
if s=="ABC":
    print("ARC")
else:
    print("ABC")
import math


def lcm(x, y):
    aaa = (x * y) // math.gcd(x, y)
    return aaa


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

AtoB = (B - (A - 1))

divisible_C = (B // C) - ((A - 1) // C)
divisible_D = (B // D) - ((A - 1) // D)

minLcm = lcm(C, D)

divisible_CD = (B // minLcm) - ((A - 1) // minLcm)

divisible_CtoD = (divisible_C + divisible_D) - divisible_CD

answer = AtoB - divisible_CtoD

print(answer)

### FIXED CODE ###

import fractions


def lcm(x, y):
    aaa = (x * y) // fractions.gcd(x, y)
    return aaa


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

AtoB = (B - (A - 1))

divisible_C = (B // C) - ((A - 1) // C)
divisible_D = (B // D) - ((A - 1) // D)

minLcm = lcm(C, D)

divisible_CD = (B // minLcm) - ((A - 1) // minLcm)

divisible_CtoD = (divisible_C + divisible_D) - divisible_CD

answer = AtoB - divisible_CtoD

print(answer)
a, b = map(int, input().split())
if int("a"*b) >= int("b"*a):
  print(int("b"*a)
else:
  print(int("a"*b)

### FIXED CODE ###

a, b = map(int, input().split())
ans = min(str(a) * b, str(b) * a)
print(ans)
n = input()
hon = [2,4,5,7,9]
pon = [0,1,6,8]
bon = [3]

if int(n[-1]) in hon:
    print('hon')
elif int(n[:-1]) in pon:
    print('pon')
else:
    print('bon')

### FIXED CODE ###

n = input()
hon = [2,4,5,7,9]
pon = [0,1,6,8]
bon = [3]

if int(n[-1]) in hon:
    print('hon')
elif int(n[-1]) in pon:
    print('pon')
else:
    print('bon')
def pickup(S,ans):
    l = len(S)
    if l<2:
        return ans
    for i in range(l-1):
        if S[i] != S[i+1]:
            S.pop(i)
            S.pop(i)
            ans += pickup(S,ans)
            return ans+2
S=input()
l = len(S)
S_list = [S[i] for i in range(l)]
ans =0
print(pickup(S_list,ans))

### FIXED CODE ###

S=input()
num_one=S.count('1')
num_zero=S.count('0')
ans = 2*min(num_one,num_zero)
print(ans)
""" small multiple """

K = int(input())

def get_sum_each_digits(number):
    """
    get sum.
    """
    chars = list(str(number))
    int_map = map(int, chars)
    result = sum(int_map)
    # print("number:{0}, result:{1}".format(number, result))
    return result

def main():
    """
    main function.
    """

    min = K
    multiple = 0
    while multiple < 100000:
        multiple += 1
        temp = get_sum_each_digits(K * multiple)
        if temp < min:
            min = temp
        if min == 1:
            break

    # print("ans ---")
    print(min)

main()

### FIXED CODE ###

c11, c12, c13 = list(input())
c21, c22, c23 = list(input())
result = c11 == c23 and \
    c12 == c22 and \
    c13 == c21

ans = "YES" if result else "NO"
print(ans)
import math
L = [int(input()) for _ in range(5)]
Lm = 10-min([i%10 for i in L if i%10 != 0])
print(sum([10*math.ceil(i/10) for i in L])-Lm)




### FIXED CODE ###

import math
L = [int(input()) for _ in range(5)]
Lm = []
for i in L:
    if i%10 == 0:
        Lm.append(0)
    else:
        Lm.append(10-i%10)
print(sum([10*math.ceil(i/10) for i in L])-max(Lm))
import math

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

answer = 0

if (x / a**2) <= (b/2):
  n = (2*x) / (a*b)
  answer = math.degrees(math.atan(b/n))
elif a == 1 and b == 1 and x == 1:
  answer = 0
else:
  n = ((2*x) / a**2) - b
  answer = 90 - math.degrees(math.atan(a / (b-n) ))

print(answer)

### FIXED CODE ###

import math

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

answer = 0

if (x / a**2) <= (b/2):
  n = (2*x) / (a*b)
  answer = math.degrees(math.atan(b/n))
elif (a**2 * b) == x:
  answer = 0
else:
  n = ((2*x) / a**2) - b
  answer = 90 - math.degrees(math.atan(a / (b-n) ))

print(answer)
a,b=map(int,input().split())
s=input()
ans="Yes"
if s.count("-")!=1:
    ans="No"
else:front,back=s.split("-")
if len(front)!=a or len(back)!=b:
    ans="No"
print(ans)

### FIXED CODE ###

a,b=map(int,input().split())
s=input()
ans="Yes"
front=""
back=""
if s.count("-")!=1:
    ans="No"
else:front,back=s.split("-")
if len(front)!=a or len(back)!=b:
    ans="No"
print(ans)
n,m = map(int,input().split())
sc = []
for _ in range(m):
    sc.append(list(map(int,input().split())))
ans = -1
flag = False
if n == 1:
    tmp = sc[0][1]
    for x in sc:
        s = x[0]
        c = x[1]
        if tmp != c:
            break
        ans = tmp
elif n == 2:
    tmp = [-1,-1]
    for x in sc:
        s = x[0]
        c = x[1]
        if tmp[s-1] != c and tmp[s-1] != -1:
            flag = True
            break
        if s == 1 and c == 0:
            flag = True
            break
        tmp[s-1] = c
    if tmp[0]==-1:
        tmp[0] = 1
    if tmp[1]==-1:
        tmp[1] = 0
    if not flag:
        ans = tmp[0]*10+tmp[1]
else:
    tmp = [-1,-1,-1]
    for x in sc:
        s = x[0]
        c = x[1]
        if tmp[s-1] != c and tmp[s-1] != -1:
            flag = True
            break
        if s == 1 and c == 0:
            flag = True
            break
        tmp[s-1] = c
    if tmp[0]==-1:
        tmp[0] = 1
    if tmp[1]==-1:
        tmp[1] = 0
    if tmp[2]==-1:
        tmp[2] = 0
    if not flag:
        ans = tmp[0]*100+tmp[1]*10+tmp[2]
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
sc = []
for _ in range(m):
    sc.append(list(map(int,input().split())))
tmp = [-1,-1,-1]
flag = False
for b in sc:
    s = b[0]
    c = b[1]
    if n >1 and s == 1 and c == 0:
        flag = True
        break
    if tmp[s-1] != -1 and tmp[s-1] != c:
        flag = True
        break
    tmp[s-1] = c
ans = 0

if not flag:
    for i in range(n):
        if tmp[i] == -1:
            if n == 1:
                tmp[i] = 0
            elif i == 0:
                tmp[i]=1
            else:
                tmp[i]=0
    for i in range(n):
        m = 10**(n-1-i)
        ans = ans + tmp[i]*m
else:
    ans = -1
print(ans)
def fib(n):
    a, b = 1, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
ans = fib(a[0])
if m != 0:
  for j in range(1,m):
    if m == 1:
        continue
    elif a[j] == a[j-1]+1:
        ans = 0
    else:
        ans *= fib(a[j]-a[j-1]-1)
  ans *= fib(n-a[m-1])
else:
  ans = fib(n+1)
print(ans%1000000007)


### FIXED CODE ###

def fib(n):
    a, b = 1, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

n,m = map(int,input().split())
if m != 0:
  a = [int(input()) for i in range(m)]
  ans = fib(a[0])
  for j in range(1,m):
    if m == 1:
        continue
    elif a[j] == a[j-1]+1:
        ans = 0
    else:
        ans *= fib(a[j]-a[j-1]-1)
  ans *= fib(n-a[m-1])
else:
  ans = fib(n+1)
print(ans%1000000007)
N = int(input())
a = list(map(int,input()))
x = 0
for i in range(N):
    x ^=  a[i]
if x:
    print('No')
else:
    print('Yes')

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
if N % 3 != 0:
    if any(a):
        print('No')
    else:
        print('Yes')
else:
    a.sort()
    a1 = set(a[:N//3])
    a2 = set(a[N//3:2*N//3])
    a3 = set(a[2*N//3:])
    if len(a1) == 1 and len(a2) == 1 and len(a3) == 1:
        if a1.pop()^a2.pop()^a3.pop() == 0:
            print('Yes')
        else:
            print('No')
    else:
        print('No')
import sys

def h1(key):
    return key % M

def h2(key):
    return 1 + key % (M - 1)

def H(key, i):
    return (h1(key) + i * h2(key)) % M

def my_insert(dic, key):
    i = 0

    while 1:
        j = H(key, i)
        if dic[j] is None:
            dic[j] = key
            return j
        else:
            i += 1

def my_search(dic, key):
    i = 0

    while 1:
        j = H(key, i)
        if dic[j] == key:
            return True
        elif dic[j] is None or i >= M:
            return False
        else:
            i += 1

def str2int(s):
    res = s

    res = res.replace("A", "1")
    res = res.replace("C", "2")
    res = res.replace("G", "3")
    res = res.replace("T", "4")

    return int(res)

M = 1_000_003
dic = [None] * M

n = int(sys.stdin.readline())

for k in range(n):
    cmd, s = sys.stdin.readline().split()

    if cmd == "insert":
        my_insert(dic, str2int(s))
    else:
        print("yes" if my_search(dic, str2int(s)) else "no")

### FIXED CODE ###

import sys

def h1(key):
    return key % M

def h2(key):
    return 1 + key % (M - 1)

def H(key, i):
    return (h1(key) + i * h2(key)) % M

def my_insert(dic, key):
    i = 0

    while 1:
        j = H(key, i)
        if dic[j] is None:
            dic[j] = key
            return j
        else:
            i += 1

def my_search(dic, key):
    i = 0

    while 1:
        j = H(key, i)
        if dic[j] == key:
            return True
        elif dic[j] is None or i >= M:
            return False
        else:
            i += 1

def str2int(s):
    res = s

    res = res.replace("A", "1")
    res = res.replace("C", "2")
    res = res.replace("G", "3")
    res = res.replace("T", "4")

    return int(res)

M = 1000003
dic = [None] * M

n = int(sys.stdin.readline())

for k in range(n):
    cmd, s = sys.stdin.readline().split()

    if cmd == "insert":
        my_insert(dic, str2int(s))
    else:
        print("yes" if my_search(dic, str2int(s)) else "no")