Harryxun/stf_run huggingface dataset:
import math


class Comb:
    m_vals = []
    _mod = 1_000_000_007
    _mod2 = 1_000_000_005

    def __init__(self, n: int, r: int):
        m_ls = [1] * (r + 1)

        for i,j in zip(range(n, 0, -1), range(1, r+1)):
            m_ls[j] = (m_ls[j-1]*i * pow(j, self._mod2, self._mod)) % self._mod

        self.m_vals = m_ls

    def vv(self, x):
        return self.m_vals[x]


def main():
    n, a, b = map(int, input().split())
    _mod = 1_000_000_007
    cmb = Comb(n,b)
    all = pow(2,n, _mod) -1
    ans = all + (_mod - cmb.vv(a)) + (_mod - cmb.vv(b))
    ans %= _mod

    print(ans)


main()


### FIXED CODE ###


def create_array(n: int, r: int, mod, mod2):
    m_ls = [1] * (r + 1)

    for i, j in zip(range(n, 0, -1), range(1, r + 1)):
        m_ls[j] = (m_ls[j - 1] * i * pow(j, mod2, mod)) % mod
    return m_ls


def main():
    n, a, b = map(int, input().split())
    _mod = 1000000007
    _mod2 = 1000000005

    m_ls = create_array(n, b, _mod, _mod2)

    _all_cnts = pow(2, n, _mod) - 1
    ans = _all_cnts + (_mod - m_ls[a]) + (_mod - m_ls[b])
    ans %= _mod

    print(ans)


main()
import numpy as np
N, M = map(int, input().split())
s, c = [], []
for i in range(M):
  tmp_s, tmp_c = map(int, input().split())
  s.append(tmp_s)
  c.append(tmp_c)

flag = 0
v_set = np.zeros(N)
#print(v_set)
for i in range(M):
  if len(v_set) != 1 and s[i] == 1 and c[i] == 0:
    flag = 0
    break
  else:
    if v_set[s[i]-1] == 0 or v_set[s[i]-1] == c[i]:
      v_set[s[i]-1] = c[i]
      flag = 1
    else:
      flag = 0
      break
if flag == 0:
  print(-1)
else:
  print(v_set)
  print(str(int(v_set[0]))+str(int(v_set[1]))+str(int(v_set[2])))
  

### FIXED CODE ###

import numpy as np
N, M = map(int, input().split())
s, c = [], []
for i in range(M):
  tmp_s, tmp_c = map(int, input().split())
  s.append(tmp_s)
  c.append(tmp_c)

v_set = [999 for i in range(N)]
if N == 1:
  if M == 0:
    print(0)
  else:
    for i in range(M):
      if v_set[0] == 999 or v_set[0] == c[i]:
        v_set[0] = c[i]
      else:
        v_set[0] = -1
        break
    print(v_set[0])
elif N >= 2:
  for i in range(M):
    if v_set[s[i]-1] == 999 or v_set[s[i]-1] == c[i]:
      v_set[s[i]-1] = c[i]
    else:
      v_set[0] = 0
      break
  if v_set[0] == 0:
    print(-1)
  else:
    if v_set[0] == 999:
      v_set[0] = 1
    for i in range(1,N):
      if v_set[i] == 999:
        v_set[i] = 0
    out = ''
    for i in range(N):
      out += str(int(v_set[i]))
    print(out)
n=int(input().split())
a=n[0]
b=n[1]
S=a*b
L=(2*a)+(2*b)


### FIXED CODE ###

#cording; UTF-8
a,b=[int(x) for x in input().split()]

S = a*b
L = 2*(a+b)
print(S,L)
N, W = [int(i) for i in input().split()]
value, weight = [0] * (N + 1), [0] * (N + 1)
for i in range(1, N + 1):
    value[i], weight[i] = [int(i) for i in input().split()]
sum_value = sum(value)
dp = [[float("inf")] * (sum_value + 1) for _ in range(N + 1)]
dp[0][0] = 0

#%%

for i in range(1, N + 1):
    for j in range(sum_value + 1):
        if j >= value[i]:
            dp[i][j] = min(dp[i][j], weight[i] + dp[i -1][j - value[i]])
        else:
            dp[i][j] = dp[i -1][j]
        
