Harryxun/stf_run huggingface dataset:
import sys
from collections import deque

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    h, w, k = nm()
    sy, sx, gy, gx = nm()
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    sx -= 1; sy -= 1
    gx -= 1; gy -= 1
    C = [ns() for _ in range(w)]
    G = [[[10**10]*w for _ in range(h)] for i in range(4)]
    for i in range(4):
        G[i][sy][sx] = 0
    q = deque([(sy, sx, i, 0) for i in range(4)])
    while q:
        y, x, t, c = q.popleft()
        dy, dx = d[t]
        ny = y + dy; nx = x + dx
        if 0 <= ny < h and 0 <= nx < w and C[ny][nx] != '@' and G[t][ny][nx] > G[t][y][x] + (c == 0):
            G[t][ny][nx] = G[t][y][x] + (c == 0)
            if c:
                q.appendleft((ny, nx, t, c-1))
            else:
                q.append((ny, nx, t, k-1))
        for i in range(4):
            if i == t:
                continue
            dy, dx = d[i]
            ny = y + dy; nx = x + dx
            if 0 <= ny < h and 0 <= nx < w and C[ny][nx] != '@' and G[i][ny][nx] > G[t][y][x] + 1:
                G[i][ny][nx] = G[t][y][x] + 1
                q.append((ny, nx, i, k-1))
    ans = min(G[i][gy][gx] for i in range(4))
    print(ans if ans < 10**10 else -1)
    return

solve()


### FIXED CODE ###

import sys
from collections import deque

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))


def solve():
    h, w, k = nm()
    sy, sx, gy, gx = nm()
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    sx -= 1; sy -= 1
    gx -= 1; gy -= 1
    C = [ns() for _ in range(h)]
    G = [[10**7]*w for _ in range(h)]
    G[sy][sx] = 0
    q = deque([(sy, sx)])
    while q:
        y, x = q.popleft()
        for i in range(4):
            dy, dx = d[i]
            ny, nx = y, x
            for _ in range(k):
                ny += dy; nx += dx
                if ny < 0 or h <= ny or nx < 0 or w <= nx:
                    break
                if C[ny][nx] == '@' or G[ny][nx] <= G[y][x]:
                    break
                if G[ny][nx] > G[y][x] + 1:
                    G[ny][nx] = G[y][x] + 1
                    q.append((ny, nx))
    ans = G[gy][gx]
    print(ans if ans < 10**7 else -1)
    return

solve()
N = int(input())
C = list(input())
ans = 0
r = 0
l = N - 1
while r+1 != l:
    while True:
        if C[r] != C[l]:
            ans += 1
            break
        else:
            l -= 1
            if r+1 == l:
                break
    r += 1
print(ans)


### FIXED CODE ###

N = int(input())
C = list(input())
ans = 0
r = 0
l = N - 1
while r < l:
    if C[r] == 'W':
        while True:
            if C[l] == 'R':
                ans += 1
                l -= 1
                break
            else:
                l -= 1
                if r == l:
                    break
    r += 1
print(ans)
n, k = map(int, input().split())
v = list(map(int, input().split()))

def solve(L, R, D):
  # print((L, R, D))
  LL = v[:L] if L > 0 else []
  RR = v[-R:] if R > 0 else []
  targetList = LL + RR
  # print(targetList)
  targetList.sort()
  ret = 0
  newList = targetList.copy()
  for i in range(min(len(targetList), D)):
    if targetList[i] < 0:
      del newList[0]
  ret = sum(newList)
  # print((ret, newList))
  return ret

result = 0
for i in range(min(k+1, n+1)):
  for j in range(min(k+1, n+1)-i):
    t = solve(i, j, k-i-j)
    if t > result:
      result = t

print(result)

### FIXED CODE ###

n, k = map(int, input().split())
v = list(map(int, input().split()))

def solve(L, R, D):
  # print((L, R, D))
  LL = v[:L] if L > 0 else []
  RR = v[-R:] if R > 0 else []
  targetList = LL + RR
  # print(targetList)
  targetList.sort()
  ret = 0
  newList = targetList[::]
  for i in range(min(len(targetList), D)):
    if targetList[i] < 0:
      del newList[0]
  ret = sum(newList)
  # print((ret, newList))
  return ret

