Harryxun/stf_run huggingface dataset:
from math import inf
class Vertice:
  def __init__(self, num):
    self.num = num
    self.connected = []
    self.edge = []
    self.pos = inf
    
def DFS(vertice):
  judge = True
  for con in vertice.connected:
    index = vertice.connected.index(con)
    if con.pos == inf:
      con.pos = vertice.pos + vertice.edge[index]
      judge = DFS(con)
    elif con.pos != vertice.pos + vertice.edge[index]:
      judge = False
    if judge == False:
      break
  return judge


N, M = (int(_) for _ in input().split())
vertices = [Vertice(i) for i in range(N)]
L, R, D = ([None for i in range(M)] for j in range(3))
for i in range(M):
  L[i], R[i], D[i] = (int(_) for _ in input().split())
for i in range(M):
  if not vertices[R[i] - 1] in vertices[L[i] - 1].connected:
    vertices[L[i] - 1].connected.append(vertices[R[i] - 1])
    vertices[R[i] - 1].connected.append(vertices[L[i] - 1])
    vertices[L[i] - 1].edge.append(D[i])
    vertices[R[i] - 1].edge.append(-D[i])
judge = True
for i in range(N):
  if vertices[i].pos == inf:
    vertices[i].pos = 0
    judge = DFS(vertices[i])
    if judge == False:
      break
if judge:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

import sys
sys.setrecursionlimit(2000002)

def DFS(i, pos, connected, distances):
  if pos[i] == None:
    pos[i] = 0
  size = len(connected[i])
  for j in range(size):
    if pos[connected[i][j]] == None:
      pos[connected[i][j]] = pos[i] + distances[i][j]
      if DFS(connected[i][j], pos, connected, distances) == False:
        return False
    elif pos[connected[i][j]] != pos[i] + distances[i][j]:
      return False
  return True

N, M = map(int, input().split())
pos = [None for i in range(N + 1)]
connected = [[] for i in range(N + 1)]
distances = [[] for i in range(N + 1)]
for i in range(M):
  l, r, d = map(int, input().split())
  connected[l].append(r)
  distances[l].append(d)
  connected[r].append(l)
  distances[r].append(-d)
judge = True
for i in range(1, N + 1):
  if pos[i] == None:
    judge = DFS(i, pos, connected, distances)
    if judge == False:
      break
if judge:
  print('Yes')
else:
  print('No')
def main():
    import math

    def lcm(x, y):
        return (x * y) // math.gcd(x, y)
    N = int(input())
    ABCD = [list(map(int, input().split())) for i in range(N)]
    for A,B,C,D in ABCD:
        # 在庫が買う本数以下 or 在庫追加が買う本数以下
        if A < B or D < B:
            print("No")
            continue

        A %= B
        # 在庫が買う本数以下になり、補給出来ない
        if C < A:
            print("No")
            continue
        if B == D:
            print("Yes")
            continue

        flag = True
        #print((B-A-1)%(D-B) ,">", (B-1)-(C+1))
        if (B-A-1)%(math.gcd(D,B)) <= (B-1)-(C+1):
            flag = False
        
        print("Yes" if flag else "No")


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import math

    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    N = int(input())
    ABCD = [list(map(int, input().split())) for i in range(N)]
    for A,B,C,D in ABCD:
        # 在庫が買う本数以下 or 在庫追加が買う本数以下
        if A < B or D < B:
            print("No")
            continue

        A %= B
        # 在庫が買う本数以下になり、補給出来ない
        if C < A:
            print("No")
            continue
        if B == D:
            print("Yes")
            continue

        flag = True
        #print((B-A-1)%(D-B) ,">", (B-1)-(C+1))
        if (B-A-1)%(gcd(D,B)) <= (B-1)-(C+1):
            flag = False
        
        print("Yes" if flag else "No")


if __name__ == '__main__':
    main()
n,m=map(int,input().split())
s=[]
for i in range(m):
    s.append(list(map(int,input().split())))
p=list(map(int,input().split()))

onoff=[["0"],["1"]]