ans = 0
for i in range(sum_value + 1):
    if dp[N][i] == W:
        ans = i

print(ans)


### FIXED CODE ###

N, W = [int(i) for i in input().split()]
weight, value = [0] * (N), [0] * (N)
for i in range(N):
    weight[i], value[i] = [int(i) for i in input().split()]

#%%

sum_value = sum(value)
dp = [[float("inf")] * (sum_value + 1) for _ in range(N + 1)]
dp[0][0] = 0

#%%

for i in range(N):
    for j in range(sum_value + 1):
        if j >= value[i]:
            dp[i + 1][j] = min(weight[i] + dp[i][j - value[i]], dp[i + 1][j])
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

#%%

ans = 0
for i in range(sum_value + 1):
    if dp[N][i] <= W:
        ans = i
        
print(ans)
import math
N = int(input())
asiba = list(map(int,input().split()))
dp =[math.inf] *N

dp[0]=0
dp[1]=abs(asiba[1]-asiba[0])

for i in range(2,N):
    dp[i] = min(dp[i-2]+abs(asiba[i]-asiba[i-2]),dp[i])
    dp[i] = min(dp[i-1]+abs(asiba[i]-asiba[i-1]),dp[i])
print(dp[N-1])

### FIXED CODE ###

N = int(input())
asiba = list(map(int,input().split()))
dp =[10**10] *N

dp[0]=0
dp[1]=abs(asiba[1]-asiba[0])

for i in range(2,N):
    dp[i] = min(dp[i-2]+abs(asiba[i]-asiba[i-2]),dp[i])
    dp[i] = min(dp[i-1]+abs(asiba[i]-asiba[i-1]),dp[i])
print(dp[N-1])
h,w=map(int,input().split())
a=input()
b=input()
print("#"*(h+w))
print("#"+a+"#")
print("#"+b+"#")
print("#"*(h+w))

### FIXED CODE ###

h,w=map(int,input().split())
print("#"*(w+2))
for i in range(h):
    a=input()
    print("#"+a+"#")
print("#"*(w+2))
import numpy as np

r = int(input())
print(r*2*np.pi)

### FIXED CODE ###

r = int(input())
print(r*2*3.141)
import numpy as np
n, m, c = map(int, input().split())
b = list(map(int, input().split()))
A = [[int(i) for i in input().split()] for i in range(n)]
B = np.array(b).reshape(m,1)
cnt = 0
for i in range(m):
    x = np.dot(A[i], B)+c
    if x >0:
    	cnt += 1

print(cnt)

### FIXED CODE ###

import numpy as np
n, m, c = map(int, input().split())
b = list(map(int, input().split()))
A = [[int(i) for i in input().split()] for i in range(n)]
B = np.array(b).reshape(m,1)
cnt = 0
for i in range(n):
    x = np.dot(A[i], B)+c
    if x >0:
    	cnt += 1

print(cnt)
i=1
while 1:
??a=input()
??if int(a)==0:break
 print(f'Case {i}: {a}')
 i+=1

### FIXED CODE ###

import sys
i=1
for e in sys.stdin:
 if'0\n'==e:break
 print(f'Case {i}: {e[:-1]}');i+=1
import sys
input = sys.stdin.readline

n = int(input())
s = input()

left = 0
right = s.count(".")
res = min(right, s.count("#"))
for i in range(n):
    if s[i] == "#":
        left += 1
    else:
        right -= 1
    res = min(res, left+right)

print(res)

### FIXED CODE ###

a, b, c = map(int, input().split())
if a < c and b > c:
    print("Yes")
elif b < c and a > c:
    print("Yes")
else:
    print("No")
X, Y = map(int, input().split())
ans = 'No'

for i in X:
    j = X - i
    if (i * 2 + j * 4) == Y:
        ans = 'Yes'

print(ans)

### FIXED CODE ###

X, Y = map(int, input().split())
ans = 'No'

for i in range(X+1):
    j = X - i
    if (i * 2 + j * 4) == Y:
        ans = 'Yes'

print(ans)
n = int(input())
w = input().split(" ")

a = []
k = False
for i in range(n):
    a.append(int(w[i]))
    if a[i] < 0:
       a[i] *= -1
       k = not(k)
    if i == 1:
        min = a[i]
    if a[i] < min:
        min = a[i]
