Harryxun/stf_run huggingface dataset:
import sys
import itertools
import networkx as nx
H, W = map(int, sys.stdin.buffer.readline().split())
S = b''.join(sys.stdin.buffer.read().split())

source = 2 * H * W
sink = source + 1

INF = 10**12

graph = nx.DiGraph()


def add(start, end, cap):
    graph.add_edge(start, end, capacity=cap)


for i in range(H * W):
    x, y = divmod(i, W)
    if S[i] == ord('.'):
        add(2 * i, 2 * i + 1, 1)
    else:
        add(source, 2 * i + 1, INF)
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        x1, y1 = x + dx, y + dy
        if 0 <= x1 < H and 0 <= y1 < W:
            j = x1 * W + y1
            add(2 * i + 1, 2 * j, INF)
        else:
            add(2 * i + 1, sink, INF)
ans = nx.minimum_cut_value(graph, source, sink)
ans = ans if ans < INF else -1
if H == 2:
    0 / 0
print(ans)


### FIXED CODE ###

import sys
import itertools
from scipy.sparse import csr_matrix, lil_matrix
from scipy.sparse.csgraph import maximum_flow

H, W = map(int, sys.stdin.buffer.readline().split())
S = b''.join(sys.stdin.buffer.read().split())

source = 2 * H * W
sink = source + 1

INF = source * 2

graph = lil_matrix((sink + 1, sink + 1), dtype=int)

for i in range(H * W):
    x, y = divmod(i, W)
    if S[i] == ord('.'):
        graph[2 * i, 2 * i + 1] = 1
    else:
        graph[source, 2 * i + 1] = INF
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        x1, y1 = x + dx, y + dy
        if 0 <= x1 < H and 0 <= y1 < W:
            j = x1 * W + y1
            graph[2 * i + 1, 2 * j] = 1
        else:
            graph[2 * i + 1, sink] = INF
graph = graph.tocsr()
ans = maximum_flow(graph, source, sink).flow_value
ans = ans if ans < INF else -1
print(ans)
N, M = map(int, input().split())
A = [input() for _ in range(N)]
B = [input() for _ in range(M)]

l = 0
while l <= len(A[0]) - len(B[0]):
	for i in range(N - M + 1):
		s = A[i][l:]
		if not B[0] in s:
			continue
		if 0 == s.index(B[0]):
			for m in range(1, M):
				if 0 != A[i + m][l:].index(B[m]):
					break
			else:
				print("Yes")
				exit()
	l += 1
print("No")


### FIXED CODE ###

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

l = 0
while l <= len(A[0]) - len(B[0]):
	for i in range(N - M + 1):
		s = A[i][l:]
		if not B[0] in s:
			continue
		if 0 == s.index(B[0]):
			for m in range(1, M):
				if not B[m] in A[i + m][l:]:
					break
				if 0 != A[i + m][l:].index(B[m]):
					break
			else:
				print("Yes")
				exit()
	l += 1
print("No")
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def same(x, y):
    if find(x) == find(y):
        return True
    else:
        return False

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x] > rank[y]:
        x, y = y, x
    par[x] += par[y]
    par[y] = x

def uCnt(x):
    return -par[find(x)]

N, M, K = map(int, input().split())
par = [-1 for i in range(N)]
rank = [0] * N
frendCnt = [0] * N
bloc = [[] for _ in range(N)]
for i in range(N):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    frendCnt[a] += 1
    frendCnt[b] += 1
    unite(a, b)

for i in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    bloc[c].append(d)
    bloc[d].append(c)

for i in range(N):
    ans = uCnt(i) - len(bloc[i]) - frendCnt[i] - 1
    print(ans, end=' ')

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#初期化
#根なら-size,子なら親の頂点
par = [-1]*n

num = [0]*n

for i in range(m):
    a,b = map(int,input().split())
    unite(a-1,b-1)
    num[a-1] += 1
    num[b-1] += 1

edge = [[] for i in range(n)]

for i in range(k):
    c,d = map(int,input().split())
    edge[c-1].append(d-1)
    edge[d-1].append(c-1)


