Harryxun/stf_run huggingface dataset:
class int(int):  
  def times(self, callback):
    for times in range(0,self):
      callback()

class list(list):
  def maps(self, callback):
    return list(map(callback, self))

  def each(self, callback):
    list(map(callback, self))
    return self

  # index will sent to the function as a second parameter.
  def each_with_index(self,callback):
    list(map(callback, self, range(0,len(self))))
    return self

# Make sure you initialize object with class name.
# Ex: int(10).times, array = list([1,2,3,4,5])

target, length = input().split()
target = int(target)
length = int(length)
nums = list(input().split())

def convert(arg):
    return int(arg)
nums = nums.maps(convert)

for i in range(0,101):
  # Xの両隣がpに存在しないかみていく（pに存在しない値をみつけたいので）
  a = target - i # まずは左隣をみていく(Xよりi小さい)
  if a not in num:
    print(a)
    exit()

  b = target + i # 次に右隣をみていく(Xより大きい)
  if b not in nums:
    print(b)
    exit()
  
# 配列pが与えられなかったとき(長さが0のとき)でも、「Xより0小さい値がpに存在しない」ので、そのままXが返せる

### FIXED CODE ###

class int(int):  
  def times(self, callback):
    for times in range(0,self):
      callback()

class list(list):
  def maps(self, callback):
    return list(map(callback, self))

  def each(self, callback):
    list(map(callback, self))
    return self

  # index will sent to the function as a second parameter.
  def each_with_index(self,callback):
    list(map(callback, self, range(0,len(self))))
    return self

# Make sure you initialize object with class name.
# Ex: int(10).times, array = list([1,2,3,4,5])

target, length = input().split()
target = int(target)
length = int(length)
nums = list(input().split())

def convert(arg):
    return int(arg)
nums = nums.maps(convert)

for i in range(0,101):
  a = target - i
  if a not in nums:
    print(a)
    exit()

  b = target + i
  if b not in nums:
    print(b)
    exit()
if __name__ == '__main__':
    n = int(input())
    c = []
    d = []
    e = []
    
    for i in range(0, n):
        a, b = map(int, input().split())
        c.append(a)
        d.append(b)
        e.append(a + b)
    
    li1, li2 = sorted(e), sorted(range(len(e)), key=lambda k: e[k])
    
    turn = 0
    happy = 0

    for i in range(n - 1, -1, -1):
        now = li1[i]
        if (turn == 0):
            max = 0
            maxKey = 0
            for j in range(i, -1, -1):
                if (now == li1[j] and max < c[li2[j]]):
                    max = c[li2[j]]
                    maxKey = j
                else:
                    li2[i], li2[maxKey] = li2[maxKey], li2[i]
                    break
            happy += c[li2[i]]
        else:

            max = 0
            maxKey = 0
            for j in range(i, -1, -1):
                if (now == li1[j] and max < d[li2[j]]):
                    max = d[li2[j]]
                    maxKey = j
                else:
                    li2[i], li2[maxKey] = li2[maxKey], li2[i]
                    break

            happy -= d[li2[i]]
        turn = (turn + 1) % 2
    print(happy)
    


    
    


### FIXED CODE ###

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

c = 0
d = a + b -n
if (a > b):
    c = b
else:
    c = a

if (d < 0):
    d = 0
    
print(str(c) + " " + str(d))
a, b = map(int, input().split())
count = 1
 
for i in range(20):
    if b > count:
        count += a-1
    else:
        break