2
sum = sum(a)
if k:
    sum -= min
print(sum)


### FIXED CODE ###

n = int(input())
w = input().split(" ")

a = []
m = 0
k = False
for i in range(n):
    a.append(int(w[i]))
    if a[i] < 0:
        a[i] *= -1
        k = not (k)
    if i == 0:
        m = a[i]
    if a[i] < m:
        m = a[i]

sum = sum(a)
if k:
    sum -= m*2
print(sum)
import heapq

n,m=map(int,input().split())
mm=10*5+1
c=[[0] for i in range(mm)]

for i in range(n):
  a,b=map(int,input().split())
  c[a].append(b)

#print(c)

ans=0
h=[]
for i in reversed(range(m)):
  d=m-i
  h+=list(map(lambda x:-x, c[d]))+[0]
  heapq.heapify(h)
  ans+=-heapq.heappop(h)

print(ans)

### FIXED CODE ###

import heapq

n,m=map(int,input().split())
mm=10**5+5
c=[[0] for i in range(mm)]

for i in range(n):
  a,b=map(int,input().split())
  c[a].append(b)

#print(c)

ans=0
h=[]
for i in reversed(range(m)):
  d=m-i
  for j in c[d]:
    heapq.heappush(h,-j)
  #heapq.heapify(h)
  ans+=-heapq.heappop(h)

print(ans)
t = input()
t = list(t)
count = 1
while(True):
    count = 0
    for i in range(len(t)):
        if t[i] == "?":
            count = count + 1
            if t[i+1] == "P":
                t[i] = 'D'
            elif t[i+1] == "D":
                t[i] = 'P'
    if count == 0:
        break
ans = "".join(t)
print(ans)

### FIXED CODE ###

t = input()
t = list(t)

for i in range(len(t)):
    if t[i] == "?":
        t[i] = 'D'
ans = "".join(t)
print(ans)
N, T = [int(i) for i in input().split(" ")]
c = []
t = []

for i in range(N):
    t = [int(i) for i in input().split(" ")]
    if t[1] <= T:
        c.append(t[0])
        t.append(t[1])

print(min(c))

### FIXED CODE ###

N, T = [int(i) for i in input().split(" ")]
c = []
t = []

for i in range(N):
    t = [int(i) for i in input().split(" ")]
    if t[1] <= T:
        c.append(t[0])
        t.append(t[1])

if c == []:
    print("TLE")
else:
    print(min(c))
import math
print("{:.6f} {:.6f}".format(r ** 2 * math.pi, 2 * r * math.pi))

### FIXED CODE ###

a = float(input())
import math
print("{:.5f} {:.5f}".format(a ** 2 * math.pi, 2 * a * math.pi))
N, K = map(int, input().split())
A = list(map(int, input().split()))

A = sorted([a for a in A if a < K])
N = len(A)
S = sum(A)

# あああああああああああああああああああ＼(＾o＾)／
if S - A[0] < K:
    print(0)
    exit()

l, r = -1, N
while r - l > 1:
    m = (l + r) // 2
    B = A[:m] + A[m + 1:]

    if S - A[m] < K - A[m]:
        l = m
        continue

    dp = [False] * (K + 1)
    dp[0] = True
    flg= False

    for i in range(N - 1):
        for j in range(K + 1)[::-1]:
            if B[i] > j:
                continue
            else:
                dp[j] = dp[j - B[i]]

            if dp[j] and K-A[m] <= j < K:
                r = m
                flg = True
                break
        if flg:
            flg = False
            break
    else:
        l = m

print(r)


### FIXED CODE ###

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

A = sorted([a for a in A if a < K])
N = len(A)
S = sum(A)

# あああああああああああああああああああ＼(＾o＾)／
if S < K:
    print(N)
    exit()
elif S - A[0] < N:
    print(0)
    exit()

l, r = -1, N
while r - l > 1:
    m = (l + r) // 2
    B = A[:m] + A[m + 1:]

    if S - A[m] < K - A[m]:
        l = m
        continue

    dp = [False] * (K + 1)
    dp[0] = True
    flg= False

    for i in range(N - 1):
        for j in range(K + 1)[::-1]:
            if B[i] > j:
                continue
            else:
                dp[j] = dp[j - B[i]]

            if dp[j] and K-A[m] <= j < K:
                r = m
                flg = True
                break
        if flg:
            flg = False
            break
    else:
        l = m