for i in range(n):
    cnt = size(i) - num[i] - 1
    for e in edge[i]:
        if same(e,i):
            cnt -= 1
    print(cnt,end=' ')
N=int(input())
xy=[list(map(int,input().split())) for _ in [0]*N]

dx = [[10**10]*N for _ in [0]*N]
dy = [[10**10]*N for _ in [0]*N]
ps = set()
qs = set()
for i in range(N):
    for j in range(N):
        if i==j:continue
        dx[i][j] = xy[i][0] - xy[j][0]
        dy[i][j] = xy[i][1] - xy[j][1]
        ps.add(dx[i][j])
        qs.add(dy[i][j])
for i in range(N):
    dx[i] = set(dx[i]) - set(10**10)
    dy[i] = set(dy[i]) - set(10**10)

ans = 0
for p in ps:
    for q in qs:
        cnt = 0
        for i in range(N):
            if (p in dx[i]) and (q in dy[i]):
                cnt += 1
        ans = max(ans,cnt)

print(N-ans)

### FIXED CODE ###

N=int(input())
xy=[list(map(int,input().split())) for _ in [0]*N]

pq = {0:0}
for i in range(N):
    for j in range(N):
        if i==j:continue
        p = xy[i][0] - xy[j][0]
        q = xy[i][1] - xy[j][1]
        pq[(p,q)] = pq.get((p,q),0)+1