if -(-count // a) >= 1:
    print(-(-count // a))
else:
    print(0

### FIXED CODE ###

a, b = map(int, input().split())
print(-(-(b-1) // (a-1)))
a,b,c,d=map(int,input(),split())
ans=b-a+1
ans-=b//c-(a-1)//c
ans-=b//d-(a-1)//d
e=c*d
ans+=b//e-(a-1)//e
print(ans)


### FIXED CODE ###

def gcd(n,m):
    if n<m:
        return gcd(m,n)
    if n%m==0:
        return m
    else:
        return gcd(m,n%m)

a,b,c,d=map(int,input().split())
ans=b-a+1
ans-=b//c-(a-1)//c
ans-=b//d-(a-1)//d
e=c*d//(gcd(c,d))
ans+=b//e-(a-1)//e
print(ans)
def fiv(n):
    return int((((1+(5)**(1/2))/2)** (n + 1) - ((1-(5)**(1/2))/2)** (n + 1))//(5**(1/2)))

n, m = map(int, input().split())
broken = []
for i in range(m):
	broken.extend(map(int, input()))

p = [0] * (m + 1) #broken間の登り方list

for i in range(m + 1):
    if i == 0: #a1 さいしょ
        if broken[0] == 1:
            p[0] = 1
        else:
            p[0] = fiv(broken[0] - 1)
    if i == m: #am さいご
        if broken[m - 1] == n - 1:
            p[m] = 1
        else:
            p[m] = fiv(n - broken[0] - 1)
    
    else:
        if broken[i] - broken[i - 1] - 1 == 0:
            print('0')
            exit()
        else:
            p[i] = fiv(broken[i] - broken[i - 1] - 1)

ans = 1
for i in range(m + 1):
    ans = ans * p[i] 
if ans < 0:
    ans = ans * -1
ans = ans % 1000000007

print(int(ans))

### FIXED CODE ###

n, m = map(int, input().split())
mod = 10 ** 9 + 7
dp = [-1 for i in range(n + 1)]
dp[0], dp[1] = 1, 1
for _ in range(m):
    dp[int(input())] = 0
for i in range(2, n + 1):
    if dp[i] != 0:
        dp[i] = (dp[i - 1] + dp[i - 2]) % mod
print(dp[n])
l, r = (int(x) for x in input().split())
tmpmin = 2020
tmprem = i*r%2019
if l*r<2019:
    print(l*(l+1))
else:
    for i in range(l, r+1):
        for j in range(l+1, r+1):
            tmp = (i*j)%2019
            tmpnxt = (i*(j+1))%2019
            if tmp < tmpmin:
                tmpmin = tmp
            if tmp < tmpnxt:
                break
    print(tmpmin)

### FIXED CODE ###

l, r = (int(x) for x in input().split())
tmpmin = 2019
if r-l >= 2019:
    print(0)
else:
    for i in range(l, r):
        for j in range(l+1, r+1):
            tmp = (i*j)%2019
            if tmp < tmpmin:
                tmpmin = tmp
                if tmpmin == 0:
                    break
    print(tmpmin)
import sys
sys.setrecursionlimit(300000)
def solve(x,y,k):
    if x==y==0: return []
    if x<0: return [(-x,y) for x,y in solve(-x,y,k)]
    if y<0: return [(x,-y) for x,y in solve(x,-y,k)]
    if x>y: return [(x,y) for y,x in solve(y,x,k)]
    if (x+y)%k==0: return [(k,0)]*(x//k)+[(0,k)]*(y//k)+([]if x%k==y%k==0 else[(x%k,y%k)])
    if x+y>=2*k: return ([(k,0)]*(x//k)+[(0,k)]*(y//k))[:-1]+solve(x%k,y%k+k,k)
    if x+y<K and (x+y)%2==1: return solve(x,y+k,k)+[(0,-k)]
    if K&1 and x+y>k and (x+y)%k%2==0: return solve(x,y-k,k)+[(0,k)]
    z=(x+y)//2
    return [(k-z+x,z-x),(z-k,z)]
K,X,Y=map(int, open(0).read().split())
if K%2==0 and (X+Y)%2==1:
    print(-1)
else:
    ans=solve(X,Y,K)
    print(len(ans))
    ax,ay=0,0
    for x,y in ans:
        ax+=x
        ay+=y
        print(ax,ay)

### FIXED CODE ###

import sys
sys.setrecursionlimit(300000)
def solve(x,y,k):
    if x==y==0: return []
    if x<0: return [(-x,y) for x,y in solve(-x,y,k)]
    if y<0: return [(x,-y) for x,y in solve(x,-y,k)]
    if x>y: return [(x,y) for y,x in solve(y,x,k)]
    if (x+y)%k==0: return [(k,0)]*(x//k)+[(0,k)]*(y//k)+([]if x%k==y%k==0 else[(x%k,y%k)])
    if x+y>=2*k:
        if x%k+y%k>=k: return [(k,0)]*(x//k)+[(0,k)]*(y//k)+solve(x%k,y%k,k)
        else: return ([(k,0)]*(x//k)+[(0,k)]*(y//k))[:-1]+solve(x%k,y%k+k,k)
    if x+y<K and (x+y)%2==1: return solve(x,y+k,k)+[(0,-k)]
    if K&1 and x+y>k and (x+y)%k%2==0: return solve(x,y-k,k)+[(0,k)]
    z=(x+y)//2
    return [(k-z+x,z-x),(z-k,z)]
K,X,Y=map(int, open(0).read().split())
if K%2==0 and (X+Y)%2==1:
    print(-1)
else:
    ans=solve(X,Y,K)
    print(len(ans))
    ax,ay=0,0
    for x,y in ans:
        ax+=x
        ay+=y
        print(ax,ay)
import itertools
import bisect
N,x = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
cumsum = list(itertools.accumulate(A))
ans = bisect.bisect_right(cumsum,x)

if ans == N:
  rest = cumsum[N] - x
  if rest != 0:
    ans -= 1

print(ans)


### FIXED CODE ###

import itertools
import bisect
N,x = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
cumsum = list(itertools.accumulate(A))
ans = bisect.bisect_right(cumsum,x)

if ans == N:
  rest = cumsum[-1] - x
  if rest != 0:
    ans -= 1

print(ans)
i = 1
n = int(input())
while i <= n:
	if i % 3 == 0:
		print(i , end = ' ')
	elif i % 10 == 3:
		print(i , end = ' ')
	i = i + 1

### FIXED CODE ###

i = 1
n = int(input())
while i <= n:
	x = i
	if x % 3 == 0:
		print('' , i , end = '')
	else:
		while x:
	 		if x % 10 == 3:
	 			print('' , i , end = '')
	 			break
	 		x = int(x / 10)
	i = i + 1
print('')
a,b,c=map(int, input().split())
if (a*b)%2==0:
  print('Even')
esle:
  print('0dd')

### FIXED CODE ###

a,b=map(int,input().split())
if (a*b)%2==0:
  print("Even")
else:
  print("Odd")
n, q = map(int, input().split())
ab = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
p, x = [], []
px = dict()
for _ in range(q):
    pp, xx = map(int, input().split())
    p.append(pp-1)
    x.append(xx)
    px[pp-1] = xx


def dfs(now):
    for i in ab[now]:
        if d[i] == -1:
            d[i] = d[now]+1
            dfs(i)


d = [-1]*n
d[0] = 0
dfs(0)
ans = [0]*n
for i in range(len(p)):
    for j in range(n):
        if d[j] >= d[p[i]]:
            ans[j] += x[i]

print(*ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)

n, q = map(int, input().split())
ab = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
add = [0]*n
for _ in range(q):
    pp, xx = map(int, input().split())
    add[pp-1] += xx


def dfs(v, p, value):
    value += add[v]
    ans[v] = value
    for c in ab[v]:
        if c == p:
            continue
        dfs(c, v, value)


ans = [0]*n
dfs(0, -1, 0)
print(*ans)
N = int(input())
A = []
B = []
for i in range(N):
    a, b = map(int,input().split())
    A.append(a)
    B.append(b)

A.sort()
B.sort()
print(A)
print(B)
if N % 2 == 1:
    AA = A[(N+1)//2]
    BB = B[(N+1)//2-1] 
    print(BB-AA+1)
else:
    AA = (A[N//2]+A[N//2+1])/2
    BB = (B[N//2-1]+B[N//2+1-1])/2
    print(BB-AA+1)

### FIXED CODE ###

N = int(input())
A = []
B = []
for i in range(N):
    a, b = map(int,input().split())
    A.append(a)
    B.append(b)

A.sort()
B.sort()
#print(A)
#print(B)
if N % 2 == 1:
    AA = A[(N+1)//2-1]
    BB = B[(N+1)//2-1] 
    print(BB-AA+1)
else:
    AA = (A[N//2-1]+A[N//2])/2
    BB = (B[N//2-1]+B[N//2])/2
    print(int((BB-AA)*2+1))
# -*- coding: utf-8 -*-
a, b = map(iint, input().split())

x = a+b
if x%2 == 1:
  print('IMPOSSIBLE')
else:
  print('{}',x//2)

### FIXED CODE ###

# -*- coding: utf-8 -*-
a, b = map(int, input().split())
 
x = a+b
if x%2 == 1:
  print('IMPOSSIBLE')
else:
  print('{}'.format(x//2))
x,a=(int(i) for i in input().split())
print((if(x>=a))*10)

### FIXED CODE ###

x,a=(int(i) for i in input().split())
if x>=a:
  print(10)
else:
  print(0)
def main():
    s = list(input())
    now = 0
    for i in range(len(s)):
        if s[i] == '?':
            if i == 0 or s[i-1] == 'P' or s[i-1] == '?':
                s[i] = 'D'
                continue
            if i != len(s) -1 or s[i+1] == 'D' or s[i+1] == '?':
                s[i] ='P'
                continue
    print(''.join(s))

if __name__=='__main__':
    main()


### FIXED CODE ###

def main():
    s = list(input())
    now = 0
    for i in range(len(s)):
        if s[i] == '?':
            if i == 0 or s[i-1] == 'P' or s[i-1] == '?':
                s[i] = 'D'
                continue
            if i+1 < len(s)  and( s[i+1] == 'D' or s[i+1] == '?'):
                s[i] ='P'
                continue
            s[i] = 'D'
    print(''.join(s))

if __name__=='__main__':
    main()
n=int(input())
a=list(map(int,input().split()))

a.sort()
nn=a[-1]

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
p = 998244353
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
#cmb(n-1, pair, p)

result=0
for i in range(1,len(a)):
    if a[i-1]<nn//2 and a[i]>=nn//2:
        if a[i]==nn:
            print(nn,a[i-1])
            exit()
        if cmb(nn,a[i-1],1)>cmb(nn,a[i],1):
            print(nn,a[i-1])
        else:
            print(nn,a[i])

        exit()
  
  


### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)

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

if n==2:
    print(aa[0],aa[1])
    exit()

aa.sort()

nn=max(aa)

c=0
tmp=10**9

for a in aa:
    if abs(nn/2.0-a)<tmp:
        tmp=abs(nn/2.0-a)
        c=a

print(nn,c)
A,B=map(int,input().split());print(("Possible","Impossible")[min([A%3,B%3,(A+B)%3])]

### FIXED CODE ###

A,B=map(int,input().split());print(("Possible","Impossible")[min([A%3,B%3,(A+B)%3])])
from collections import defaultdict

n, m = [int(i) for i in raw_input().split()]

parents = defaultdict(list)

i = 0
while i < m:
    u, v = [int(x) for x in raw_input().split()]
    parents[v-1].append(u-1)
    i += 1

def calc_f(parents, f, i):
    if f[i] != -1:
        return f[i]

    f[i] = float("-inf")
    for v in parents[i]:
        f[i] = max(f[i], calc_f(parents, f, v)+1)

    return f[i]

f = [-1] * n
j = 0
while j < n:
    calc_f(parents, f, j)
    j += 1

print max(f)

### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)

n, m = [int(i) for i in raw_input().split()]
parents = defaultdict(list)

i = 0
while i < m:
    u, v = [int(x) for x in raw_input().split()]
    parents[v-1].append(u-1)
    i += 1

def calc_f(parents, f, i):
    if i < 0 or i >= len(f):
        return 0

    if f[i] != -1:
        return f[i]

    f[i] = 0
    for v in parents[i]:
        f[i] = max(f[i], calc_f(parents, f, v)+1)

    return f[i]

f = [-1] * n
j = 0
while j < n:
    calc_f(parents, f, j)
    j += 1

if len(f) == 0:
    print 0
else:
    print max(f)
a,b=map(int, input().split())
     
     
if (a + b) % 2 === 0:
    print((a + b) // 2)
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

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

if (a + b) % 2 == 0:
    print((a + b) // 2)
else:
    print("IMPOSSIBLE")
import math

n, M= map(int,input().split())
#AB=[]
#N = int(input())
#C = input()
parents = [-1] * n

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

def union(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return

    if parents[x] > parents[y]:
        x, y = y, x

    parents[x] += parents[y]
    parents[y] = x

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

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

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

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

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

def all_group_members():
    return {r: members(r) for r in roots()}

def __str__():
    return '\n'.join('{}: {}'.format(r, members(r)) for r in roots())
 
C = []
for i in range(M):
    A, B = map(int,input().split())
    union(A,B)
    '''
    c = 0
    for p in C:
        if A in p:
            c = 1
            p.add(B)
        elif B in p:
            c = 1
            p.add(A)
    if c != 1:
        C.append(set([A,B]))
    '''
print(group_count()-1)


### FIXED CODE ###

import math

n, M= map(int,input().split())
#AB=[]
#N = int(input())
#C = input()
parents = [-1] * n

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

def union(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return

    if parents[x] > parents[y]:
        x, y = y, x

    parents[x] += parents[y]
    parents[y] = x

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

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

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

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

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

def all_group_members():
    return {r: members(r) for r in roots()}

def __str__():
    return '\n'.join('{}: {}'.format(r, members(r)) for r in roots())
 
C = []
for i in range(M):
    A, B = map(int,input().split())
    union(A-1,B-1)
    '''
    c = 0
    for p in C:
        if A in p:
            c = 1
            p.add(B)
        elif B in p:
            c = 1
            p.add(A)
    if c != 1:
        C.append(set([A,B]))
    '''
print(group_count()-1)
W , H, x, y、r = map(int, input().split())

if r <= x <= W -r) and (r <= y <= H -r):

    print("Yes")

else:
    print("No")



### FIXED CODE ###

W, H, x, y, r = map(int, input().split())

if r <= x and x <= (W - r):
    if r <= y and y <= (H - r):
        print("Yes")
    else:
        print("No")

else:
    print("No")
k = int(input())
alist =1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51 . split(,)
alist[k-1]


### FIXED CODE ###

k = int(input())
alist = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(alist[k-1])
mod = 10**9+7

def dfs(v,pr,k):
  if len(G[v]) > k:
    return 0
  
  kc = k-2
  if pr == -1:
    kc = k-1  
  
  ret = 1
  
  for vi in G[v]:
    if vi == pr:
      continue
    ret *= kc
    ret %= mod
    kc -= 1
    
  for vi in G[v]:
    if vi == pr:
      continue
    ret *= dfs(vi,v,k)
    ret %= mod
  
  return ret


n,k = map(int,input().split())
G = [[] for i in range(n)]
for i in range(n-1):
  a,b = map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)      
  
print(dfs(0,-1,k) * k % mod )

### FIXED CODE ###

import sys
sys.setrecursionlimit(410000)

mod = 10**9+7

def dfs(v,pr,k):
  if len(G[v]) > k:
    return 0
  
  kc = k-2
  if pr == -1:
    kc = k-1  
  
  ret = 1
  
  for vi in G[v]:
    if vi == pr:
      continue
    ret *= kc
    ret %= mod
    kc -= 1
    
  for vi in G[v]:
    if vi == pr:
      continue
    ret *= dfs(vi,v,k)
    ret %= mod
  
  return ret


n,k = map(int,input().split())
G = [[] for i in range(n)]
for i in range(n-1):
  a,b = map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)      
  
print(dfs(0,-1,k) * k % mod )
N = int(input())
T, A = map( int, input().split())
H = list( map( int, input.split()))
         
K = []
Ksorted=[]
tmp=[]
 
for i in range(N):
  tmp.append( T - H[i] * 0.006)
  K.append(abs( A - tmp[i]))
  Ksorted = sorted(K)
  
T = K.index(Ksorted[0])
print(T+1)


### FIXED CODE ###

N = int(input())
T, A = map( int, input().split())
H = list( map( int, input().split()))
         
K = []
Ksorted=[]
tmp=[]
 
for i in range(N):
  tmp.append( T - H[i] * 0.006)
  K.append(abs( A - tmp[i]))
  Ksorted = sorted(K)
  
T = K.index(Ksorted[0])
print(T+1)
import heapq

H,W = map(int,input().split())
C = [[int(x) for x in input().split()] for _ in range(10)]
num = [0] * 10
for _ in range(H):
    for x in input().split():
        if int(x) != -1
            num[int(x)] += 1

que = []
flag = [True]*10
flag[1] = False
cost = [10**10]*10
cost[1] = 0

for i in range(10):
    if flag[i]:
        heapq.heappush(que,[C[i][1],i])

while que:
    a,b = heapq.heappop(que)
    if flag[b]:
        flag[b] = False
        cost[b] = a
        for i in range(10):
            if flag[i]:
                heapq.heappush(que,[C[i][b]+a,i])

ans = 0
for i in range(10):
    ans += num[i]*cost[i]
print(ans)


### FIXED CODE ###

import heapq

H,W = map(int,input().split())
C = [[int(x) for x in input().split()] for _ in range(10)]
num = [0] * 10
for _ in range(H):
    for x in input().split():
        if int(x) != -1:
            num[int(x)] += 1

que = []
flag = [True]*10
flag[1] = False
cost = [10**10]*10
cost[1] = 0

for i in range(10):
    if flag[i]:
        heapq.heappush(que,[C[i][1],i])

while que:
    a,b = heapq.heappop(que)
    if flag[b]:
        flag[b] = False
        cost[b] = a
        for i in range(10):
            if flag[i]:
                heapq.heappush(que,[C[i][b]+a,i])

ans = 0
for i in range(10):
    ans += num[i]*cost[i]
print(ans)
n = int(input())
a = [int(input()) for i in range(n)]
maximum = a[1]-a[0]
minimum = min(a[0], a[1])
for i in range(n):
    minimum = min(minimum, a[i])
    maximum = max(maximum, a[i] - minumum)

    
print(maximum)
        


### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
ma = a[1]-a[0]
mi = a[0]
for i in range(1,n):
    ma = max(ma, a[i] - mi)
    mi = min(mi, a[i])
    
print(ma)
s=raw_input()
t='CODEFESTIVAL2016'
c=0
for i in range(16);
  if s[i] != t[i]:
    c += 1
print c

### FIXED CODE ###

s=raw_input()
t='CODEFESTIVAL2016'
c=0
for i in range(16):
  if s[i] != t[i]:
    c += 1
print c
S=input()
K=int(input())
L=len(S)
cnt=0
ren=1

if L==1:
  ans= K//2
elif L==2:
  if S[0]==S[1]:
    ans = K
  else:
    ans = 0
else:  #|S|>=3が保証
  if S[0]!=S[-1]:
    for i in range(1,L):  
      if S[i]==S[i-1]:
        ren +=1
        if i==L-1:
          cnt += ren//2  
      else:
        cnt += ren//2
        ren=1
    ans=cnt*K
  else:
    head=0
    tail=0
    i=0
    j=0
    while S[i]==S[0]:
      head += 1
      i +=1
    while S[-1-j]==S[-1]:
      tail += 1
      j += 1
    #print(head,tail)
    elif L-head-tail<=0:
      ans=K*L//2
    else:  
      for k in range(head,L-tail):  
        #print("k=",k,"S[k]=",S[k])
        if S[k]==S[k-1]:
          ren +=1
          if k==L-tail-1:
            cnt += ren//2  
        else:
          cnt += ren//2
          ren=1
      #print("cnt",cnt)   
      
    ans=K*cnt + (K-1)*(head+tail)//2 + head//2 + tail//2
    
print(ans)


### FIXED CODE ###

S=input()
K=int(input())
N=len(S)

if S.count(S[0])==N:
  ans= K*N//2
else:
  h=0
  for i in range(N):
    if S[i]==S[0]:
      h +=1
    else:
      break
  t=0
  for i in range(N-1,-1,-1):
    if S[i]==S[-1]:
      t +=1
    else:
      break
  ren=1
  cnt=0
  for i in range(h,N-t):
    if S[i]==S[i-1]:
      ren +=1
      if i==N-t-1:
        cnt += ren//2
    else:
      cnt += ren//2
      ren=1    
      
  if S[0]==S[-1]:
    #print(h//2, (K-1)*((h+t)//2), t//2 ,K*cnt)
    ans= h//2 + (K-1)*((h+t)//2) + t//2 + K*cnt
  else:
    #print(h//2,cnt,t//2)
    ans= (h//2 + cnt + t//2)*K
print(ans)
n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
interval_max = 0
for i in range(len(a)-1):
    if a[i+1] - a[i] == 1:
        print(0)
        exit()
    interval_max = max(interval_max, a[i+1] - a[i])
a.insert(0, 0)
a.append(n)
for i in range(len(a)-1):
    interval_max = max(interval_max, a[i+1] - a[i])

step = [0]*interval_max
step[0] = step[1] = 1
for i in range(2,interval_max):
    step[i] = (step[i-2] + step[i-1])
sum_step = 1
for i in range(len(a)-1):
    sum_step *= step[a[i+1] - a[i] - 1]
sum_step = sum_step % 1000000007
print(sum_step)

### FIXED CODE ###

n, m = map(int, input().split())
if m > 0:
    a = [int(input()) for i in range(m)]
    interval_max = 0
    for i in range(len(a)-1):
        if a[i+1] - a[i] == 1:
            print(0)
            exit()
        interval_max = max(interval_max, a[i+1] - a[i])
else:
    a = []
    interval_max = n
a.insert(0, 0)
a.append(n)
for i in range(len(a)-1):
    interval_max = max(interval_max, a[i+1] - a[i])

fibb = [0]*(max(interval_max+2, 3))
fibb[0] = fibb[1] = fibb[2] = 1
for i in range(3,interval_max+2):
    fibb[i] = (fibb[i-2] + fibb[i-1]) % 1000000007
sum_step = 1
# print(a)
if m == 0:
    sum_step = fibb[n+1]
else:
    for i in range(len(a)-1):
        if i == 0 or i == len(a)-2:
            sum_step *= fibb[a[i+1] - a[i]]
            # print(fibb[a[i+1] - a[i]])
        else:
            sum_step *= fibb[a[i+1] - a[i] - 1]
            # print(fibb[a[i+1] - a[i]] - 1)
        sum_step = sum_step % 1000000007
print(sum_step)
# print(step)