for i in range(n):
    tmp=[]
    for j in onoff:
        tmp.append(j+["0"])
        tmp.append(j+["1"])
    onoff=tmp

ans=0
for i in onoff:
    f=0
    for j in range(m):
        c=0
        for k in range(s[j][0]):
            if onoff[s[j][i+k]-1]=="1":
                c+=1
        if c%2!=p[j]:
            f+=1
    if f==0:
        ans+=1
print(ans)
                

### FIXED CODE ###

n,m=map(int,input().split())
s=[]
for i in range(m):
    s.append(list(map(int,input().split())))
p=list(map(int,input().split()))

onoff=[["0"],["1"]]

for i in range(n-1):
    tmp=[]
    for j in onoff:
        tmp.append(j+["0"])
        tmp.append(j+["1"])
    onoff=tmp

ans=0
for i in onoff:
    f=0
    for j in range(m):
        c=0
        for k in range(s[j][0]):
            if i[s[j][1+k]-1]=='1':
                c+=1
        if c%2!=p[j]:
            f+=1
    if f==0:
        ans+=1
print(ans)
n=int(input())
def d(s):
    if len(s)==n:print(s)
    else:for i in range(97,ord(max(s))+2):d(s+chr(i))
d("a")

### FIXED CODE ###



def dfs(string,n):
    if len(string)==n:
        print(string)
    else:
        s=string
        for i in range(97,max([ord(j)for j in string])+2):
            dfs(string+chr(i),n)
        

dfs("a",int(input()))
a, b=map(int, input().split())
if a*b%2==0:
    print(Even)
else:
    print(Odd)


### FIXED CODE ###

a, b=map(int, input().split())
if a*b%2==0:
    print("Even")
else:
    print("Odd")
[a, b] = input().split()
if a+b == 15:
  print("+")
elif a*b == 15:
  print("*")
else:
    print("x")

### FIXED CODE ###

[a, b] = map(int, input().split())
if a+b == 15:
  print("+")
elif a*b == 15:
  print("*")
else:
    print("x")
N = int(input())
A = list(map(int,input().split()))
S = []
for i in range(1,N+1):
    S.append(A.index(i)+1)
print(*S)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=[]
kari=[]
for i in range(N):
    ans.append([A[i],i+1])
ans.sort()
#print(ans)
for j in range(N):
    kari.append(ans[j][1])
print(*kari)
import numpy as np

def count_num_light(a):
  ret = [0 for _ in range(len(a))]
  n = len(a)
  for i in range(n):
    start = max(0, i-a[i])
    end = min(n-1, i+a[i])
    ret[start] += 1
    if end+1 < n:
      ret[end+1] -= 1
  for i in range(1,n):
    ret[i] += ret[i-1]
  
  return ret
                  
n, k = map(int, input().split())
a = list(map(int, input().split()))
num_light = count_num_light(a)
 
for i in range(k-1):
  num_light = count_num_light(num_light)
  if np.all(num_light == n):
    break
    
print(*num_light)


### FIXED CODE ###

def count_num_light(a):
  ret = [0 for _ in range(len(a))]
  n = len(a)
  for i in range(n):
    start = max(0, i-a[i])
    end = min(n-1, i+a[i])
    ret[start] += 1
    if end+1 < n:
      ret[end+1] -= 1
  for i in range(1,n):
    ret[i] += ret[i-1]
  
  return ret
                  
n, k = map(int, input().split())
a = list(map(int, input().split()))
num_light = count_num_light(a)
 
for i in range(k-1):
  num_light = count_num_light(num_light)
  if sum(num_light) == n**2:
    break
    
print(*num_light)
import numpy as np
n,k = list(map(int,input().split()))
p = np.array(list(map(int,input().split())))

P = 0
for i in range(n-k):
  if P < p[i:i+k].sum():
    P = p[i:i+k].sum()
    mp = p[i:i+4]