print(N - max(pq.values()))
n=int(input())
v=list(map(int,input().split()))
v1 = [v[2*i] for i in range(n//2)]

if len(set(v))==1:
    print(n//2)
    exit()
d1 = {}
for x in v1:
    if x in d1.keys():
        d1[x] = d1[x] + 1
    else:
        d1[x] = 1
d1 = sorted(d1.items(), key=lambda x:-x[0])

d2 = {}
v2 = [v[2*i+1] for i in range(n//2)]
ma2=0
for x in v2:
    if x in d2.keys():
        d2[x] = d2[x] + 1
    else:
        d2[x] = 1
d2 = sorted(d2.items(), key=lambda x:-x[0])
if d1[0][0] != d2[0][0]:
    print(n-d1[0][1]-d2[0][1])
else:
    if len(d1==1):
        print(n-d1[0][1]-d2[1][1])
    elif len(d2==1):
        print(n-d1[1][1]-d2[0][1])
    else:
        print(n-max(d1[0][1]+d2[1][1],d1[1][1]+d2[0][1]))

### FIXED CODE ###

n=int(input())
v=list(map(int,input().split()))
v1 = [v[2*i] for i in range(n//2)]

if len(set(v))==1:
    print(n//2)
    exit()
d1 = {}
for x in v1:
    if x in d1.keys():
        d1[x] = d1[x] + 1
    else:
        d1[x] = 1
d1 = sorted(d1.items(), key=lambda x:-x[1])

d2 = {}
v2 = [v[2*i+1] for i in range(n//2)]
ma2=0
for x in v2:
    if x in d2.keys():
        d2[x] = d2[x] + 1
    else:
        d2[x] = 1
d2 = sorted(d2.items(), key=lambda x:-x[1])
if d1[0][0] != d2[0][0]:
    print(n-d1[0][1]-d2[0][1])
else:
    if len(d1) == 1:
        print(n-d1[0][1]-d2[1][1])
    elif len(d2) == 1:
        print(n-d1[1][1]-d2[0][1])
    else:
        print(n-max(d1[0][1]+d2[1][1],d1[1][1]+d2[0][1]))
A, B, C, D, E, F = map(int, input().split())
M = 0
Concmax = 0

for i in range(F//100//A+1):
  WA = i*100*A
  for k in range((F-WA)//100//B+1):
    WB = k*100*B
    W = WA+WB
    if W <= F:
      for j in range((F-W)//C+1):
        SC = j*C
        for l in range((F-W-C)//D+1):
          SD = l*D
          S = SC+SD
          if 0 < W+S <= F and S <= W*E/100:
            Conc = S/(S+W)
            if Conc > Concmax:
              Concmax= Conc
              Sans = S
              M = S+W
#              print(WA,WB,SC,SD,Conc)
print(M,Sans)

### FIXED CODE ###

A, B, C, D, E, F = map(int, input().split())
ans = 0
W = set()
S = set()

for i in range(F):
  x1 = 100 * A * i
  if x1 > F:
    break
  for j in range(F):
    x2 = x1 + 100 * B * j
    if x2 > F or x2 == 0:
      break
    W.add(x2)
for i in range(F):
  y1 = C * i
  if y1 > F:
    break
  for j in range(F):
    y2 = y1 + D * j
    if y2 > F:
      break
    S.add(y2)

W = list(set(W))
S = list(set(S))

for i in range(len(W)):
  for j in range(len(S)):
    tmp = S[j]/W[i]
    tmp1 = S[j] + W[i]
    if tmp1 <= F and ans <= tmp <= E/100:
      ans = tmp
      ans1 = tmp1
      ans2 = S[j]
print(ans1, ans2)
n=int(input())
a=list(map(int,input().split()))
s=[i for i in a if i<0]
t=sorted([i for i in a if i>0])
if len(s)==0:
    print(t[-1]-t[0]+sum(t[1:-1]))
    k=t[0]
    for i in range(1,n-1):
        print(k,t[i])
        k-=t[i]
    print(t[-1],k)
elif len(t)==0:
    d=s[0]
    for i in range(1,n):
        print(d,s[i])
        d-=s[i]
else:
    print(t[-1]-sum(s)+sum(t[:-1]))
    p=t[-1]
    for i in range(1,len(s)):
        print(p,s[i])
        p-=s[i]
    g=s[0]
    for i in range(len(t)-1):
        print(g,t[i])
        g-=t[i]
    print(p,g)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
s=sorted([i for i in a if i<0])
t=sorted([i for i in a if i>=0])
if len(s)==0:
    print(t[-1]-t[0]+sum(t[1:-1]))
    k=t[0]
    if n!=2:
        for i in range(1,n-1):
            print(k,t[i])
            k-=t[i]
    print(t[-1],k)
elif len(t)==0:
    d=s[-1]
    print(s[-1]-sum(s[:-1]))
    for i in range(n-1):
        print(d,s[i])
        d-=s[i]
else:
    print(t[-1]-sum(s)+sum(t[:-1]))
    p=t[-1]
    for i in range(1,len(s)):
        print(p,s[i])
        p-=s[i]
    g=s[0]
    for i in range(len(t)-1):
        print(g,t[i])
        g-=t[i]
    print(p,g)
ans = None
for r in range(100):
    for i in [-r, r]:
        if (X + i) not in p:
            ans = X+i
            break

    if ans is not None:
        break


print(ans)

### FIXED CODE ###

X, N = list(map(int, input().split()))
p = list(map(int, input().split()))

ans = None
for r in range(100):
    for i in [-r, r]:
        if (X + i) not in p:
            ans = X+i
            break

    if ans is not None:
        break

print(ans)
import heapq
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
R = [i for i in range(N)]
def root(R, i):
  if R[i] == i:
    return i
  else:
    R[i] = root(R, R[i])
    return R[i]
def union(i, j):
  Ri = root(R, i)
  Rj = root(R, j)
  if A[Ri] <= A[Rj]:
    R[j] = i
  else:
    R[i] = j
for m in range(M):
  i, j = map(int, input().split())
  union(i, j)
for i in range(N):
  r = root(R, i)
T = {}
for i, t in enumerate(list(set(R))):
  T[t] = i
F = [[] for i in T]
for i, r in enumerate(R):
  heapq.heappush(F[T[r]], A[i])
F = [sorted(f) for f in F]
RF = [i for i in range(len(F))]
ans = 0
if len(F) > 1:
  for i in range(len(F) - 1):
    for f in F:
      if len(f) == 0:
        ans = 'Impossible'
    if ans == 'Impossible':
      break
    f0 = sorted([[heapq.heappop(F[j]), j] for j in range(len(F))])
    ans += f0[0][0] + f0[1][0]
    for f in f0[2:]:
      heapq.heappush(F[f[1]], f[0])
    F[f0[0][1]] = heapq.merge(F[f0[0][1]], F[f0[1][1]])
    F.pop(f0[1][1])
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
A = [int(x) for x in input().split()]
R = [i for i in range(N)]
def root(R, i):
  if R[i] == i:
    return i
  else:
    R[i] = root(R, R[i])
    return R[i]
def union(i, j):
  ri = root(R, i)
  rj = root(R, j)
  if ri <= rj:
    R[rj] = ri
  else:
    R[ri] = rj
for m in range(M):
  i, j = map(int, input().split())
  union(i, j)
for i in range(N):
  R[i] = root(R, i)
if N < 2 * (N - M - 1):
  print('Impossible')
elif M == N - 1:
  print(0)
else:
  cnt= 0
  E = N - M - 2
  C = [0] * N
  F = sorted([[a, R[i]] for i, a in enumerate(A)])
  for a, r in F:
    if C[r] == 0:
      C[r] = a
      cnt += a
    elif E > 0:
      cnt += a
      E -= 1
  print(cnt)
input_ = input().split()

a, b, c = input_
a, b, c = int(a), int(b), int(c)

if a == b + c, b == c + a, c == a + b:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

input_ = input().split()

a, b, c = input_
a, b, c = int(a), int(b), int(c)

if a == b + c or b == c + a or c == a + b:
    print("Yes")
else:
    print("No")
# C
import numpy as np

inp = input().split(' ')
N, M = int(inp[0]), int(inp[1])

inps = input().split(' ')
H = np.array([int(inps[i]) for i in range(len(inps))])
AB = []
for i in range(M):
    inps = input().split(' ')
    AB.append([int(inps[0]), int(inps[1])])
    
import pandas as pd

df_1, df_2 = pd.DataFrame(), pd.DataFrame()
tmp = np.array(AB).T
df_1['1'] = tmp[0]
df_1['2'] = tmp[1]
df_2['1'] = tmp[1]
df_2['2'] = tmp[0]
print(sum([sum(df['2'].apply(lambda t: H[t-1]) <= H[g-1]) - len(df) == 0 for g, df in pd.concat([df_1, df_2]).groupby('1')]))

### FIXED CODE ###

# C
N, M = map(int, input().split())
H = list(map(int, input().split()))

A = [0] * N
for i in range(M):
    a, b = map(int, input().split())
    A[a-1] = max(A[a-1], H[b-1])
    A[b-1] = max(A[b-1], H[a-1])
    
res = sum([H[i] > A[i] for i in range(N)])
print(res)
N = int(input())
u, v, w = [0]*(N-1), [0]*(N-1), [0]*(N-1)
n = [-1] * N 
# n[][0] 色　n[][1] 連結先一覧リスト(連結先奇数なら+ 偶数なら-がかかる1追加された値)
for i in range(N):
    n[i] = [0]*2
    n[i][1] = []

visited = []

for i in range(N-1):
    u[i], v[i], w[i] = list(map(int, input().split()))
    n[u[i]-1][1].append((v[i])*(w[i]%2*2 -1))
    n[v[i]-1][1].append((u[i])*(w[i]%2*2 -1))

def dfs(num):
    visited.append(num)
    for item in n[num][1]:
        if not (abs(item)-1 in visited):
            if item < 0:
                item = -1*item
                n[item-1][0] = n[num][0]
                dfs(item-1)
            else:
                n[item-1][0] = -1 * n[num][0] +1
                dfs(item-1)

dfs(0)

for i in n:
    print(i[0])

### FIXED CODE ###

N = int(input())
u, v, w = [0]*(N-1), [0]*(N-1), [0]*(N-1)
n = [-1] * N
# n[][0] 色　n[][1] 連結先一覧リスト n[][2] mod2 
for i in range(N):
    n[i] = [0]*4
    n[i][1] = []
    n[i][2] = []

for i in range(N-1):
    u[i], v[i], w[i] = list(map(int, input().split()))
    n[u[i]-1][1].append(v[i]-1)
    n[v[i]-1][1].append(u[i]-1)
    n[u[i]-1][2].append(w[i]%2)
    n[v[i]-1][2].append(w[i]%2)

stack = [u[0]-1]

while True:
    num = stack.pop()
    n[num][3] = 1
    for i in range(len(n[num][1])):
        if n[n[num][1][i]][3] == 0:
            stack.append(n[num][1][i])
            if n[num][2][i] == 0:
                n[n[num][1][i]][0] = n[num][0]
            else:
                n[n[num][1][i]][0] = -1 * n[num][0] + 1
    if len(stack) == 0:
        break

for i in n:
    print(i[0])
b = input():
if b == "A":
  print("T")
elif b = "T":
  print("A")
elif b = "G":
  print("C")
elif v = "C":
  print("G")

### FIXED CODE ###

b = input()
if b == "A":
  print("T")
elif b == "T":
  print("A")
elif b == "G":
  print("C")
elif b == "C":
  print("G")
n,k=map(int,input().split())
d=list(input().split())
for i in range(n,100001):
    set_i=set(list(str(i)))
    for j in set_i:
        if s in d:
            break
    else:
        print(i)
        break


### FIXED CODE ###

n,k=map(int,input().split())
d=list(input().split())
ans=n
p=0
for i in range(10*n+1):
    s=str(ans)
    for j in range(len(str(s))):
        if s[j] in d:
            break
    else:
        break
    ans+=1
print(ans)
h,a=map(int,input().split(" "))

if h%a==0:
  print(h/a)
else:
  primt((h//a)+1)

### FIXED CODE ###

h,a = map(int,input().split())
n = -((-h)//a)
print(n)
s = list(input())

for i in range(1, 4):
  c = "R" * i
  if c in s:
    ans = c
    
print(ans)
  

### FIXED CODE ###

s = input()
 
if 'RRR' in s:
  i = 3
elif 'RR' in s:
  i = 2
elif 'R' in s:
  i = 1
else:
  i = 0
print(i)
n,k,q = map(int, raw_input().split())
import numpy as np

vec = np.full(n, k, dtype=int)
for i in range(q):
  ind = np.full(n, 1, dtype=int)
  a = int(raw_input())
  ind[a-1] = 0
  vec = vec - ind
  
print('Yes' if i > 0 in vec else 'No')


### FIXED CODE ###

s = str(raw_input())
w = ['Sunny', 'Cloudy', 'Rainy']
i = w.index(s)
if i < 2:
    print(w[i+1])
else:
    print(w[0])
import collections as c
s=input()
t=input()
d=c.defaultdict(list)
d2=c.defaultdict(list)
for k,v in enumerate(s):
    d[v].append(k)
for k,v in enumerate(t):
    d2[v].append(k)
if list(d.values())==list(d2.values()):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

a=list(sorted(input().split()))[::-1];a.insert(2,"+");print(eval("".join(a)))
s,t=input(),input()
dp=[[0]*(len(t)+1) for i in range(len(s)+1)]
for i in range(len(s)+1):
    for j in range(len(t)+1):
        if i<len(s):
            dp[i+1][j]=max(dp[i+1][j],dp[i][j])
        if j<len(t):
            dp[i][j+1]=max(dp[i][j+1],dp[i][j])
        if i<len(s) and j<len(t):
            dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+(s[i]==t[j]))
ans=""
def move(i,j):
    global dp,ans
    if i==0 or j==0:
        return
    elif dp[i][j]>dp[i-1][j-1] and s[i-1]==t[j-1]:
        ans=s[i-1]+ans
        move(i-1,j-1)
    else:
        if dp[i][j]==dp[i][j-1]:
            move(i,j-1)
        elif dp[i][j]==dp[i-1][j]:
            move(i-1,j)
move(len(s),len(t))
print(ans)

### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(10**7)
s,t=input(),input()
dp=[[0]*(len(t)+1) for i in range(len(s)+1)]
for i in range(len(s)+1):
    for j in range(len(t)+1):
        if i<len(s):
            dp[i+1][j]=max(dp[i+1][j],dp[i][j])
        if j<len(t):
            dp[i][j+1]=max(dp[i][j+1],dp[i][j])
        if i<len(s) and j<len(t):
            dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+(s[i]==t[j]))
ans=""
def move(i,j):
    global dp,ans
    if i==0 or j==0:
        return
    elif dp[i][j]>dp[i-1][j-1] and s[i-1]==t[j-1]:
        ans=s[i-1]+ans
        move(i-1,j-1)
    else:
        if dp[i][j]==dp[i][j-1]:
            move(i,j-1)
        else:
            move(i-1,j)
move(len(s),len(t))
print(ans)
N=int(input())
to = [[] for _ in range(N)]
for _ in range(N-1):
    u, v, w = [int(x) for x in input().split()]
    u -= 1
    v -= 1
    to[u].append([v, w])
    to[v].append([u, w])
ans = [-1] * N
ans[0] = 0
def dfs(v, p=-1, c=0):
    for u, w in to[v]:
        if u == p: continue
        if (w%2 != 0):
            c ^= 1
        ans[u] = c
        dfs(u, v, c)
dfs(0)
for v in ans:
    print(v)


### FIXED CODE ###

N=int(input())
to = [[] for _ in range(N)]
for _ in range(N-1):
    u, v, w = [int(x) for x in input().split()]
    u -= 1
    v -= 1
    to[u].append([v, w])
    to[v].append([u, w])
ans = [-1] * N
ans[0] = 0
q = [0]
while(len(q) != 0):
    v = q.pop()
    for u, w in to[v]:
        if (ans[u] != -1): continue
        ans[u] = (ans[v]+w) % 2
        q.append(u)
for v in ans:
    print(v)
def LCS():
    X = raw_input()
    Y = raw_input()
 
    a, b = len(X), len(Y)
    c1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = X[i]
        c2 = c1+[]
        for j in range(b):
            if e1 == Y[j]:
                c1[j+1] = c2[j] + 1
            elif c1[j+1] < c1[j]:
                c1[j+1] = c1[j]
    return x1[-1]
 
n = input()
for i in range(n):
    print LCS()

### FIXED CODE ###

def LCS():
    X = raw_input()
    Y = raw_input()
 
    a, b = len(X), len(Y)
    c1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = X[i]
        c2 = c1+[]
        for j in range(b):
            if e1 == Y[j]:
                c1[j+1] = c2[j] + 1
            elif c1[j+1] < c1[j]:
                c1[j+1] = c1[j]
    return c1[-1]
 
n = input()
for i in range(n):
    print LCS()
N = int(input())
if N == 1:
    print('Hello World')
else N == 2:
    A = int(input())
    B = int(input())
    print(A+B)

### FIXED CODE ###

N = int(input())
if N == 1:
    print('Hello World')
elif N == 2:
    A = int(input())
    B = int(input())
    print(A+B)
r1,c1,r2,c2=map(int,input().split())
MOD=10**9+7
idx=r2+c2+3
perm=[1]*(idx+1)
for i in range(1,idx+1):
    perm[i]=perm[i-1]*i
    perm[i]%=MOD
def inv_mod(a):
  return pow(a,MOD-2,MOD)

def comb(n,m,p=10**9+7):
    if n < m : return 0
    if n < 0 or m < 0:return 0
    m = min(m, n-m)
    top = bot = 1
    for i in range(m):
        top = top*(n-i) % p
        bot = bot*(i+1) % p
    bot = pow(bot, p-2, p)
    return top*bot % p
def g(i,j):
    return comb(i+j+2,i+1,mod)
def s(n,m):
    return comb(n+m+2, m+1, mod)
res=g(r2,c2)-g(r2,c1-1)-g(r1-1,c2)+g(r1-1,c1-1)

mod = 10**9+7
ans = s(r2,c2) - s(r2, c1-1) - s(r1-1, c2) + s(r1-1, c1-1)
ans %= mod
print(res)

### FIXED CODE ###

r1,c1,r2,c2=map(int,input().split())
MOD=10**9+7
idx=r2+c2+3
perm=[1]*(idx+1)
for i in range(1,idx+1):
    perm[i]=perm[i-1]*i
    perm[i]%=MOD
def inv_mod(a):
  return pow(a,MOD-2,MOD)

def comb(n,m,p=10**9+7):
    if n < m : return 0
    if n < 0 or m < 0:return 0
    m = min(m, n-m)
    top = bot = 1
    for i in range(m):
        top = top*(n-i) % p
        bot = bot*(i+1) % p
    bot = pow(bot, p-2, p)
    return top*bot % p
def g(i,j):
    return comb(i+j+2,i+1,MOD)
def s(n,m):
    return comb(n+m+2, m+1, MOD)
res=g(r2,c2)-g(r2,c1-1)-g(r1-1,c2)+g(r1-1,c1-1)
res%=MOD

ans = s(r2,c2) - s(r2, c1-1) - s(r1-1, c2) + s(r1-1, c1-1)
ans %= MOD
print(res)
N,M = map(int, input().split())
a = [int(input()) for _ in range(M)]
dp = [0]*n
dp[0] = 1
dp[1] =0 if 2 in a else 1
for i in range(2, N+1):
  dp[i] = (dp[i-1] + dp[i-2])%(10**9+7) if i not in a else 0
print(dp[n])

### FIXED CODE ###

N,M = map(int, input().split())
a = set([int(input()) for _ in range(M)])
dp = [0]*(N+1)
dp[0] = 1
dp[1] =0 if 1 in a else 1
for i in range(2, N+1):
  dp[i] = (dp[i-1] + dp[i-2])%(10**9+7) if i not in a else 0
print(dp[N])
n,k= int(input().split())
print(0 if n%k=0 else 1)

### FIXED CODE ###

n,k= map(int,input().split())
print(0 if n%k==0 else 1)
import bisect

n=int(input())
arr=[int(input()) for _ in range(n)][::-1]
LIS = [arr[0]]
for i in range(1,n):
  print(LIS)
  if arr[i] >= LIS[-1]:
    LIS.append(arr[i])
  else:
    LIS[bisect.bisect_left(LIS, arr[i])] = arr[i]
print(len(LIS))

### FIXED CODE ###

#quoted LIS from https://qiita.com/python_walker/items/d1e2be789f6e7a0851e5
import bisect

n=int(input())
arr=[int(input()) for _ in range(n)][::-1]
LIS=[arr[0]]
for i in range(1,n):
  if arr[i]>=LIS[-1]:
    LIS.append(arr[i])
  else:
    LIS[bisect.bisect_right(LIS,arr[i])]=arr[i]
print(len(LIS))
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd, log10
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement, chain
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
from copy import copy, deepcopy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


# https://qiita.com/greenteabiscuit/items/31c46ab3ceac07e749d2


n, m = LI()
graph = [[] for _ in range(m)]
v = [False] * n

for i in range(m):
    a, b = LI()
    graph[a - 1].append(b)
    graph[b - 1].append(a)


def dfs(now, depth):
    if v[now - 1]:
        return 0
    if depth == n-1:
        return 1
    ans = 0
    v[now - 1] = True
    for node in graph[now - 1]:
        ans += dfs(node, depth+1)

    v[now - 1] = False
    # ここが大事.上で探索の一つが終わるからリセットしている.

    return ans


print(dfs(1, 0))


### FIXED CODE ###

#Nはノード数、Mはエッジ数
N, M = map(int, input().split())

path_matrix = []

#無向行列の初期化
for n in range(N):
    path_matrix.append([False] * N)

#まず無向グラフを表す行列を作る
for m in range(M):
    line = map(int, input().split())
    paths = [x - 1 for x in line]
    path_matrix[paths[0]][paths[1]] = True
    path_matrix[paths[1]][paths[0]] = True

#最初はvisited、つまり訪問したことのあるノードはひとつもないので、Falseにする
visited = [False] * N


#再帰関数、ここが難しいかもしれない。
def dfs(now, depth):
    if visited[now]:
        return 0
    if depth == N - 1:
        return 1

    visited[now] = True
    total_paths = 0
    for i in range(0, N):
        if path_matrix[now][i]:
            total_paths += dfs(i, depth + 1)

    visited[now] = False

    return total_paths

print(dfs(0, 0))
x = int(input())

quo = x // 100
rem = u % 100

req = rem // 5

if rem % 5:
  req += 1
  
if req > qum:
  print(0)
else:
  print(1)
  

### FIXED CODE ###

x = int(input())

quo = x // 100
rem = x % 100

req = rem // 5

if rem % 5:
  req += 1
  
if req > quo:
  print(0)
else:
  print(1)