print(r)
n=int(input())
import bisect as b
n=int(input())
ans=1
clist=[int(input())]
for i in range(n-1):
    next=int(input())
    pos=b.bisect_left(clist,next)
    if pos==0:
        clist=[next]+clist
        ans+=1
    else:
        clist[pos-1]=next
print(ans)


### FIXED CODE ###

import bisect as b
from collections import deque
n=int(input())
ans=1
clist=deque([int(input())])
for i in range(n-1):
    next=int(input())
    pos=b.bisect_left(clist,next)
    if pos==0:
        clist.appendleft(next)
        ans+=1
    else:
        clist[pos-1]=next
print(ans)
a, b, c = map(int, input().sprit())
print(min(c, b//a))

### FIXED CODE ###

a,b,c = map(int, input().split())
print(min(c, b//a))
N=int(input())
D=list(map(int,input().split()))
D.sort()
mi=D[0]
ma=D[N-1]
point=0
for j in range(mi,ma+1): #Kはj
  i,s=0
  while D[i]<j and s<N//2:
    i+=1
    s+=1
  if s==N//2:
    point+=1
print(point)
    
  


### FIXED CODE ###

N=int(input())
D=list(map(int,input().split()))
D.sort()
mi=D[0]
ma=D[N-1]
point=0
for j in range(mi,ma+1): #Kはj
    if D[N//2-1]<j<=D[N//2]:
        point+=1
print(point)
cond=input().split(" ")
n=int(cond[0])
m=int(cond[1])
q=int(cond[2])
train=[[0 for i in range(2)] for j in range(m)]
sect=[[0 for i in range(2)] for j in range(q)]
#print(train)
 
def judge(arr_m,arr_q):
    a=0
    #print(arr_m)
    #print(arr_q)
    #print("*")
    if arr_q[0]<=arr_m[0] and arr_m[1]<=arr_q[1]:
        a=1
    return a
for i in range(m):
    train[i]=input().split(" ")
    train[i]=list(map(int,train[i]))
    #print(train)
for i in range(q):
    sect[i]=input().split(" ")
    sect[i]=list(map(int,sect[i]))
    #print(sect)
for i in range(q):
    ans=0
    for j in range(m):
        ans+=judge(train[j],sect[i])
    print(ans)

### FIXED CODE ###

nums=input().split(" ")
print((int(nums[0])-1)*(int(nums[1])-1))
h, n = map(int, input().split())

a = [map(int, input().split()) for _ in range(n)]

h -= sum(a)
if h <= 0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

h, n = map(int, input().split())
a = [int(x) for x in input().split()]

h -= sum(a)

if h <= 0:
    print('Yes')
else:
    print('No')
l = []
ans = 0

for s in input():
    if s == "0":
        if l and l[-1] == "1":
            l.pop()
            ans += 2
        else:
            l.append(s)
    else:
        if l and l[-1] == "0":
            l.pop()
            ans += 2
        else:
            l.append(i)

print(ans)

### FIXED CODE ###

a,b=0,0
for i in input():
  if i=="1":a+=1
  else:b+=1
print(2*min(a,b))
#
import sys
import math
import itertools


# 整数をいくつか入力
n,x,m = (int(i) for i in input().split())

if n < 100000:
    b=0
    for i in range(n):
        b += x
        #print(x)
        x = (x*x) %m
    print(b)
else:
    ll=[0]*100000
    s=0
    for i in range(100000):
        ll[i]=x
        s += x
        x = (x*x) %m
    for i in range(99998,-1,-1):
        if ll[i]==ll[99999]:
            term=99999-i
    p=(n-100000)//term
    q=(n-100000)%term
    r=0
    for i in range(term):
        r += ll[100000-term+i]
    s += r * p
    for i in range(q):
        s += ll[100000-term+i]
    print(s%)



### FIXED CODE ###

#
import sys
import math
import itertools


# 整数をいくつか入力
n,x,m = (int(i) for i in input().split())

if n < 100000:
    b=0
    for i in range(n):
        b += x
        #print(x)
        x = (x*x) %m
    print(b)
else:
    ll=[0]*100000
    s=0
    for i in range(100000):
        ll[i]=x
        s += x
        x = (x*x) %m
    for i in range(99998,-1,-1):
        if ll[i]==ll[99999]:
            term=99999-i
    p=(n-100000)//term
    q=(n-100000)%term
    r=0
    for i in range(term):
        r += ll[100000-term+i]
    s += r * p
    for i in range(q):
        s += ll[100000-term+i]
    print(s)
a,b = map(int, raw_input().split());

print (2*(a+b), a*b);

### FIXED CODE ###

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

print a*b, 2*(a+b)
global cnt
cnt=0

def merge(A,left,mid,right):
    global cnt
    n1=mid-left
    n2=right-mid
    #L=[0 for i in range(n1+1)]
    #R=[0 for i in range(n2+1)]
    L=[]
    R=[]
    for i in range(n1):
            L.append(A[left+i])
    for i in range(n2):
            R.append(A[mid+j])
    L.append(float("inf"))
    R.append(float("inf"))
    i=0
    j=0
    for k in range(left,right):
        if L[i]<=R[j]:
            A[k]=L[i]
            i=i+1
            cnt+=1
        else:
            A[k]=R[j]
            j=j+1
            cnt+=1

def mergeSort(A,left,right):
    if left+1<right:
        mid=(int)((left+right)/2)
        mergeSort(A,left,mid)
        mergeSort(A,mid,right)
        merge(A,left,mid,right)

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


mergeSort(S,0,n)
print(*S)
print(cnt)



### FIXED CODE ###

global cnt
cnt=0

def merge(A,left,mid,right):
    L=A[left:mid]
    R=A[mid:right]
    L.append(float("inf"))
    R.append(float("inf"))
    
    i=0
    j=0
    for k in range(left,right):
        global cnt
        cnt+=1
        if L[i]<=R[j]:
            A[k]=L[i]
            i=i+1
        else:
            A[k]=R[j]
            j=j+1

def mergeSort(A,left,right):
    if left+1<right:
        mid=(int)((left+right)/2)
        mergeSort(A,left,mid)
        mergeSort(A,mid,right)
        merge(A,left,mid,right)

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

mergeSort(S,0,n)
print(*S)
print(cnt)
N,M = (map(int,input().split()))
A = list(map(int,input().split()))

dp = []
dp.append(1) # 0段目
if 1 in A: # 1段目
  dp.append(0) 
else :
  dp.append(1) 

for i in range(2,N+1):  
  if i in A:
    dp.append(0)
  else :
    dp.append(dp[i-1]+dp[i-2])
print(dp[N])  

### FIXED CODE ###

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
dp=[0]*(n+1)
dp[0]=1

af = [0]*(n+1)
for ai in a:
  af[ai]+=1

if 1 in a:
  dp[1]=0
else:
  dp[1]=1

  
for i in range(2,n+1):
  dp[i]=dp[i-2]+dp[i-1]
  if af[i]==1:    
    dp[i]=0

print(dp[-1]%1000000007)
r,d,x=input().split()
m = int(x)
for i in range(1, 11):
    m = int(r) * int(m) - int(d)
    print(int(m))

### FIXED CODE ###

a,b=input().split()
if int(a) >= 13:
  print(b)
elif int(a) >= 6:
  m = int(b) /  2
  print(int(m))
else:
  print("0")
N, M = map(int, input().split())
list = []
for i in range(H):
    list.append(input())
count = 0
for i in range(M):
    x = input()
    for j in list:
    if x in j:
        count+=1
print("No" if count=0 else "Yes")

### FIXED CODE ###

N, M = map(int, input().split())
a = []
b = []
for i in range(N):
    a.append(input())
c = 0
ans = "No"
for i in range(M):
    b.append(input())
for i in range(N-M+1):
    for j in range(N-M+1):
        for k in range(M):
            if a[i+k][j:j+M] == b[k]:
                c += 1
        if c == M:
            ans = "Yes"
            break
        c = 0
print(ans)
T1, T2=(int(i) for i in input().split())
A1, A2=(int(i) for i in input().split())
B1, B2=(int(i) for i in input().split())

if T1*A1+T2*A2==T1*B1+T2*B2:
    print("infinity")
elif ((A1>B1) & (T1*A1+T2*A2-(T1*B1+T2*B2)>0)) or ((A1<B1) & (T1*A1+T2*A2-(T1*B1+T2*B2)<0)):
    print(0)
else:
    d=T1*A1+T2*A2-(T1*B1+T2*B2)#T1+T2だけ走った後離れている距離
    if abs(T1*(A1-B1))%d==0:
        ss=1
    print(abs(T1*(A1-B1))//d*2-ss+1)

### FIXED CODE ###

T1, T2=(int(i) for i in input().split())
A1, A2=(int(i) for i in input().split())
B1, B2=(int(i) for i in input().split())

if T1*A1+T2*A2==T1*B1+T2*B2:
    print("infinity")
elif ((A1>B1) & (T1*A1+T2*A2-(T1*B1+T2*B2)>0)) or ((A1<B1) & (T1*A1+T2*A2-(T1*B1+T2*B2)<0)):
    print(0)
else:
    d=abs(T1*A1+T2*A2-(T1*B1+T2*B2))#T1+T2だけ走った後離れている距離
    ss=0
    if abs(T1*(A1-B1))%d==0:
        ss=1
        
    print(abs(T1*(A1-B1))//d*2-ss+1)
N, M = map(int, input().split())
LR_list = [list(map(int, input().split())) for _ in range(0, M)]

num_card = 0

for i in range(0, N):
    for j in range(0, M-1):
        if not (i >= LR_list[j][0] and i <= LR_list[j][1]):
            break
    else:
        num_card += 1

print(num_card)


### FIXED CODE ###

age, fee= map(int, input().split())

if age <= 5:
    print(0)
elif 6 <= age and age <= 12:
    print(int(fee/2))
elif 13 <= age:
    print(fee)
#!/usr/bin/env python3
import sys
from sympy.ntheory import factorint
import numpy as np


def solve(N: int):

    fct = factorint(N)

    fct_list = []
    for key, item in zip(fct.keys(), fct.values()):
        fct_list += [key] * item

    result = 1e12

    if len(fct_list) == 2:
        x = fct_list[0]
        y = fct_list[1]
        print(x - 1 + y - 1)
    elif len(fct_list) == 1:
        x = fct_list[0]
        y = 1
        print(x - 1 + y - 1)

    else:
        for i in range(1, len(fct_list) - 1):

            x = np.prod(fct_list[: i + 1])
            y = np.prod(fct_list[i + 1 :])

            result = min(result, x - 1 + y - 1)
        print(result)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import numpy as np


def solve(N: int):
    result_list = []
    for i in range(1, int(np.sqrt(N)) + 1):
        if N % i == 0:
            result_list.append(i - 1 + N // i - 1)
        else:
            pass
    print(min(result_list))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)


if __name__ == "__main__":
    main()
N=int(input())
A= list(map(int,input().split()))

for i in A:
    S+=1/A[i]

print(1/S)

### FIXED CODE ###

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

for i in A:
    S+=1/i

print(1/S)
S=input().split()
N=S[0]
N=int(N)
del S[0]
M=S[0]
M=int(M)
del S[0]
s=0
for i in range(M):
    s=s+int(S[i])
if s>N:
    print(-1)
else:
    print(N-s)


### FIXED CODE ###

n,m=map(int,input().split())
l=list(map(int,input().split()))
sum=0
for i in range(m):
  sum+=l[i]
if sum>n:
  print(-1)
else:
  print(n-sum)
import math
import numpy as np
N,K=map(int,input().split())
a=[0]*N
a=list(map(int,input().split()))
A=np.array(a)
b=np.zeros(N)
for i in range(K):
    if(K*N==sum(A)):
        break
    b=np.zeros(N)
    for j in range(N):

        minmin=max(0,math.ceil(j-A[j]-0.5))

        maxmax=min(N,math.floor(j+A[j]+0.5)+1)

        if(minmin==maxmax):
            maxmax=maxmax+1
            if(N<=maxmax):
                minmin=N-1
                maxmax=N

        for k in range(minmin,maxmax):
            b[k]=b[k]+1

    A=b
A=A.astype(np.int)
da=list(A)
L=[str(a) for a in da]

da=" ".join(L)
print(da)


### FIXED CODE ###

import math
N,K=map(int,input().split())
A=[0]*N
A=list(map(int,input().split()))

da=[0 for i in range(N)]
for k in range(K):
    B=[0 for i in range(N)]
    for i in range(N):
        l=max(0,i-A[i])
        r=min(N-1,i+A[i])
        B[l]=B[l]+1
        if(r+1<N):
            B[r+1]=B[r+1]-1
    for i in range(1,N):
        B[i]=min(N,B[i]+B[i-1])
    if(A==B):
        break
    A=B
b=[str(i) for i in B]
b=" ".join(b)
print(b)
mod=10**9+7
n,k=map(int,input().split())
a=list(map(int,input().split()))
if max(a)<0:
  if k%2:a.sort(reverse=1)
  else:a.sort()
  ans=1
  for i in a[:k]:ans=(ans*i)%mod
  exit(print(ans))
p=[(0,0)]
m=[(0,0)]
for i in a:
  if i<0:m.append((-i,1))
  else:p.append((i,0))
pp=mm=None
p.sort()
m.sort()
oe=0
ans=1
for i in range(k):
  if p[-1][0]>m[-1][0]:
    t,f=p.pop()
    pp=t
  else:
    t,f=m.pop()
    mm=t
  ans=(ans*t)%mod
  if ans==0:exit(print(0))
  oe^=f
if oe:
  if (pp*p[-1][0]>mm*m[-1][0] and mm!=None) or pp!=None:
    ans=(ans*pow(mm,mod-2,mod)*p[-1][0])%mod
  else:
    ans=(ans*pow(pp,mod-2,mod)*m[-1][0])%mod
print(ans)


### FIXED CODE ###

from itertools import combinations
mod=10**9+7
def solve(n,k,a):
  if min(a)>0:
    ans=1
    a.sort(reverse=1)
    for i in a[:k]:
      ans*=i
      ans%=mod
    return ans
  if max(a)<0:
    if k%2==0:
      a.sort()
      ans=1
      for i in a[:k]:
        ans*=i
        ans%=mod
      return ans
    else:
      a.sort(reverse=1)
      ans=1
      for i in a[:k]:
        ans*=i
        ans%=mod
      return ans
  if n==k:
    ans=1
    for i in a:
      ans*=i
      ans%=mod
    return ans
  if k==1:
    return max(a)
  if n-k==1:
    ans=1
    if a.count(0)>1:return 0
    p=[]
    m=[]
    for i in a:
      if i>0:p.append(i)
      elif i<0:m.append(i)
    if 0 in a:
      if len(m)%2==0:
        for i in a:
          if i==0:continue
          ans=(ans*i)%mod
      else:ans=0
    else:
      if len(m)%2==0:
        for i in sorted(p)[1:]+m:ans=(ans*i)%mod
      else:
        for i in p+sorted(m)[:-1]:ans=(ans*i)%mod
    return ans


  ans=1
  p=[]
  m=[]
  for i in a:
    if i<0:m.append(i)
    elif i>=0:p.append(i)
  p.sort()
  m.sort(reverse=1)

  while k>1:
    if k<=5:
      if len(p)>=10:p=p[-10:]
      if len(m)>=10:m=m[-10:]
      ans*=solve2(len(p)+len(m),k,m+p)
      ans%=mod
      k=0
      break
    if len(p)<2:
      ans*=m.pop()*m.pop()
      k-=2
    elif len(m)<2:
      ans*=p.pop()*p.pop()
      k-=2
    elif m[-1]*m[-2]>p[-1]*p[-2]:
      ans*=m.pop()*m.pop()
      k-=2
    else:
      ans*=p.pop()*p.pop()
      k-=2
    ans%=mod
  if k:
    ans*=p.pop()
  return ans
  print(ans%mod)

def solve2(n,k,a):
  ans=-10**20
  for c in combinations(range(n),k):
    anss=1
    for i in c:anss*=a[i]
    ans=max(ans,anss)
  return ans%mod

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

"""
from random import randint
for i in range(10000):
  n=randint(1,10)
  k=randint(1,n)
  a=sorted([randint(-10,10)for _ in range(n)])
  print(n,k,a)
  ans1=solve(n,k,a)
  ans2=solve2(n,k,a)
  if ans1==ans2:print("ok")
  else:
    print("error")
    print(n,k)
    print(*a)
    print(ans1,ans2)
    exit()
"""