Harryxun/stf_run huggingface dataset:
# dpぽい気がするのでそうする
# なぜかREなる....

s = input()
dp = {}


def rec(i, cur_g, cur_p, tmp):
    # if i in dp:
    #     return dp[i]
    if i == len(s):
        ret = 0
        for j in range(len(s)):
            if tmp[j] == "p" and s[j] == "g":
                ret += 1
            elif tmp[j] == "g" and s[j] == "p":
                ret -= 1
        return ret
    if cur_g > cur_p:
        # パーを出せる（出さなくてもいい）
        ret = max(
            rec(i + 1, cur_g, cur_p + 1, tmp + "p"),
            rec(i + 1, cur_g + 1, cur_p, tmp + "g"),
        )
        # dp[i] = ret
        return ret

    else:
        # 勝てるかどうかにかかわらずグーを出すしか無い
        ret = rec(i + 1, cur_g + 1, cur_p, tmp + "g")
        # dp[i] = ret
        return ret


print(rec(0, 0, 0, ""))


### FIXED CODE ###

# dpぽい気がするのでそうする
# なぜかREなる....
# pythonだとrecursion limitがアレなのを忘れていた...
# なぜかTLEなる....

import sys

sys.setrecursionlimit(10 ** 8)


s = input()
dp = {}


def rec(i, cur_g, cur_p, g, p):
    if i in dp:
        return dp[i]
    if i == len(s):
        ret = p - g
        dp[i] = ret
        return ret
    if cur_g > cur_p:
        # パーを出せる（出さなくてもいい）
        if s[i] == "g":
            ret = max(
                rec(i + 1, cur_g, cur_p + 1, g, p + 1),
                rec(i + 1, cur_g + 1, cur_p, g, p),
            )
            dp[i] = ret
            return ret
        elif s[i] == "p":
            ret = max(
                rec(i + 1, cur_g, cur_p + 1, g, p),
                rec(i + 1, cur_g + 1, cur_p, g + 1, p),
            )
            dp[i] = ret
            return ret
    else:
        # 勝てるかどうかにかかわらずグーを出すしか無い
        if s[i] == "g":
            ret = rec(i + 1, cur_g + 1, cur_p, g, p)
            dp[i] = ret
            return ret
        elif s[i] == "p":
            ret = rec(i + 1, cur_g + 1, cur_p, g + 1, p)
            dp[i] = ret
            return ret


print(rec(0, 0, 0, 0, 0))
N, M=map(int, input().split())
KA=[list(map(int,input().split())) for _ in range(N)]

tmp=[0]*M
for i in range(N):
	for j in range(KA[i][0]):
		tmp[KA[i][j]]+=1
# print(tmp)
ans=0
for i in range(M):
	if tmp[i]==N:
		ans+=1
print(ans)

### FIXED CODE ###

N, M=map(int, input().split())
KA=[list(map(int,input().split())) for _ in range(N)]

tmp=[0]*(M+1)
for i in range(N):
	for j in range(1,KA[i][0]+1):
		tmp[KA[i][j]]+=1
# print(tmp)
ans=0
for i in range(M+1):
	if tmp[i]==N:
		ans+=1
print(ans)
import numpy

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

l = []
for v in range(n):
    l.append(list(map(int, input().split())))

ans = 0

for i in range(n - 1):
    for j in range(i + 1, n):
        if i == j:
            continue
        a = numpy.array(l[i])
        b = numpy.array(l[j])
        c = numpy.linalg.norm(b - a)
        if (c.is_integer()):
            ans += 1

print(ans)


### FIXED CODE ###

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

if (n * a > b):
    ans = b
else:
    ans = n * a

print(ans)
S = input()
T = input()

def d(s,t):
  return sum([1 if i!=j else 0 for i,j in zip(s,t)])

print(min([d(S[i:], T) for i in range(len(S)-len(T))]))


### FIXED CODE ###

S = input()
T = input()

def d(s,t):
  return sum([1 if i!=j else 0 for i,j in zip(s,t)])

print(min([d(S[i:], T) for i in range(len(S)-len(T) + 1)]))
import math
import heapq