result = 0
for i in range(min(k+1, n+1)):
  for j in range(min(k+1, n+1)-i):
    t = solve(i, j, k-i-j)
    if t > result:
      result = t

print(result)
#!/usr/bin/env python3
# import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
# inf = float('inf') ;mod = 10**9+7
# mans = inf ;ans = 0 ;count = 0 ;pro = 1
from heapq import heappush,heappop

n,q=map(int,input().split())
STX=[tuple(map(int,input().split())) for i in range(n)]
D=[int(input()) for i in range(q)]
event=[]
for si,ti,xi in STX:
  event.append((si-xi,0,xi))
  event.append((ti-xi,-1,xi))
for di in D:
  event.append((di,1,di))
event.sort()
hq=[]; S=set()
for time, query, number in event:
  if query == 0:
    heappush(hq,number)
    S.add(number)
  elif query == -1:
    S.remove(number)
  else:
    while hq and hq[0] not in S:
      heappop(hq)
    if not hq:
      print(-1)
    else:
      print(hq[0])




### FIXED CODE ###

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,q=map(int,input().split())
STX=[tuple(map(int,input().split())) for i in range(n)]
D=[int(input()) for i in range(q)]
event=[]
for si,ti,xi in STX:
  event.append((si-xi,0,xi))
  event.append((ti-xi,-1,xi))
for di in D:
  event.append((di,1,di))
event.sort()
hq=[]; S=set()
for time, query, number in event:
  if query == 0:
    heapq.heappush(hq,number)
    S.add(number)
  elif query == -1:
    S.remove(number)
  else:
    while hq and hq[0] not in S:
      heapq.heappop(hq)
    if not hq:
      print(-1)
    else:
      print(hq[0])
N, K = map(int, input().split())
height_list = list(map, input().split())
len_height_list = len(height_list)
count = 0

for i in range(len_height_list):
    if height_list[i] >= K:
        count += 1
        
print(count)

### FIXED CODE ###

N, K = map(int, input().split())
height_list = list(map(int, input().split()))
len_height_list = len(height_list)
count = 0

for i in range(len_height_list):
    if height_list[i] >= K:
        count += 1
        
print(count)
A, B = map(int, input().split())