ans = 0
for i in mp:
  if i%2 == 0:
    ans += ((i+1) * i//2)/i
  else:
    ans += ((i+1) * (i//2) + (i//2) + 1)/i
print(ans)


### FIXED CODE ###

from itertools import accumulate
n,k = list(map(int,input().split()))
p = list(map(int,input().split()))

P = list(accumulate([(i+1)/2 for i in p]))
P = [0] + P
ans = max([P[i+k]-P[i] for i in range(n-k+1)])
print(ans)
from collections import deque

h, w = map(int, input().split())
maze = {(i,j):c for i in range(h) for j, c in enumerate(input())}

blacks = sum(c == '#' for c in maze.values())

def bfs(i, j):
    dq = deque()
    dq.appendleft((1, (i, j)))
    while dq:
        steps, (i, j) = dq.pop()
        if (i, j) == (h-1, w-1):
            return steps
        if maze.get((i, j), '#') == '#':
            continue
        maze[(i, j)] = '#'
        dirs = ((-1, 0), (1, 0), (0, 1), (0, -1))
        dq.extendleft((steps+1, (i+di, j+dj)) for di, dj in dirs)

print(h*w - bfs(0, 0) - blacks)

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
maze = {(i,j):c for i in range(h) for j, c in enumerate(input())}

blacks = sum(c == '#' for c in maze.values())

def bfs(i, j):
    dq = deque()
    dq.appendleft((1, (i, j)))
    while dq:
        steps, (i, j) = dq.pop()
        if (i, j) == (h-1, w-1):
            return steps
        if maze.get((i, j), '#') == '#':
            continue
        maze[(i, j)] = '#'
        dirs = ((-1, 0), (1, 0), (0, 1), (0, -1))
        dq.extendleft((steps+1, (i+di, j+dj)) for di, dj in dirs)

res = bfs(0, 0)
print(-1 if res is None else h*w - res - blacks)
a, b = map(int, input().split())
s = input()
first, second = s.split("-")
if len(first) == a and len(second) == b:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

a, b = map(int, input().split())
s = input()
try:
    first, second = s.split("-")
    if len(first) == a and len(second) == b:
        print("Yes")
    else:  
        print("No")
except:
    print("No")
import sys
a = []
for l in sys.stdin:
    a.append(map(lambda x: int(x), l.split(" ")))

N = a[0][0]
D = a[0][1]
coo = a[1:]

import math

count = 0
for c in coo:
    l = math.sqrt(c[0]**2 + c[1]**2)
    if l <= D:
        count += 1

print(count)

### FIXED CODE ###

import sys
a = []
for l in sys.stdin:
    if l == "":
        break
    a.append(list(map(lambda x: int(x), l.split(" "))))

N = a[0][0]
D = a[0][1]
coo = a[1:]

import math

count = 0
for c in coo:
    l = math.sqrt(c[0]**2 + c[1]**2)
    if l <= D:
        count += 1

print(count)
ab = input()
num_ab = ab.split()
if int(num_ab[0]) < int(num_ab[1]):
    print('a < b')
elif int(num_ab[0]) > int(num_ab[1]):
    print('a > b')
else:
    print('a == b')

### FIXED CODE ###

ab = input()
num_ab = ab.split()
a = int(num_ab[0])
b = int(num_ab[1])
if a < b:
    print('a < b')
elif a > b:
    print('a > b')
else:
    print('a == b')
A, B = list(map(int, input().split()))

def calc_num(N):
  if N % 4 == 1:
    return (1, 0)
  if N % 4 == 2:
    return (N, 1)
  if N % 4 == 3:
    return (0, 0)
  return (N, 0)

A, subA = calc_num(A-1)
B, subB = calc_num(B)

A = [int(i) for i in str(bin(A)).split("b")[1]]
B = [int(i) for i in str(bin(B)).split("b")[1]]
A[-1] += subA
A[-1] %= 2
B[-1] += subB
B[-1] %= 2

if len(B) > len(A):
  temp = [0] * (len(B)-len(A))
  temp.extend(A)
  A = temp
#print(A)
#print(B)

res = [str((A[i]+B[i])%2) for i in range(len(A))]
#print(res)
print(long("".join(res), 2))


### FIXED CODE ###

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

def calc_num(N):
  if N==0:
    return 0
  if N % 4 == 1:
    return 1
  if N % 4 == 2:
    return N ^ 1
  if N % 4 == 3:
    return 0
  return N ^ 0

A = calc_num(A-1)
B = calc_num(B)

print(A^B)
a,b,c=map(int,input().split())
for in range(10):
  print(a*c-b)
  b=(a*c-b)

### FIXED CODE ###

a,b,c=map(int,input().split())
for i in range(10):
  print(a*c-b)
  c=(a*c-b)
import numpy as np

def mod_2019(L, R):
  year = 2019
  if (R - L) >= year:
    return 0
 
  import numpy as np
  array = np.array([[i for i in range(L, R)]])
  if (array % year).min() == 0:
    return 0
  
  
  array_2d = np.dot(array.T, array)
  for i in range(len(array_2d[0])):
     array_2d[i][i] = year -1
  return (array_2d % year).min()
  

L, R = (int(i) for i in input().split())

print(mod_2019(L, R))

### FIXED CODE ###

N, A, B = (int(i) for i in input().split())
cost = N * A if N * A < B else B
print(cost)
line = input()
data = line.split()
 
height = int(data[0])
wei = int(data[1])
 
if height %2 ==0:
    print(int(height/2)*wei)
else:
  if wei %2 ==0:
    print(int(height/2)* wei + int(wei/2))
  else:
    print(wei* int(height/2) + int(wei/2)+1)


### FIXED CODE ###

data =[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]
line =int(input())

print(data[line -1])
s=str(input())

for i in range(len(s)):
  if s[i]=='a':
    S=s.index(s[i])
    break
for j in reversed(range(len(s)):
  if s[j]=='z':
    G=s.index(s[j])
    break
print(G-S+1)

### FIXED CODE ###

s=str(input())
S=int()
G=int()

#Sに最初のAのインデックスを取得
for i in range(len(s)):
  if s[i]=='A':
    S=s.index(s[i])
    break
    
ss=s[::-1]

#Gに最後のZのインデックスを取得
for j in range(len(ss)):
  if ss[j]=='Z':
    G=len(ss)-j-1
    break
print(G-S+1)
def dfs_v(u):
  color[u] = 1
  t += 1
  d[u] = t
  for v in range(n):
    if M[u][v] == 0 and color[v] == 0:
      dfs_v(v)
  color[u] = 2
  t += 1
  f[u] = t

def dfs():
  color = [0 for i in range(n)]
  t = 0
  for u in range(n):
    dfs_v(u)
  for u in range(n):
    print "%d %d %d" %(u+1, d[u], f[u])

n = input()

d = [0 for i in range(n)]
f = [0 for i in range(n)]
M = [0 for i in range(n)]0 for j in range(n)]

for i in range(n):
  u, k = map(int, raw_input().split())
  for j in range(k):
   v = input()
   M[u-1][v-1] = 1

dfs()
    

### FIXED CODE ###

n = int(raw_input())
 
d = [0 for i in range(n)]
f = [0 for i in range(n)]
G = [0 for i in range(n)]
M = [[0 for i in range(n)] for j in range(n)]
col = [0 for i in range(n)]
t = [0]
 
def DFS_visit(u):
    col[u] = 1
    t[0] += 1
    d[u] = t[0]
    for v in range(n):
        if M[u][v] == 1 and col[v] == 0:
            DFS_visit(v)
    col[u] = 2
    t[0] += 1
    f[u] = t[0]
 
def DFS():
    for u in range(n):
        if col[u] == 0:
            DFS_visit(u)
    for u in range(n):
        print'{0} {1} {2}'.format(u+1, d[u], f[u])
     
for i in range(n):
    X = map(int, raw_input().split())
    for j in range(X[1]):
        M[X[0]-1][X[2+j]-1] = 1
 
DFS()
a=list(input())
if 'a' in a & 'b' in a & 'c' in a:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

a=list(input())
if ('a' in a) & ('b' in a) & ('c' in a):
  print('Yes')
else:
  print('No')
a,b,h = map(int,input().split())

print(((a+b)*h)//2)

### FIXED CODE ###

a = int(input())
b = int(input())
h = int(input())

print(((a+b)*h)//2)
from collections import deque
import itertools
d,g = list(map(int,input().split()))
pc = [list(map(int,input().split())) for _ in range(d)]
g /= 100

pat = list(itertools.permutations(range(d)))
ans = sum([[x,y] for x,y in zip(pc[0], pc[1])][0])

def dfs(k, point, cnt, pat):
  global ans
  i = pat[k]
  
  for j in range(pc[i][0]):
      point += (i+1)
      cnt += 1
      if j == pc[i][0]-1:
        point += pc[i][1]//100
      
      if point >= g:
        ans = min(ans, cnt)
        point = 0
        cnt = 0
        break
    
  if k < d-1:
    dfs(k+1, point, cnt, pat)

for p in pat:
  dfs(0, 0, 0, list(p))

print(ans)

### FIXED CODE ###

from collections import deque
import itertools, math
d,g = list(map(int,input().split()))
pc = [list(map(int,input().split())) for _ in range(d)]
g /= 100

#ans = sum([pc[x][0] for x in range(d)])
ans = float('inf')
for bit in range(1<<d):
  cnt = 0
  point = 0
  pat = set(range(1,d+1))
  
  for i in range(d):
    if bit & (1<<i):
      point += pc[i][0]*(i+1) + pc[i][1]//100
      cnt += pc[i][0]
      pat.discard(i+1)
  
  if point < g:
      next = max(pat)
      n = min(pc[next-1][0], math.ceil((g - point)/(next)))
      cnt += n
      point += n*(next)
    
  if point >= g:
      #print(ans,cnt)
      ans = min(ans,cnt)


print(ans)
S = list(input())
acgt = ['A', 'C', 'G', 'T']

list=[]
answer=[]
for word in S:
    if word in acgt:
        list.append(word)
    else:
        answer.append(len(list))
        list=[]

print(max(answer))

### FIXED CODE ###

S = list(input())
acgt = ['A', 'C', 'G', 'T']

c=0
ans=0
for word in S:
    c = c+1 if word in acgt else 0
    ans = max(ans, c)
print(ans)
H, W = map(list, input().split())
h, w = map(list, input().split())

print((H-h)*(W-w))


### FIXED CODE ###

H, W = map(int, input().split())
h, w = map(int, input().split())

print((H-h)*(W-w))
f = lambda x: x if p[x]<0 else f(p[x])
N,M = map(int,input().split())
p = [-1]*N
for _ in range(M):
  A,B = map(lambda x:f(int(x)),input().split())
  if A==B: continue
  elif A<B: A,B=B,A
  p[A] += p[B]
  p[B] = A
print(sum(i<0 for i in p)-1)

### FIXED CODE ###

def f(x):
  while p[x]>0: x = p[x]
  return x
N,M = map(int,input().split())
p = [-1]*N
for _ in range(M):
  A,B = map(lambda x:f(int(x)-1),input().split())
  if A==B: continue
  elif A<B: A,B=B,A
  p[A] += p[B]
  p[B] = A
print(sum(i<0 for i in p)-1)
N=int(input())
A=int(input())
B=int(input())
if N==1:
    print("Hello World")
else:
    print(A+B)

### FIXED CODE ###

N=int(input())
if N == 1:
    print("Hello World")
if N == 2:
    A=int(input())
    B=int(input())
if N == 2:
    print(A+B)
N = input()
p = list(map(int,input().split()))
s = sorted(p)
k = 0
for i in range(N):
  if p[i]!=s[i]:
    k += 1
if k < 3 :
   print("YES")
else:
   print("NO")

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
b = sorted(a)
k = 0
for i in range(N):
  if a[i] != b[i]:
    k += 1
if k >2 :
  print("NO")
else:
  print("YES")
S = int(input())
h = S // 3600
m = S % 3600 // 60
s = (S % 3600) - (m * 60)
print(h,m,s sep=':')

### FIXED CODE ###

S = int(input())
h = S // 3600
m = S % 3600 // 60
s = (S % 3600) - (m * 60)
print(h,m,s,sep=':')
a,b = map(int,input().split())

if a + b = 15 :
    print("+")
elif a*b = 15 :
    print("*")
else :
    print("×")


### FIXED CODE ###

a,b = map(int,input().split())
if a+b == 15 :
  print("+")
elif a*b == 15 :
  print("*")
else :
  print("x")
#!/usr/bin/env python3
import sys


def solve(A: int, B: int):
    # 100,100のグリッド作る
    grid = [["."]*100 for _ in range(50)]+ [["#"]*100 for _ in range(50)]
    A-=1
    B-=1

    # .を＃に置き換えていく
    for i in range(50):
        for j in range(100):
            if (i%2)^(j%2) == 1 and B > 0:
                grid[i][j] = "#"
                B-=1
    
    for i in range(51,100):
        for j in range(100):
            if (i%2)^(j%2) == 1 and A>0:
                grid[i][j] = "."
                A-=1
    
    print(100,100)
    for i in range(100):
        print(''.join(rid[i]))
    return


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

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(A: int, B: int):
    # 100,100のグリッド作る
    grid = [["."]*100 for _ in range(50)]+ [["#"]*100 for _ in range(50)]
    A-=1
    B-=1

    # .を＃に置き換えていく
    for i in range(50):
        for j in range(100):
            if i%2 == 0 and j%2 == 0 and B > 0:
                grid[i][j] = "#"
                B-=1
    
    for i in range(51,100):
        for j in range(100):
            if i%2 == 0 and j%2 == 0 and A>0:
                grid[i][j] = "."
                A-=1
    
    print(100, 100)
    for i in range(100):
        print(''.join(grid[i]))
    return


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

if __name__ == '__main__':
    main()
from collections import Counter
n = int(input())
s = [list(map(int,input().split())) for i in range(n)]

t1 = []
for i in range(n):
    t1.append(str(s[i][0])+" "+str(s[i][1]))


t3 = Counter(t1)
t2 = list(set(t1))
c = []
for i in range(len(t2)):
    for j in range(i+1,n):
        x = int(t2[j][0]) - int(t2[i][0])
        y = int(t2[j][2]) - int(t2[i][2])
        e = min(t3[t2[i]],t3[t2[j]])
        for i in range(e):
            c.append(str(x) + " " + str(y))

r = Counter(c)
q = list(r.values())
q1 = max(q)
print(n-q1)

### FIXED CODE ###

from collections import defaultdict
n = int(input())
s = [list(map(int,input().split())) for i in range(n)]
s.sort()
c = []
if n == 1:
    print(1)
else:
    for i in range(n):
        for j in range(i+1,n):
            x = s[j][0] - s[i][0]
            y = s[j][1] - s[i][1]
            c.append(str(x) + " " + str(y))
    r = defaultdict(int)
    for g in c:
        r[g] += 1
    q = list(r.values())
    q1 = max(q)
    print(n-q1)
from sys import stdin
import numpy as np
x,y = [int(x) for x in stdin.readline().rstrip().split()]
ans = [(y-x),(y-(-x))+1, (y-x)+2, (x-(-y))+1]
ans = np.array(ans)
ans = ans[ans > 0]
print(min(ans))

### FIXED CODE ###

from sys import stdin
import numpy as np
x,y = [int(x) for x in stdin.readline().rstrip().split()]
ans = [(y-x),(y-(-x))+1, (-y+x)+2, (-x-y)+1]
ans = np.array(ans)
ans = ans[ans > 0]
print(min(ans))
import sys
amount = int(input())

if amount < 3:
    print(0)
    sys.exit()

coins = [x for x in range(3,amount+1)]

lst = [amount+1 for x in range(amount+1)]

lst[0] = 1
lst[1] = 0
lst[2] = 0
lst[3] = 1
lst[4] = 1
lst[5] = 1



for i in range(6,amount+1):
    counter = 0
    for coin in coins:
        change = i - coin

        if change >= 0:
            counter += lst[change]
    lst[i] = counter

print(lst[-1] % (10**9 + 7))

### FIXED CODE ###

import sys
amount = int(input())

lst1 = [3,4,5]
if amount in lst1:
    print(1)
    sys.exit()
elif amount < 6:
    print(0)
    sys.exit()

coins = [x for x in range(3,amount+1)]

lst = [amount+1 for x in range(amount+1)]

lst[0] = 1
lst[1] = 0
lst[2] = 0
lst[3] = 1
lst[4] = 1
lst[5] = 1


for i in range(6,amount+1):
    counter = 0
    for coin in coins:
        change = i - coin

        if change >= 0:
            counter += lst[change]
    lst[i] = counter

print(lst[-1] % (10**9 + 7))
s = input()
count_arr = []
count = 0
for i in s:
    if i == "R": count += 1
    elif i == "S":
        count_arr.append(count)
        count = 0
print(max(count_arr))


### FIXED CODE ###

s = input()
for i in range(3, -1, -1):
    if 'R' * i in s:
        print(i)
        break
N,M = map(int,input().split())
A = list(map(int,input().split()))

dp = [-1 for _ in range(1010)]
dp[0] = 0            

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

for i in range(1,1005):
    for x in A:          
        if i-MatchNum[x] >= 0:
            tmp = dp[i-MatchNum[x]]*10 + x
            dp[i] = max(tmp,dp[i])
print(dp[N])


### FIXED CODE ###

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

dp = [-1 for _ in range(10010)]
dp[0] = 0            

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

for i in range(1,10005):
    for x in A:          
        if i-MatchNum[x] >= 0:
            tmp = dp[i-MatchNum[x]]*10 + x
            dp[i] = max(tmp,dp[i])
print(dp[N])
def main(input):
    if 0 <= input < 86400:
        hour = input / 3600
        minute = (input / 60) % 60
        seconde = input % 60
        print("%d:%d:%d" % (hour,minute,seconde))

if __name__ == "__main__":
    main(int(input))

### FIXED CODE ###

input = int(input())
if 0 <= input < 86400:
    hour = input / 3600
    minute = (input / 60) % 60
    second = input % 60
    print("%d:%d:%d" % (hour,minute,second))
import numpy as np
s=np.asarray(list(str(input())))
r=15-s.size()
if(8 <= r + np.sum(s=="o")):
  print("YES")
else:
  print("NO")
 

### FIXED CODE ###

import numpy as np
s=np.asarray(list(str(input())))
r=15-s.size
if(8 <= r + np.sum(s=="o")):
  print("YES")
else:
  print("NO")
S = int(input())
 
hour = S / (60*60)
min = S % (60*60) / 60
sec = S % 60
 
print (hour+":"+min+":"sec)


### FIXED CODE ###

S = int(input())
 
hour = int(S / (60*60))
min = int(S % (60*60) / 60)
sec = int(S % 60)

print (':'.join(map(str,[hour,min,sec])))
a, b = map(int, raw_imput().split())

if a < b:
 print 'a < b' 
elif a == b:
 print 'a == b'
elif a > b:
 print 'a > b'

### FIXED CODE ###

a, b = map(int, raw_input().split())
 
if a < b:
 print "a < b"
elif a > b:
 print "a > b"
elif a == b:
 print "a == b"
i = list(map(int,input().split()))
a = i[0]
b = i[1]
c = i[2]
d = i[3]

m = min(c,d)
n = max(c,d)

while m != 0:
  n = m
  m = n % m
  
  
g = m
l = (c*d)/g

s = int((a-1)/c)
t = int((a-1)/d)
u = int((a-1)/l)
x = int(b/c)
y = int(b/d)
z = int(b/l)

B = b - x - y + z
A = a - 1 - s - t + u

print(B - A)



  

### FIXED CODE ###

i  = list(map(int,input().split()))
a = i[0]
b = i[1]
c = i[2]
d = i[3]

def gcd(n,m):
    x = min(n,m)
    y = max(n,m)
    while x != 0:
        x1 = x
        x = y%x
        y = x1
    return y

l = (c*d)//gcd(c,d)

count = (b - b//c - b//d + b//l) - ((a-1) - (a-1)//c - (a-1)//d + (a-1)//l)
print(count)