N=int(input[0])
V=list(map(int, input[1].split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき

heapq.heapify(V)
a=heapq.heappop(V)
b=0
for i in range(len(V)):
    b=heapq.heappop(V)
    a=(a+b)/2

print(a)

### FIXED CODE ###

import math
import heapq

N=int(input())
V=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき

heapq.heapify(V)
a=heapq.heappop(V)
b=0
for i in range(len(V)):
    b=heapq.heappop(V)
    a=(a+b)/2

print(a)
K = int(input())
target = 7
for i in range(1,100000):
  if target %  K == 0:
    print(i)
    sys.exit()
  else:
    target *= 10
    target += 7
  
print("-1")

### FIXED CODE ###

K = int(input())
 
if K%2 == 0 or K%5==0:
    print(-1)
    exit()
 
nw = 7%K
ans = 1
while nw != 0:
    nw = nw*10+7
    nw %= K
    ans += 1
print(ans)
n, m = map(int, input().split())
a = [input().split() for i in range(n)]
c = []
for i in range(n):
  for j in range(m):
    b = input().split()
    c.append(abs(a[i][0] - b[0]) + abs(a[i][1] - b[1]))
  print(c.index(min(c)))
 
    
  

### FIXED CODE ###

n, m = map(int, input().split())
p = [list(map(int, input().split())) for i in range(n + m)]
for a, b in p[:n]:
  x = [abs(a - c) + abs(b - d) for c, d in p[n:]]
  print(x.index(min(x)) + 1)
n=int(input())
edges=[[] for i in range(n)]
for i in range(n-1):
    a,s,w=map(int,input().split())
    edges[a-1].append([s-1,w]);edges[s-1].append([a-1,w])
colors=[-1]*n
colors[0]=1
def dfs(now):
    for to,cost in edges[now]:
        if colors[to]==-1:
            colors[to]=(cost+colors[now])%2
            dfs(to)

dfs(0)
print(*colors,sep="\n")

### FIXED CODE ###

n=int(input())
edges=[[] for i in range(n)]
import sys

sys.setrecursionlimit(10**9)
for i in range(n-1):
    a,s,w=map(int,input().split())
    edges[a-1].append([s-1,w]);edges[s-1].append([a-1,w])
colors=[-1]*n
colors[0]=1
def dfs(now):
    for to,cost in edges[now]:
        if colors[to]==-1:
            colors[to]=(cost+colors[now])%2
            dfs(to)

dfs(0)
print(*colors,sep="\n")
N, M = map(int, input().split())
useful_num_list = list(map(int, input().split()))

need_matches = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

dp = [-1] * (N+1)
dp[0] = 0
for i in range(1, N+1):
    max_scale = -1
    for num in useful_num_list:
        if need_matches[num] <= i:
            scale = dp[i-need_matches[num]] + 1
            if max_scale < scale:
                max_scale = scale
    dp[i] = max_scale

useful_num_list.sort(reverse=True)
ans = 0
n = N
while n > 0:
    for num in useful_num_list:
        if dp[n] - 1 == dp[n - need_matches[num]]:
            ans += num * (10**(dp[n]-1))
            n -= need_matches[num]
            break
print(ans)


### FIXED CODE ###

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

need_matches = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

dp = [-1] * (N+1)
dp[0] = 0
for i in range(1, N+1):
    max_scale = -1
    for num in useful_num_list:
        if need_matches[num] <= i:
            scale = dp[i-need_matches[num]] + 1
            if max_scale < scale:
                max_scale = scale
    dp[i] = max_scale

useful_num_list.sort(reverse=True)
ans = 0
n = N
while n > 0:
    for num in useful_num_list:
        if n < need_matches[num]:
            continue
        if dp[n] - 1 == dp[n - need_matches[num]]:
            ans += num * (10**(dp[n]-1))
            n -= need_matches[num]
            break
print(ans)
import math
a,b,c,d = map(int,input().split())
n = (a-1)//c #1~a-1までのcで割り切れる数
m = b//c #1~bまでのcで割り切れる数
ck = m - n #a~bまでのcで割り切れる数

o = (a-1)//d #1~a-1までのdで割り切れる数
p = b//d #1~bまでのdで割り切れる数
dk = p - o #a~bまでのdで割り切れる数

#cでもdでも割り切れる場合
e = (c * d) // math.gcd(c, d) #cとdの最小公倍数
q = (a-1)//e #1~a-1までのeで割り切れる数
r = b//e #1~bまでのeで割り切れる数
ek = r - q #a~bまでのeで割り切れる数

#cまたはdで割り切れる数
cord = ck + dk - ek

ans = b - a + 1 - cord
print(ans)

### FIXED CODE ###

from fractions import gcd
a,b,c,d = map(int,input().split())
n = (a-1)//c #1~a-1までのcで割り切れる数
m = b//c #1~bまでのcで割り切れる数
ck = m - n #a~bまでのcで割り切れる数

o = (a-1)//d #1~a-1までのdで割り切れる数
p = b//d #1~bまでのdで割り切れる数
dk = p - o #a~bまでのdで割り切れる数

#cでもdでも割り切れる場合
e = (c * d) // gcd(c, d) #cとdの最小公倍数
q = (a-1)//e #1~a-1までのeで割り切れる数
r = b//e #1~bまでのeで割り切れる数
ek = r - q #a~bまでのeで割り切れる数

#cまたはdで割り切れる数
cord = ck + dk - ek

ans = b - a + 1 - cord
print(ans)
N, M, X = map(int, input().split())
A = list(map(int, input().split()))
right = 0
left = 0
for i in range(X, N):
    if i in A:
        right += 1
for i in range(0, X+1):
    if i in B:
        left += 1
print(min(right,left))

### FIXED CODE ###

N, M, X = map(int, input().split())
A = list(map(int, input().split()))
right = 0
left = 0
for i in range(X, N):
    if i in A:
        right += 1
for i in range(0, X+1):
    if i in A:
        left += 1
print(min(right,left))
a,b = int(input().split())
if a % 2 == 0 or b & 2 == 0:
    print("Evem")
else:
    print("Odd")
    

### FIXED CODE ###

a = list(map(int, input().split()))
if a[0] % 2 == 0 or a[1] % 2 == 0:
	print("Even")
else:
	print("Odd")
word=list(input())
check=True
for i in range(len(word)//2)
    if word[i]==word[len(word)-1]:
        continue:
    else:
          check=False
          braek:
if check==True:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

S=list(input())
N=len(S)
check=True
for i in range(N//2):
    if S[i]!=S[N-1-i]:
        check=False
        break
if check==False:
    print("No")
else:
    C=False
    for i in range((N//2)//2):
        if S[i]!=S[N//2-1-i]:#0123456
          C=True
          break
    if C==True:
        print("No")
    else:
        print("Yes")
l,r=map(int,input().split())
s=list(range(l,r+1))
ans=[2018]
for i in range(r-l):
    for j in range(i+1,r-l+1):
        ans=min((s[i]%2019)*(s[j]%2019),ans)
        if ans==0:
            break
print(ans)

### FIXED CODE ###

l,r=[int(i) for i in input().split()]
ans=2018
for i in range(l,r):
    for j in range(i+1,r+1):
        ans=min(i*j%2019,ans)
        if ans==0:
            print(ans)
            exit()
print(ans)
K = int(input())

def gcd(a, b):
  if b == 0:
    return a
  return gcd(b, a % b)

s = 0
for i in range(1, K + 1):
	for j in range(1, K + 1):
      for k in range(1, K + 1):
        s += gcd(i, gcd(j, k))

print(s)

### FIXED CODE ###

K = int(input())

def gcd(a, b):
  if b == 0:
    return a
  return gcd(b, a % b)


gcds = [[0 for _ in range(K + 1)] for _ in range(K + 1)]

for i in range(1, K + 1):
  for j in range(1, K + 1):
    gcds[i][j] = gcd(i, j)

s = 0
for i in range(1, K + 1):
  for j in range(1, K + 1):
    for k in range(1, K + 1):
      s += gcds[gcds[i][j]][k]

print(s)
d=int(input())
c=list(map(int,input().split()))
s=[]
for i in range(d):
  s.append(list(map(int,input().split())))
last=[0]*26

for day in range(1,d+1):
  co=[]
  dla=[]
  down=0
  for (i,j) in zip(last,c):
    down+=(day-i)*j
  for (i,j) in zip(last,c):
    dla.append(down-(j*(day-i)))
  for con in range(26):
    co.append(s[day][con]-dla[con]*c[con])
  choice=co.index(max(co))
  last[choice]=day
  print(choice+1)

### FIXED CODE ###

d=int(input())
c=list(map(int, input().split()))
s=[]
for i in range(d):
  s.append(list(map(int, input().split())))
for i in s:
  print(i.index(max(i))+1)
N=int(input())
A=input().split()
A=[int(a) for a in A]

import math
a=math.gcd(A[0],A[1])
for i in range(2,len(A)):
	a=math.gcd(a,A[i])
print(a)



### FIXED CODE ###

def gcd(x,y):
  return y if x%y==0 else gcd(y,x%y)
N=input();A=list(map(int,input().split()));
g=A[0];
for a in A:
  g=gcd(g,a)
print(g)
def main(length_num,num_list):
    count_num = 0
    for i in range(0,length_num):
        flag_tag = True
        for j in range(0 , i ):
          if int(num_list[i]) >= int(num_list[j]):
              flag_tag = False
              break
        if flag_tag != False:
            count_num += 1
    return count_num


    
if __name__ == "__main__":
    input_length_num = int(input())
    input_num2 = input()
    input_num_list = input_num2.split()
    print(main(length_num,num_list))

### FIXED CODE ###

def main(test_case,clear_case):
    if test_case <= clear_case:
      return "Yes"
    else:
      return "No"
    
if __name__ == "__main__":
    input_num = input()
    num1 = int(input_num.split()[0])
    num2 = int(input_num.split()[1])
    print(main(num1,num2))
n=int(input())
a=[list(map(int,input().split())) for i in range(2)]
ans=0
for i in range(n):
  cnt=0
  for j in range(i+1):
    cnt+=a[j][0]
  for j in range(i,n):
    cnt+=a[j][1]
  ans=max(ans,cnt)
print(ans)

### FIXED CODE ###

n=int(input())
a=[list(map(int,input().split())) for i in range(2)]
ans=0
for i in range(n):
  cnt=0
  for j in range(i+1):
    cnt+=a[0][j]
  for j in range(i,n):
    cnt+=a[1][j]
  ans=max(ans,cnt)
print(ans)
n,m=map(int,input().split())

p=[[] for _ in range(n)]

for _ in range(m):
    x,y=map(int,input().split())
    p[x-1].append(y-1)



def calc(x):
    if len(p[x])==0:
        return 0
    return max([calc(i) for i in p[x]])+1

m=0
for i in range(n):
    j=calc(i)
    if m<j:
        m=j
print(m)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)


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

p=[[] for _ in range(n)]

for _ in range(m):
    x,y=map(int,input().split())
    p[x-1].append(y-1)

f=[-1 for _ in range(n)]

def calc(x):
    if f[x]!=-1:
        return f[x]
    if len(p[x])==0:
        f[x]=0
        return 0
    f[x]=max([calc(i) for i in p[x]])+1
    return f[x]

m=0
for i in range(n):
    if f[i]!=-1:
        continue
    m=max(m,calc(i))
print(m)
N = int( input() )
T = [ int( input() ) for _ in range(N) ]


# 最小公倍数を求めたい
# aとbの最小公倍数 = a*b / aとbの最大公約数
# 最大公約数 (Greatest Common Divisor)
def GCD( a, b ):
    if b == 0: return a
    return GCD(b, a%b)

# 最小公倍数 (Least Common Multiple)
def LCM( a, b ):
    return a*b / GCD(a,b)


ans = LCM( T[0], T[1] )
for i in range(2,N):
    ans = LCM( ans, T[i] )
print( ans )

### FIXED CODE ###

import fractions
import functools

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

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

def lcm_list( numbers ):
    return functools.reduce( lcm, numbers, 1 )

if N == 1: print( T[0] )
else     : print( lcm_list(T) )
a, b = map(int, input().split())
A = 0

print(a * a - b)


### FIXED CODE ###

a = int(input())
b = int(input())
print(a * a - b)
#C
import math
#入力
A,B=map(int,input().split())

#処理
c=0
d=0
c=max([math.floor(A/0.08),math.floor(B/0.1)])
d=min([math.ceil((A+1)/0.08),math.ceil((B+1)/0.1)])
x=-1
for i in range(c,d+1):
    if math.floor(i*0.08)==A and math.floor(i*0.1)==B:
        z=i
        break
print(z)

### FIXED CODE ###

#C
import math
#入力
A,B=map(int,input().split())

#処理
c=0
d=0
c=max([math.floor(A/0.08),math.floor(B/0.1)])
d=min([math.ceil((A+1)/0.08),math.ceil((B+1)/0.1)])
z=-1
for i in range(c,d+1):
    if math.floor(i*0.08)==A and math.floor(i*0.1)==B:
        z=i
        break
print(z)
from collections import deque
x,y,a,b,c = map(int,input().split())
red = [int(i) for i in input().split()]
gw = [int(i) for i in input().split()] + [int(i) for i in input().split()]
red.sort()
gw.sort()
gwrui = []
rui = 0
for i in range(b+c):
    rui += gw[i]
    gwrui.append(rui)
redq = deque(red[:x])
ans = 0
oisr = 0
for i in range(1,x+1):
    oisr += redq.popleft()
    temp = oisr
    temp += gwrui[x+y-i]
    ans = max(ans,temp)
print(ans)

### FIXED CODE ###

from collections import deque
x,y,a,b,c = map(int,input().split())
red = [int(i) for i in input().split()]
g = [int(i) for i in input().split()]
w = [int(i) for i in input().split()]
red.sort(reverse=True)
g.sort(reverse=True)
g = g[:y]
gw = g+w
gw.sort(reverse=True)
gwrui = []
rui = 0
for i in range(y+c):
    rui += gw[i]
    gwrui.append(rui)
red = red[:x]
rrui = []
rui = 0
for i in range(x):
    rui += red[i]
    rrui.append(rui)
rrui = [0] + rrui
ans = 0
oisr = 0
lgw = len(gw)
#print(red,gw,gwrui)
for i in range(0,x+1):
    temp = rrui[i]
    if x+y-i <= lgw:
        temp += gwrui[x+y-i-1]
        ans = max(ans,temp)
print(ans)
MOD = 10**9 + 7
K = input()
N = len(K)
D = int(input())
S = [[0, 0] for i in range(D)]
S[0][0] = 1
for i in range(N):
    c = int(K[i])
    T = [[0, 0] for i in range(D)]
    for d in range(D):
        w0, w1 = S[d]
        w0 %= MOD
        w = S[d][0] % MOD
        for v in range(c):
            T[d+v-D][1] += w0
        T[d+c-D][0] += w0

        w1 %= MOD
        for v in range(10):
            T[d+v-D][1] += w1
    S = T
print((sum(S[0])-1) % MOD)

### FIXED CODE ###

MOD = 10**9 + 7
K = input()
N = len(K)
D = int(input())

S = [[0, 0] for i in range(D)]
S[0][0] = 1
for i in range(N):
    c = int(K[i])
    T = [[0, 0] for i in range(D)]
    for d in range(D):
        w0, w1 = S[d]
        w0 %= MOD
        w = S[d][0] % MOD
        for v in range(c):
            T[(d+v)%D][1] += w0
        T[(d+c)%D][0] += w0

        w1 %= MOD
        for v in range(10):
            T[(d+v)%D][1] += w1
    S = T
print((sum(S[0])-1) % MOD)
n = int(input())
a = list(map(int, input().split()))

hu = []
sei = []
for i in a:
	if i < 0:
		hu.append(i)
	else:
		sei.append(i)
hu.sort()
sei.sort()
if len(hu)%2 == 0:
	ans = sum(sei) + (-1)*sum(hu)
else:
	b = sei.pop(0)
	c = hu.pop(-1)
	if abs(b) <= abs(c):
		b *= -1
		c *= -1
	ans = sum(sei) + (-1)*sum(hu)
	ans += (b+c)
print (ans)


### FIXED CODE ###

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

hu = []
sei = []
for i in a:
	if i < 0:
		hu.append(i)
	else:
		sei.append(i)
hu.sort()
sei.sort()
if len(hu)%2 == 0:
	ans = sum(sei) + (-1)*sum(hu)
else:
	if len(sei) == 0:
		ans = (-1)*sum(hu[:-1]) + hu[-1]
		print (ans)
		exit()
	else:
		b = sei[0]
	if len(hu) == 0:
		ans = sum(sei[1:] + sei[-1])
		print (ans)
		exit()
	else:
		c = hu[-1]
	if abs(b) <= abs(c):
		b *= -1
		c *= -1
	ans = sum(sei[1:]) + (-1)*sum(hu[:-1])
	ans += (b+c)
print (ans)
a,b,c = map(int,input())
for i in range(b):
  if(a*i%b==c):
    print("YES")
    ans = True
    
if(!ans):print("NO")


### FIXED CODE ###

a,b,c = map(int,input().rstrip().split())
ans = False
for i in range(b):
  if(a*i%b==c and not(ans)):
    print("YES")
    ans = True
    
if(not(ans)):
  print("NO")
N = int(input())
S = input(())
a = len(S)
A = chr(ord(S[0])+N)
for i in range(1,N):
  A += chr(ord(S[i])+N)
print(A)

### FIXED CODE ###

n = int(input())
chars = input()

alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
ans = ""
for c in chars:
    pos = alphabet.find(c)
    ans += alphabet[(pos + n) % 26]

print(ans)
s=list(input())
print(sum(int(s)))

### FIXED CODE ###

s=list(input())
print(s.count("1"))
N, K = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
K = K-1
ans = -10**9-1
for i in range(N):
   i += 1
   start = i
   circle = 1
   number = c[i-1]
   while i != start:
      i = p[i-1]
      circle += c[i-1]
      number += 1
   for j in range (min(number, K+1)):
      sum = 0
      for k in range(j+1):
         index = (i + k - 1)%number
         sum += c[index]
      if circle > 0:
         sum = circle*((K-j)//number) + sum
      ans = max(sum, ans)
print(ans)

### FIXED CODE ###

N, K = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
K = K-1
ans = -10**9-1
for h in range(N):
   i = h+1
   start = i
   circle = [c[i-1]]
   i = p[i-1]
   while i != start:
      score = circle[-1] + c[i-1]
      circle.append(score)
      i = p[i-1]
   l=len(circle)
   for j in range(min(l, K+1)):
      if circle[l-1] > 0:
         score = circle[j] + ((K - j)//l)*circle[l-1]
      else:
         score = circle[j]
      ans = max(score, ans)      
print(ans)
n, m = map(int, input().split())
hole_ids = {int(input()) - 1: 0 for _ in range(m)}
X = 1000000007


def solve(n, hole_ids):
    nums = []
    # nums = [0] * n
    for i in range(n):
        if i in hole_ids:
            nums.append(0)
            # nums[i] = 0
            continue

        if i == 0:
            nums.append(1)
            # nums[i] = 1
        elif i == 1:
            # 1つ前から1段上がるから2つ前から2個飛ばし
            nums.append(nums[-1] + 1)
            # nums[i] = nums[i-1] + 1
        else:
            nums.append((nums[-1] % X + nums[-2] % X) % X)
            # nums[i] = (nums[i-1] + nums[i-2]) % X
    return nums[-1]


print(solve(n, hole_ids))
n, m = map(int, input().split())
hole_ids = {int(input()) - 1: 0 for _ in range(m)}
X = 1000000007


def solve(n, hole_ids):
    nums = []
    # nums = [0] * n
    for i in range(n):
        if i in hole_ids:
            nums.append(0)
            # nums[i] = 0
            continue

        if i == 0:
            nums.append(1)
            # nums[i] = 1
        elif i == 1:
            # 1つ前から1段上がるから2つ前から2個飛ばし
            nums.append(nums[-1] + 1)
            # nums[i] = nums[i-1] + 1
        else:
            nums.append((nums[-1] % X + nums[-2] % X) % X)
            # nums[i] = (nums[i-1] + nums[i-2]) % X
    return nums[-1]


print(solve(n, hole_ids))


### FIXED CODE ###

n, m = map(int, input().split())
hole_ids = {int(input()) - 1: 0 for _ in range(m)}
X = 1000000007


def solve(n, hole_ids):
    # nums = []
    nums = [0] * n
    for i in range(n):
        if i in hole_ids:
            # nums.append(0)
            nums[i] = 0
            continue

        if i == 0:
            # nums.append(1)
            nums[i] = 1
        elif i == 1:
            # 1つ前から1段上がるから2つ前から2個飛ばし
            # nums.append(nums[-1] + 1)
            nums[i] = nums[i-1] + 1
        else:
            # nums.append((nums[-1] % X + nums[-2] % X) % X)
            nums[i] = (nums[i-1] + nums[i-2]) % X
    return nums[-1]


print(solve(n, hole_ids))
# -*- coding: utf-8 -*-

import numpy as np

N,  = map(int, input().split())
A = np.array(list((map(int, input().split()))))


thr = 10**18

res = np.prod(A)

if res > thr:
    res = -1

print(int(res))


### FIXED CODE ###

# coding: utf-8

#import numpy as np

N = int(input())
A = list((map(int, input().split())))

thr = 10**18

res = 1

if 0 in A:
    res = 0
else:
    for a in A:

        res *= a

        if res > thr:
            res = -1
            break

print(int(res))
N,X = map(int, input().split())
L = [x for x in map(int, input().split())]
accumL = [sum(L[:x]) <= X for x in range(len(L)+1)]
print(accumL.index(False))

### FIXED CODE ###

N,X = map(int, input().split())
L = [x for x in map(int, input().split())]
accumL = [sum(L[:x]) <= X for x in range(len(L)+1)]
if accumL[-1] == True:
  print(N + 1)
else:
  print(accumL.index(False))
N = int(input())
A = sorted(list(map(int, input().split())))
print(sum(A[N:2*N])


### FIXED CODE ###

N = int(input())
A = sorted(list(map(int, input().split())))

ans = 0
for i in range(2 * N):
    if i % 2 == 1:
        ans += A[3 * N - i - 1]

print(ans)
num = int(input())
num_ls = sorted([x for x in map(int, input().split(' '))])
while True:
    dam = []
    searchMin = [ x for x in num_ls if x != 1 ]
    for x in num_ls:
        div = x % min(searchMin)
        if div == 0:
            dam.append(x)
        else:
            dam.append(div)

    if num_ls == dam:
        break
    else:
        num_ls = dam

print(min(num_ls))

### FIXED CODE ###

x, y = map(int, input().split(' '))
if y % x == 0:
    print(x+y)
else:
    print(y-x)
n, m = map(int, input().split())
WA = [0] * n
AC = [0] * n

for i in range(m):
    p, s = map(str, input().split())
    p = int(p) - 1
    if s == "AC":
        AC[p] = 1
    elif s == "WA" and AC[p] == 0:
        WA[p] += 1

WA = [WA[i] for i in range(m) if AC[i] >= 1]

print(sum(AC), sum(WA))

### FIXED CODE ###

n, m = map(int, input().split())
WA = [0] * n
AC = [0] * n

for i in range(m):
    p, s = map(str, input().split())
    p = int(p) - 1
    if s == "AC":
        AC[p] = 1
    elif s == "WA" and AC[p] == 0:
        WA[p] += 1

for i in range(n):
    WA[i] = 0 if AC[i] == 0 else WA[i]

print(sum(AC), sum(WA))
import math

a, b, c, d = (int(x) for x in input().split())
def kansu(x,y,z):
    sta = x
    end = y
    if sta%z != 0:
        sta = sta+(z-(sta%z))
    if end%z != 0:
        end = end-(end%z)
    ans = ((end-sta)/z) +1
    return ans
a1 = kansu(a,b,c)
a2 = kansu(a,b,d)
lcm = c*d/(math.gcd(c,d))
a3 = kansu(a,b,lcm)
print(int(b-a-a1-a2+a3+1))

### FIXED CODE ###

import fractions
 
a, b, c, d = (int(x) for x in input().split())
def kansu(x,y,z):
    sta = x
    end = y
    if sta%z != 0:
        sta = sta+(z-(sta%z))
    if end%z != 0:
        end = end-(end%z)
    ans = ((end-sta)//z) +1
    return ans
a1 = kansu(a,b,c)
a2 = kansu(a,b,d)
lcm = c*d//(fractions.gcd(c,d))
a3 = kansu(a,b,lcm)
print(b-a-a1-a2+a3+1)