print(A*B*10//10)

### FIXED CODE ###

A, B = input().split()

A = int(A)
B = int(float(B) * 100 + 0.5)
ans = A * B // 100

print(ans)
S = input()
N = len(S)
ans = 0
for i in range(N):
	for j in range(i, N):
		if all('ACGT'.count(c) == 1 for c in S[i : j + 1]):
ans = max(ans, j - i + 1)
print(ans)

### FIXED CODE ###

S = input()
N = len(S)
ans = 0
for i in range(N):
    for j in range(i, N):
        if all('ACGT'.count(c) == 1 for c in S[i : j + 1]):
            ans = max(ans, j - i + 1)
print(ans)
h,w = map(int,input().split())
l = [list(map(int,input().split())) for i in range(10)]
a = [list(map(int,input().split())) for i in range(h)]
ans = 0
l = np.array(l)
for rep in range(10):
    for i in range(10):
        for j in range(10):
            for k in range(10):
                if l[i][j] > l[i][k]+l[k][j]:
                    l[i][j] = l[i][k]+l[k][j]
num = [i[1] for i in l] + [0]
for i in a:
    for j in i:
        ans += num[j]
print(ans)


### FIXED CODE ###

import numpy as np
h,w = map(int,input().split())
l = [list(map(int,input().split())) for i in range(10)]
a = [list(map(int,input().split())) for i in range(h)]
ans = 0
l = np.array(l)
for rep in range(10):
    for i in range(10):
        for j in range(10):
            for k in range(10):
                if l[i][j] > l[i][k]+l[k][j]:
                    l[i][j] = l[i][k]+l[k][j]
num = [i[1] for i in l] + [0]
for i in a:
    for j in i:
        ans += num[j]
print(ans)
list1 = []
while True:
    x = str(input())
    if x == '0':
        break
    else:
        for i in x:
            result += int(x[i])
            list1.append(result)
sum(list1)

### FIXED CODE ###

list1 = []
while True:
    x = str(input())
    if x == '0':
        break
    else:
        result=0
        for i in x:
            result += int(i)
        list1.append(result)
            
for i in list1:
    print(i)
S = input()

# 1 <= |S| <= 26
# lowercase

import sys
import copy

if len(S) == 26:
    if S == "zyxwvutsrqponmlkjihgfedcba":
        ans = "-1"
        print(ans)
        sys.exit()

    else:
        original = copy.copy(S)
        np = ""
        for i in range(0, len(S)-2):
            # print(i)
            if S[i] < S[i+1]:
                np += S[i]

            else:
                i = i - 1
                for j in reversed(range(i, len(S))):
                    # print("checking:", j)
                    # print("S[i], S[j]", S[i], ",", S[j])
                    if S[i] < S[j]:
                        np = np[:-1] + S[j]
                        tmp = S[i]
                        S = S[:i-1] + S[j] + S[i+1:]
                        S = S[:j-1] + tmp + S[j+1:]
                        # S[i+1:] = S[:i] + "".join(list(reversed(S[i+1:])))
                        # S = S[:i] + 
                        np += "".join(list(reversed(S[i+1:])))
                        break

        # print("np", np)
        for b in range(0, 27):
            if np[b] != original[b]:
                print(np[:b+1])
                exit()

        print(S)

            
else:
    hist = set(S)
    for c in range(0, 27):
        cand = chr(c+ord('a'))
        if cand not in hist:
            print(S+cand)
            sys.exit()

### FIXED CODE ###

S = input()

# 1 <= |S| <= 26
# lowercase

import sys
import copy

def next_permutation(a):
    for i in reversed(range(len(a) - 1)):
        if a[i] < a[i + 1]:
            break
    else:
        return False

    j = next(j for j in reversed(range(i + 1, len(a))) if a[i] < a[j])
    a[i], a[j] = a[j], a[i]
    a[i + 1:] = reversed(a[i + 1:])
    return True

if len(S) == 26:
    sl = list(S)
    if next_permutation(sl):
        np = "".join(sl)
        for b in range(0, 26):
            if np[b] != S[b]:
                print(np[:b+1])
                exit()

    else:
        print(-1)
        exit()
else:
    hist = set(S)
    for c in range(0, 27):
        cand = chr(c+ord('a'))
        if cand not in hist:
            print(S+cand)
            sys.exit()
import math
MOD = 10 ** 9 + 7

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

if (X + Y) % 3 != 0:
    print (0)
    exit()

x = X - (X + Y) // 3
y = Y - (X + Y) // 3

if x < y:
    x, y = y, x

tmp = math.factorial(y)

ans = 1
for i in range(x + 1, x + y + 1):
    ans *= i
    ans %= MOD

def modinv(a, m): #mod. m でのaの逆元 a^{-1}を計算する
    b = m
    u = 1
    v = 0
    while b:
        t = a//b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    
    u %= m
    if u < 0:
        u += m
    return u

tmp = modinv(tmp, MOD)

ans *= tmp

ans %= MOD

print (ans)

### FIXED CODE ###

import math
MOD = 10 ** 9 + 7

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

if (X + Y) % 3 != 0:
    print (0)
    exit()

x = X - (X + Y) // 3
y = Y - (X + Y) // 3

if x < 0 or y < 0:
    print (0)
    exit()

if x < y:
    x, y = y, x

# tmp = math.factorial(y)
tmp = 1
for i in range(1, y + 1):
    tmp *= i
    tmp %= MOD

ans = 1
for i in range(x + 1, x + y + 1):
    ans *= i
    ans %= MOD

def modinv(a, m): #mod. m でのaの逆元 a^{-1}を計算する
    b = m
    u = 1
    v = 0
    while b:
        t = a//b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    
    u %= m
    if u < 0:
        u += m
    return u

tmp = modinv(tmp, MOD)

ans *= tmp

ans %= MOD

print (ans)

# print (x, y)
n,k=map(int,input())
s=input()
t=s.pop(k-1)
s.insert(k-1,t.lower())
print(s)

### FIXED CODE ###

n,k=map(int,input().split())
s=list(input())
t=s.pop(k-1)
s.insert(k-1,t.lower())
print("".join(s))
a=input(); b=input();
print a*b; print a*2+b*2;

### FIXED CODE ###

a,b=map(int,raw_input().split())
if 0<=b<=100 and 0<=b<=100:
    print a*b,
    print a*2+b*2
else:
    pass
import sys
sys.setrecursionlimit(200000)
h,w = map(int, input().split())
s = [input() for _ in range(h)]
dx = [0,0,1,-1]
dy = [1,-1,0,0]
def dfs(x,y):
    global check
    global was
    was[y][x] = 1
    if s[y][x] == "#":
        check[0] += 1
    else:
        check[1] += 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if ny >= 0 and ny >= 0 and nx < w and ny < h and s[ny][nx] != s[y][x] and not was[ny][nx]:
            dfs(nx,ny)
ans = 0
was = [[0 for i in range(h)] for j in range(w)]
for i in range(h):
    for j in range(w):
        if not was[i][j]:
            check = [0,0]
            dfs(i,j)
            ans += check[0] * check[1]
print(ans)

### FIXED CODE ###

h,w = map(int, input().split())
s = []
for i in range(h):
    s.append(input())
import sys
sys.setrecursionlimit(200000)
dy = [0,0,1,-1]
dx = [1,-1,0,0]
def dfs(y,x):
    global check
    global was
    was[y][x] = 1
    if s[y][x] == "#":
        check[0] += 1
    else:
        check[1] += 1
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if nx >= 0 and ny >= 0 and nx < w and ny < h and s[ny][nx] != s[y][x] and not was[ny][nx]:
            dfs(ny,nx)
ans = 0
was = [[0 for i in range(w)] for j in range(h)]
for i in range(w):
    for j in range(h):
        if not was[j][i]:
            check = [0,0]
            dfs(j,i)
            ans += check[0] * check[1]
print(ans)
N = int(input())
number = [1,2,3,4,5,6,7,8,9]
for B in number :
  for A in N :
  if A / 9 < 10 and A % B :
    print("Yes")
    
else :
  print("No")
    

### FIXED CODE ###

N = int(input())
number = []
for a in range(1,10):
    for b in range(1,10):
        number.append(b*a)
if N in number :
    print("Yes")
else :
    print("No")
# ABC150 D
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
from fractions import gcd
def lcm(x, y):
    """
    xとyの最小公倍数を求める。

    Parameters
    ----------
    x,y : int
        自然数

    Returns
    -------
        最小公倍数：int

    """
    return (x * y) // gcd(x, y)
n,m=nm()
a=nl()
b=[]
lc=[]

# for i in range(n):
#     b.append(a[i]//2)
# print(a)
for i in range(n):
    a[i]//=2
# print(a)
t=0
for i in range(n-1):
    if i==0:
        t=lcm(a[i],a[i+1])
        lc.append(t)
    elif i!=0:
        t=lcm(lc[i-1],a[i+1])
        # t=min(lc[i-1],t)
        lc.append(t)
# print(lc)
# print(max(a))
# ans=(m-max(a)//max(lc))//2
ans=0
ans=(m+max(a))//max(lc)
if ans%2==1:
    ans//=2
    ans+=1
else:
    ans//=2
print(ans)



### FIXED CODE ###

# ABC150 D
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
from fractions import gcd
from math import ceil
def lcm(x, y):
    return (x * y) // gcd(x, y)
n,m=nm()
a=nl()
ans=0
a=[x//2 for x in a] 

lcm_v=a[0]
for i in range(n):
    lcm_v=lcm(lcm_v,a[i])
ok_flg=[(lcm_v//i)%2==1 for i in a]
if all(ok_flg):
    ans=((m//lcm_v)+1)//2
print(ans)
S = int(input())

mod = 10**9+7

def dfs_memo(n):
    memo = [0]*(n+1)
    memo[3] = 1

    def dfs(n):
        if n < 3:
            return 0
        elif memo[n] != 0:
            return memo[n]
        memo[n] = dfs(n-1)+dfs(n-3)
        return memo[n]
    return dfs(n)

if S <3:
    print(0)
else:
    print(dfs_memo(S)%mod)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)
S = int(input())

mod = 10**9+7

def dfs_memo(n):
    memo = [0]*(n+1)
    memo[3] = 1

    def dfs(n):
        if n < 3:
            return 0
        if memo[n] != 0:
            return memo[n]
        memo[n] = dfs(n-1)+dfs(n-3)
        return memo[n]
    return dfs(n)

if S <3:
    print(0)
else:
    print(dfs_memo(S)%mod)
import sys
s = sys.stdin.readline().rstrip()
q = int(sys.stdin.readline().rstrip())

for _ in range(q):
    t = sys.stdin.readline().rstrip()
    if t == '1':
        s = s[::-1]
    else:
        t, f, c = t.split()
        if f == '1':
            s = c + s
        else:
            s = s + c

print(s)

### FIXED CODE ###

s = input()
if s == 'AAA' or s == 'BBB':
    print('No')
else:
    print('Yes')
x, y = map(int, input().split())
print x * y, 2 * (x + y)

### FIXED CODE ###

(x, y) = map(int, raw_input().split())
print x * y, 2 * (x + y)
import sys
N = int(input())
for i in range(1, 10):
    for j in range(1, 10):
        if i * j == N:
            print('Yes')
            sys.exit(1)
print('No')


### FIXED CODE ###

N = int(input())
no=0
for i in range(1, 10):
    for j in range(1, 10):
        if ((i * j) == N):
            print('Yes')
            no += 1
            break
    if no == 1:
        break
if no==0:
    print('No')
N,M = map(int,input().split())
a = list(map(int,input().split()))
a = sorted(a,reverse=True)
for m in range(M):
  max_=max(a[:2])
  a.remove(max_)
  if max_//2<a[0]:
    a.insert(1,max_//2)
  else:
    a.insert(0,max_//2)
print(sum(a))

### FIXED CODE ###

from heapq import heapify,heappush,heappop

N,M = map(int,input().split())
a = list(map(int,input().split()))
a = [(-x, x) for x in a]

heapify(a)

for m in range(M):
  max_ = heappop(a)
  a_ = max_[1]//2
  heappush(a,(-a_,a_))

ans=0
for a_ in a:
  ans+=a_[1]
print(ans)
import math
 
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
 
if N == K:
    print(1)
    quit()
else:
    one_index = A.index(1)
    l = one_index #1の左側にある数字の数
    r = N - one_index - 1 #1の右側にある数字の数
 
    assert N % 3 == 0

### FIXED CODE ###

input_line = input().split()

num_array = int(input_line[0])
num_equal = int(input_line[1])

input_line = input() # 無視

equalized = 1
i = 0
while equalized < num_array:
    equalized += (num_equal - 1)
    # print(i, equalized)
    i += 1

print(str(i))
a,b,t=map(int,input().split())

print(t//a*b

### FIXED CODE ###

a,b,t=map(int,input().split())
 
print(t//a*b)
a = input()
if a[0]*a[1]%2==0:
  print("Even")
else:
  print("Odd")

### FIXED CODE ###

b, c = map(int, input().split())
if b*c%2==0:
  print("Even")
else:
  print("Odd")
a = int(input())
b = int(input())
c = list(map(int,input().split()))
sum = 0
for i in range c:
  sum = sum + i
count = 0
vote = (1/(4*b))*sum
for j in c:
  if j>=vote:
    count = count + 1
if count>=b:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a,b = map(int,input().split())
c = list(map(int,input().split()))
sum = 0
for i in c:
  sum = sum + i
vote = (1/(4*b))*sum
count = 0
for j in c:
  if j>=vote:
    count = count + 1

if count>=b:
  print("Yes")
else:
  print("No")
from decimal import *
A,B = map(int, input().split())
A = Decimal(A)
B = Decimal(B)

print(Decimal((A*B)/1))

### FIXED CODE ###

import sys
S, T = map(str, input().split())
 
S1 = int(S)
T1 = T.replace(".", "")


print(S1*int(T1)//100)
# import math
# from itertools import permutations as permus
# from fractions import gcd
# from collections import deque
from collections import Counter

# import numpy as np
# import scipy as scp

# 入力の受け取り
n = int(input())
arrN = []
for _ in range(n):
    arrN += [input()]  #table.append(input())とも書ける
m = int(input())
arrM = []
for _ in range(m):
    arrM += [input()]  #table.append(input())とも書ける

countaN = Counter(arrN)
countaM = Counter(arrM)
countaAns = countaN - countaM

s,ans = countaAns.most_common()[0]

print(ans)

### FIXED CODE ###

# import math
# from itertools import permutations as permus
# from fractions import gcd
# from collections import deque
from collections import Counter

# import numpy as np
# import scipy as scp

# 入力の受け取り
n = int(input())
arrN = []
for _ in range(n):
    arrN += [input()]  #table.append(input())とも書ける
m = int(input())
arrM = []
for _ in range(m):
    arrM += [input()]  #table.append(input())とも書ける

countaN = Counter(arrN)
countaM = Counter(arrM)
countaAns = countaN - countaM

if len(countaAns) !=0:
    s,ans = countaAns.most_common()[0]
else:
    ans = 0

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


if x-r :
    print("No")
elif x + r :
    print ("No")
elif y-r :
    print ("No")
elif y+r :
    print ("No")
else:
    print ("Yes"


### FIXED CODE ###

W,H,x,y,r = map(int, input().split())
if x-r < 0 or x+r > W or y-r < 0 or y+r > H:
    print("No")
else:
    print("Yes")
n=int(input())
m=map(int,input().split())
a=[0 for i in range(100001)]
x=0
y=0
for i in m:
    a[i]+=1
for i in range(len(a)):
    if a[i]>=2:
        x=y
        y=i

ans=x*y
print(ans)


### FIXED CODE ###

n=int(input())
a=map(int,input().split())
a=sorted(a)
a=list(reversed(a))
h,w=0,0
tmp=0
f=0
for x in a:
    if tmp==x:
        if w!=0:
            h=x
            break
        else:
            w=x
            tmp=0
            continue
    tmp=x
print(w*h)
x = input()
if x == "7"or"5"or"3"
    print("YES")
else:
    print("NO")

### FIXED CODE ###

x = input()
if x == "7"or x=="5"or x=="3":
    print("YES")
else:
    print("NO")
X = input()

if X >= 40:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

X = input()

X = int(X)

if X >= 30:
    print('Yes')
else:
    print('No')
import math
N, K = map(int,input().split())

for i in range(1, K+1):
    ans = math.factorial(N - K + 1) // math.factorial(N - K + 1 - i) // math.factorial(i)
    ans *= math.factorial(K - 1) // math.factorial(K - i) // math.factorial(i - 1)
    ans %= 10 ** 9 + 7
    print(ans)


### FIXED CODE ###

N, K = map(int,input().split())
ans = N-K+1
print(ans)
for i in range(2, K+1):
    ans = ans * (N-K+2-i) * (K+1-i) // (i - 1) // i
    print(ans % (10 ** 9 + 7))
n=input()
print(n+n**2+n**3)

### FIXED CODE ###

n=int(input())
print(n+n**2+n**3)
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]

from functools import lru_cache
@lru_cache(maxsize=None)
def fibo(n):
    if n in A:
        return 0
    elif n == 0 or n == 1:
        return 1
    return fibo(n-1) + fibo(n-2)

print(fibo(N) % 1_000_000_007)

### FIXED CODE ###

N, M = map(int, input().split())
A = set([int(input()) for i in range(M)])
t = 10**9+7
import sys
sys.setrecursionlimit(500000)
from functools import lru_cache
@lru_cache(maxsize=None)
def fibo(n):
    if n in A:
        return 0
    elif n == 0 or n == 1:
        return 1
    return (fibo(n-2) + fibo(n-1)) % t
print(fibo(N) % t)
def get(num):
    n=0
    is_prime=[0]*200050
    for i in range(0,num+1):
        is_prime[i]=True
    is_prime[0]=is_prime[1]=False
    for i in range(2,num+1):
        if(is_prime[i]):
            n+=1
            for j in range(2*i,num+1,i):
                is_prime[j]=False
    return n

while True:
    try:
        a=map(int,raw_input().strip().split())
        b=a[0]
        if(b==0):
            break
        p=get(2*b)-get(b)

#        p=0
#        for i in range(b+1,2*b+1):
#            if(judge(i)):
#                p+=1
        print(p)
    except EOFError:
        break



### FIXED CODE ###

def get(num):
    n=0
    is_prime=[0]*300050
    for i in range(0,num+1):
        is_prime[i]=True
    is_prime[0]=is_prime[1]=False
    for i in range(2,num+1):
        if(is_prime[i]):
            n+=1
            for j in range(2*i,num+1,i):
                is_prime[j]=False
    return n

while True:
    a=map(int,raw_input().strip().split())
    b=a[0]
    if(b==0):
        break
    p=get(2*b)-get(b)

#        p=0
#        for i in range(b+1,2*b+1):
#            if(judge(i)):
#                p+=1
    print(p)