Harryxun/stf_run huggingface dataset:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

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

#############
# Main Code #
#############

S = str(input())

l = [null,"SAT","FRI","THU","WED","TUE","MON","SUN"]

for i in range(8):
  if S == l[i]:
    print(i)


### FIXED CODE ###

S = input()
 
l = [None,"SAT","FRI","THU","WED","TUE","MON","SUN"]
 
for i in range(8):
  if S == l[i]:
    print(int(i))
s=input()
ans=0
if s[0]=='C':
    ans+=1
if s[1]='O':
    ans+=1
if s[2]='D':
    ans+=1
if s[3]='E':
    ans+=1
if s[4]='F':
    ans+=1
if s[5]='E':
    ans+=1
if s[6]='S':
    ans+=1
if s[7]='T':
    ans+=1
if s[8]='I':
    ans+=1
if s[9]='V':
    ans+=1
if s[10]='A':
    ans+=1
if s[11]='L':
    ans+=1
if s[12]='2':
    ans+=1
if s[13]='0':
    ans+=1
if s[14]='1':
    ans+=1
if s[15]='6':
    ans+=1
print(ans)

### FIXED CODE ###

s1 = 'CODEFESTIVAL2016'
s2 = raw_input()
ans = 0
for i in range(len(s1)):
    ans += [0, 1][s1[i] != s2[i]]
print ans
a=sum[int(x) for x in input().split()]
if a>=10:
  a='error'
print(a)

### FIXED CODE ###

a=sum([int(x) for x in input().split()])
if a>=10:
  a='error'
print(a)
# -*- coding: utf-8

while True:
   A = raw_input().split()
   if A[1] == '?':
      break
   if A[1] == '+':
      print(int(A[0])+int(A[2])
   if A[1] == '-':
      print(int(A[0])-int(A[2])
   if A[1] == '*':
      print(int(A[0])*int(A[2])
   if A[1] == '/':
      print(int(A[0])/int(A[2])





### FIXED CODE ###

# -*- coding: utf-8

while True:
   A = raw_input().split()
   if A[1] == '?':
      break
   if A[1] == '+':
      print(int(A[0])+int(A[2]))
   if A[1] == '-':
      print(int(A[0])-int(A[2]))
   if A[1] == '*':
      print(int(A[0])*int(A[2]))
   if A[1] == '/':
      print(int(A[0])/int(A[2]))
n=int(input())
ws=[input()]
for i in range(1,n):
  w=input()
  if w in ws or w[0]!=ws[i-1][-1]:
    print("No")
    break
else:print("Yes")

### FIXED CODE ###

n=int(input())
ws=[input()]
for i in range(1,n):
  w=input()
  if w in ws or w[0]!=ws[i-1][-1]:
    print("No")
    break
  ws.append(w)
else:print("Yes")
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M = list(map(int, sys.stdin.buffer.readline().split()))
S = sys.stdin.buffer.readline().decode().rstrip()

# 後ろから貪欲
ans = []
S = S[::-1]

pos = [N + 1] * len(S)
p = N + 1
l = N
while p - l <= M:
    pos[l] = p
    l -= 1
p -= 1
while p >= 0:
    if S[p] == '1':
        p -= 1
        continue

    while p - l <= M and l >= 0:
        pos[l] = p
        l -= 1
    p -= 1

i = 0
while i < N:
    me = None
    for j in reversed(range(1, min(M + 1, pos[i] - i + 1))):
        if i + j < len(S) and S[i + j] == '0':
            me = j
            break
    if me is None:
        print(-1)
        exit()
    ans.append(me)
    i += me
print(*ans[::-1])


### FIXED CODE ###

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M = list(map(int, sys.stdin.buffer.readline().split()))
S = sys.stdin.buffer.readline().decode().rstrip()

# 後ろから貪欲
ans = []
S = S[::-1]

pos = [N + 1] * len(S)
p = N + 1
l = N
while p - l <= M and l >= 0:
    pos[l] = p
    l -= 1
p -= 1
while p >= 0:
    if S[p] == '1':
        p -= 1
        continue

    while p - l <= M and l >= 0:
        pos[l] = p
        l -= 1
    p -= 1

i = 0
while i < N:
    me = None
    for j in reversed(range(1, min(M + 1, pos[i] - i + 1))):
        if i + j < len(S) and S[i + j] == '0':
            me = j
            break
    if me is None:
        print(-1)
        exit()
    ans.append(me)
    i += me
print(*ans[::-1])
n, K = map(int,input().split())
h =[int(_) for _ in input().split()]

res = 0
for i in range(n):
  if h[i] >= k:
    res += 1
print(res)

### FIXED CODE ###

n, k = map(int,input().split())
h =[int(_) for _ in input().split()]
 
res = 0
for i in range(n):
  if h[i] >= k:
    res += 1
print(res)
from collections import deque

def insert(x, dll):
    dll.appendleft(x)

def delete(x, dll):
    dll.remove(x)

def deleteFirst(dll):
    dll.popleft()

def deleteLast(dll):
    dll.pop()

n = int(input())
command1 = {"insert": insert, "delete": delete}
command2 = {"deleteFirst": deleteFirst, "deleteLast": deleteLast}
dll = deque()
for i in range(n):
    input_line = [str(s) for s in input().split()]
    if(input_line[0] in command1):
        command1[input_line[0]](int(input_line[1]), dll)
    else:
        command2[input_line[0]](dll)
print(*dll)

### FIXED CODE ###

from collections import deque
   
n = int(input())
dll = deque()
   
for i in range(n):
    input_line = input().split()
    if input_line[0] == "insert":
        dll.appendleft(input_line[1])
    elif input_line[0] == "delete":
        try:
            dll.remove(input_line[1])
        except:
            pass
    elif input_line[0] == "deleteFirst":
        dll.popleft()
    else:
        dll.pop()
           
print(*dll)
x = input("1??\???100??\????????´??°?????\?????????????????????: ")
if (x < 1) or (x > 100):
    while (x < 1) and (x > 100):
        x = input("??????????????\?????????????????????: ")
else:
    num = x * x * x
    print(num, end="\n")

### FIXED CODE ###

x = int(input(""))
if (x >= 1) or (x <= 100):
    num = x ** 3 
    print(num, end="\n")
else:
    pass
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
L = []
for i in range(Q):
    B,C = map(int,input().split())
    L.append([B,C])
c = {}
for i in range(1,10002):
    c[i] = 0
for k in A:
    c[k] += 1
s = sum(A)
for i in range(Q):
    if c[L[i][0]] == 0:
        print(s)
    else:
        n = c[L[i][0]]
        c[L[i][1]] += n
        c[L[i][0]] = 0
        s += (L[i][1] - L[i][0])*n
        print(s)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
L = []
for i in range(Q):
    B,C = map(int,input().split())
    L.append([B,C])
c = {}
for i in range(1,100001):
    c[i] = 0
for k in A:
    c[k] += 1
s = sum(A)
for i in range(Q):
    if c[L[i][0]] == 0:
        print(s)
    else:
        n = c[L[i][0]]
        c[L[i][1]] += n
        c[L[i][0]] = 0
        s += (L[i][1] - L[i][0])*n
        print(s)
n = int(input())
l = list(map(int,input().split()))
h = [0]*(10**5+1)
for i in l:
  h[i+1] += 1
  h[i] += 1
  h[i+2] += 1
print(max(h))

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
h = [0]*(10**5+2)
for i in l:
  h[i+1] += 1
  h[i] += 1
  h[i+2] += 1
print(max(h))
n,m = map(int,input().split())
x=['0']*m
y=['0']*m
for i in range(m):
    x[i],y[i] = map(str,input().split())

num = 0
pena = 0

lis=[0]*(n+1)
lis2=[0]*n
lis3=[0]*n
sw = [0]*n

for i in range(m):
    if y[i] == 'WA' and sw[int(x[i])]== 0:
        lis[int(x[i])] += 1
    else:
        lis2[int(x[i])] = 1
        sw[int(x[i])] = 1
        
pena = sum(lis)
num = sum(lis2)

print(num,pena)

### FIXED CODE ###

n,m = map(int,input().split()) 
x=['0']*m 
y=['0']*m 
for i in range(m): 
    x[i],y[i] = map(str,input().split())

num = 0 
pena = 0

lis=[0]*n 
sw = [0]*n

for i in range(m): 
    if y[i] == 'WA':
        lis[int(x[i])-1] += 1
    else:
        if sw[int(x[i])-1] == 0:
            num += 1
            pena = pena + lis[int(x[i])-1]
            sw[int(x[i])-1] = 1

        else:
            pass
        
print(num,pena)
a,b,k = map(int,input().split())
tmp = list(range(a,b+1))
if b-a+1 > k:
	ans = tmp[:k] + tmp[-k:]
else:
	ans = tmp
for i in set(ans):
	print(i)

### FIXED CODE ###

a,b,k=map(int,input().split())
if a+k-1>=b-k+1:
    for i in range(a,b+1):
        print(i)
else:
    for i in range(a,a+k):
        print(i)
    for i in range(b-k+1,b+1):
        print(i)
N,M,K=map(int,input().split(' '))
mod = 998244353
ans =0
fac=[0]*N
inv=[0]*N
finv=[0]*N
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,N):
    fac[i] = fac[i-1]*i%mod
    inv[i] = mod-inv[mod%i]*(mod//i)%mod
    finv[i] = finv[i-1]*inv[i]%mod
def COM(n,k):
    if (n < k):
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n]*(finv[k]*finv[n-k]%mod)%mod
for i in range(K+1):
    #print(M*pow(M-1,N-1-i,mod),COM(N-1,i))
    ans += M*pow(M-1,N-1-i,mod)*COM(N-1,i)
    ans %=mod
print(ans)

### FIXED CODE ###

N,M,K=map(int,input().split(' '))
mod = 998244353
ans =0
fac=[0]*(N+1)
inv=[0]*(N+1)
finv=[0]*(N+1)
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,N+1):
    fac[i] = fac[i-1]*i%mod
    inv[i] = mod-inv[mod%i]*(mod//i)%mod
    finv[i] = finv[i-1]*inv[i]%mod
def COM(n,k):
    return fac[n]*(finv[k]*finv[n-k]%mod)%mod
for i in range(K+1):
    ans += M*pow(M-1,N-1-i,mod)*COM(N-1,i)
    ans %=mod
print(ans)
s=input()
if s=='AAA' or s=='BBB':
  print("No")
else:
print("Yes")

### FIXED CODE ###

s = input()

if s == 'AAA' or s == 'BBB':
    print("No")
else:
    print("Yes")
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

def mapline(t = int):
    return map(t, sysread().split())
def mapread(t = int):
    return map(t, read().split())

def run():
    N, *A = mapread()
    ans = 1
    current = [0,0,0]
    for a in A:
        transition = 0
        cache = None
        for i, c in enumerate(current):
            if c == a:
                transition += 1
                cache = i
        ans *= transition
        ans %= mod
        current[cache] += 1
    print(ans)


if __name__ == "__main__":
    run()


### FIXED CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

def mapline(t = int):
    return map(t, sysread().split())
def mapread(t = int):
    return map(t, read().split())

def run():
    N, *A = mapread()

    dp = [defaultdict(lambda:0) for _ in range(N+1)]
    dp[0][(0,0,0)] = 1
    for i in range(N):
        a = A[i]
        k = i + 1
        for key in dp[k-1].keys():
            for ii, v in enumerate(key):
                if v == a:
                    tmp = list(key)
                    tmp[ii] += 1
                    dp[k][tuple(tmp)] += dp[k-1][key] % mod
    ans = 0
    for key in dp[N].keys():
        ans = (ans + dp[N][key]) % mod
    #print(dp)
    print(ans)


if __name__ == "__main__":
    run()
import numpy as np
N=input()
A=map(input().split())
B=map(input().split())
C=array(map(input().split()))

sb=sum(B)
dC=np.diff(A)
sC=C[np.where(dC==1)[0]].sum()

print(sb+sC)

### FIXED CODE ###

import numpy as np
N=int(input())
A=np.array(list(map(int,input().split())))
B=list(map(int,input().split()))
C=np.array(list(map(int,input().split())))

sb=sum(B)
dC=np.diff(A)

sC=C[A[np.where(dC==1)[0]]-1].sum()
#print(sb, sC)
print(sb+sC)
if b > 0 and d > 0:
    print(max(b*d, a*c))
elif b > 0 and d < 0:
    print(a*d)
elif b < 0 and d > 0:
    print(b*c)
elif b <= 0 and d <= 0:
    print(a*c)

### FIXED CODE ###

a, b, c, d = map(int, input().split())

print(max(a*c, a*d, b*c, b*d))
big = 10**9 + 7

def typical_stairs(n,m,a):

    flag = [True]*(n+1)
    for i in range(m):
        tmp = a[i]
        flag[tmp] = False

    route = [0]*(n+1)
    route[0] = 1
    if flag[1]:
        route[1] = 1
    else:
        route[1] = 0

    for i in range(2,n+1):
        if flag[i]:
            route[i] = route[i-1] + route[i-2]

        ans = route[i]

    return ans%big
if __name__ == '__main__':
    n,m = map(int,raw_input().split())
    a = [int(raw_input()) for _ in range(m)]

    print typical_stairs(n,m,a)

### FIXED CODE ###

big = 10**9 + 7

def typical_stairs(n,m,a):

    flag = [True]*(n+1)
    for i in range(m):
        tmp = a[i]
        flag[tmp] = False

    route = [0]*(n+1)
    route[0] = 1
    ans = route[0]
    if flag[1]:
        route[1] = 1
    else:
        route[1] = 0

    for i in range(2,n+1):
        if flag[i]:
            route[i] = route[i-1] + route[i-2]

        ans = route[i]

    return ans%big
if __name__ == '__main__':
    n,m = map(int,raw_input().split())
    a = [int(raw_input()) for _ in range(m)]
    print typical_stairs(n,m,a)
n = int(raw_input())
a = map(int, raw_input().split())

for i in range(n):
  print a[n-i],

### FIXED CODE ###

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

for i in range(n):
  print a[n-i-1],
a=str(input())
b=str(input())
c=str(input())
print(a[:1]b[1:2]c[2:3])

### FIXED CODE ###

a=list(str(input()))
b=list(str(input()))
c=list(str(input()))
print(str(a[0]+b[1]+c[2]))
#include <iostream>

using namespace std;

int main(){
  int a,b,cnt,now;
  cin >> a >> b;
  now = 1;
  cnt = 0;
  while(now < b){
    if (cnt == 0) now += a;
    else now += a - 1;
  cnt += 1;
  }
  cout << cnt << endl;
  return 0;
}

### FIXED CODE ###

[a,b] = [int(i) for i in input().split()]
now = 1
cnt = 0
while(now < b):
    now += a-1
    cnt += 1
print(cnt)
a, b = map(int, input().split())

n = int(input())

s = n // (a + b)
m = n % (a + b)

if a > m:
    print(a * s + a)
else:
    print(a * s + m)

### FIXED CODE ###

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

result = 0
result += N // (A + B) * A
result += min(N % (A + B), A)
print(result)
a = int(input())

i = 2
max_num = 1
while i**2 < a:
    j = 1
    temp = 0
    while i**j < a:
        temp = i**j
        j+=1

    if temp > max_num:
        max_num = temp
    i+=1
print(max_num)


### FIXED CODE ###

a,b,c,d = map(int, input().split())

ab = abs(a - b)
bc = abs(b - c)
ca = abs(c - a)

if(ab <= d and bc <= d or ca <=d):
  print("Yes")
else:
  print("No")
N, M = list(map(int, input().split()))
lines = [list(map(int, input().split())) for _ in range(M)]

graph = [[False] * N for _ in range(N)]
for a,b in lines:
    graph[a-1][b-1] = graph[b-1][a-1] = True

visited = [False for _ in range(N)]

def DFS(v):
    visited[v] = True
    for from_v in range(N):
        if not graph[v][from_v]:
            continue
        if visited[from_v]:
            continue
        DFS(from_v)
    
cnt = 0
for i in range(M):
    pass_a, pass_b = lines[i]
    pass_a -= 1
    pass_b -= 1
    graph[pass_a][pass_b] = graph[pass_b][pass_a] = False
    DFS(i)
    
    cnt += 1 if False in visited else 0
    
    visited = [False for _ in range(N)]
    graph[pass_a][pass_b] = graph[pass_b][pass_a] = True

print(cnt)

### FIXED CODE ###

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

graph = [[False] * N for _ in range(N)]
for a,b in lines:
    graph[a-1][b-1] = graph[b-1][a-1] = True

visited = [False for _ in range(N)]

def DFS(v):
    visited[v] = True
    for from_v in range(N):
        if not graph[v][from_v]:
            continue
        if visited[from_v]:
            continue
        DFS(from_v)
    
cnt = 0
for i in range(M):
    pass_a, pass_b = lines[i]
    pass_a -= 1
    pass_b -= 1
    graph[pass_a][pass_b] = graph[pass_b][pass_a] = False
    DFS(pass_a)
    
    cnt += 1 if False in visited else 0
    
    visited = [False for _ in range(N)]
    graph[pass_a][pass_b] = graph[pass_b][pass_a] = True

print(cnt)
n = int(input())
ans = 0
for i in range(1,n + 1):
    for j in range(1, n + 1):
        f = fractions.gcd(i, j)
        for k in range(1, n + 1):
            ans += fractions.gcd(f, k)
print(ans)

### FIXED CODE ###

from math import gcd
n = int(input())
ans = 0
for i in range(1,n + 1):
    for j in range(1, n + 1):
        f = gcd(i, j)
        for k in range(1, n + 1):
            ans += gcd(f, k)
print(ans)
import sys
s = input()
t = input()
s.sort()
t.sort()
for x, y in zip(s, t[::-1]):
    if x > y:
        print('No')
        sys.exit()
    elif x == y:
        continue
    else:
        print('Yes')
        sys.exit()
if len(s) <= len(t):
    print('Yes')
else:
    print('No')

### FIXED CODE ###

import math
a, b = map(int, input().split())
x = (a+b)/2
print(math.ceil(x))
N=input()
n=int(N)
for s in range(n):
  ds1,ds2=input().split()
if ds1==ds2 and d(s+1)1==d(s+1)2 and d(s+2)1==d(s+2)2:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N=input()
n=int(N)
x=0
for s in range(n):
  ds1,ds2=input().split()
  if ds1==ds2:
    x+=1
  else:
    x=0
  if x==3:
    print("Yes")
    break
else:
  print("No")
A, B = input().strip()
print(A+B)

### FIXED CODE ###

A, B = input().split()
print(B+A)
N=int(input())

A=list(map(int,input().split()))
#B=[]
#C=[]
D=[0]*10000000
E=[0]*10000000

ans=0

for i in range(N):
  #B.append(A[i]+i+1)
  #C.append(-A[i]+i+1)
  D[A[i]+i+1]+=1
  E[-A[i]+i+1]+=1

for i in range(len(D)):
  #ans+=C.count(i)
  ans+=D[i]*E[i]

print(ans)

### FIXED CODE ###

N=int(input())
 
A=list(map(int,input().split()))
#B=[]
#C=[]
D=[0]*1000000
E=[0]*1000000
 
ans=0
 
for i in range(N):
  if A[i]<500000:
  #B.append(A[i]+i+1)
  #C.append(-A[i]+i+1)
  #if -A[i]+i>=0:
  	D[A[i]+i]+=1
  	E[-A[i]+i]+=1
   #print(E[-A[i]+i],-A[i]+i)

for i in range(1000000):
  #ans+=C.count(i)
  ans+=D[i]*E[i]
 
print(ans)
N = int(input())

if N < 1000:
    print(f'ABC{N:03}')
else:
    print(f'ABD{N-999:03}')

### FIXED CODE ###

N = int(input())

if N < 1000:
    print('ABC')
else:
    print('ABD')
def main():
  n,k = map(int,input().split())
  a = list(filter(lambda x:x<k,list(map(int,input().split()))))
  n = len(a)
  a.sort(reverse=True)
  ng = -1
  ok = n
  while ok-ng > 1:
  mid = (ok+ng)//2
  dp = [False]*(k+1)
  dp[0] = True
  f = 0
  for j in range(n):
    if j == mid:
      continue
    w = a[j]
    for i in range(k,w-1,-1):
      if dp[i-w]:
        dp[i] = True
        if k-a[mid] <= i < k:
          ng = mid
          f = 1
          break
    if f:
      break
  else:
    ok = mid
      
  print(n-ok)

if __name__ == "__main__":
  main()
  

### FIXED CODE ###

n, k = map(int,input().split())
a = [k+1 if x > k else x for x in map(int,input().split())]
a.sort()
lef = [1]*n
rig = [1]*n
mask = (1 << (k+1)) - 1
for i in range(n-1):
  lef[i+1] = lef[i] | (lef[i] << a[i]) & mask
  rig[-i-2] = rig[-i-1] | (rig[-i-1] << a[-i-1]) & mask
ok = -1
ng = n
while ng - ok > 1:
  mid = (ng + ok) // 2
  if a[mid] >= k:
      ng = mid
      continue
  lc = lef[mid]
  rc = rig[mid]
  cov = ((1 << k) - 1) ^ ((1 << (k - a[mid])) - 1)
  for i in range(k):
    if lc & 1 and rc & cov:
      ng = mid
      break
    lc >>= 1
    cov >>= 1
  else:
    ok = mid
print(ok + 1)
K = int(input())
S = input()
X = len(S)
mod = 10**9+7

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 3*10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

ans = 0
for i in range(X,K+X+1):
  	temp = 1
    A = i-X
    B = K+X-i
    temp *= cmb(A+X-1,X-1,mod)*power(25,A,mod)
    temp %= mod
    temp *= power(26,B,mod)
    ans += temp
    ans %= mod
print(ans)

### FIXED CODE ###

K = int(input())
S = input()
X = len(S)
mod = 10**9+7

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 2*10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


A = 0
B = K
temp = cmb(A+X-1,X-1,mod)*power(25,A,mod)
temp %= mod
temp *= power(26,B,mod)
temp %= mod

ans = temp

for i in range(X+1,K+X+1):

    temp *= 25
    temp %= mod
    
    temp *= pow(26, mod-2, mod)
    temp %= mod
    
    temp *= i-1
    temp %= mod
    
    temp *= pow(i-X, mod-2, mod)
    temp %= mod    

    ans += temp
    ans %= mod

print(ans)
h,w = map(int, input().split())
Array = [list(map(int, input().split())) for _ in range(h)]
dx = [1,1,0,-1,-1,-1,0,1]
dy = [0,1,1,1,0,-1,-1,-1]
for i in range(h):
  for j in range(w):
    if Array[i][j]='#':
      continue
    num=0
    for d in range(8):
      ni = i+dy[d]
      nj = j+dx[d]
      if ni<0 or h<=ni:
        continue
      if nj<0 or w<=nj:
        continue
      if Array[ni][nj]=='#':
        num=num+1
    Array[i][j]=char(num)
    
for i in Array:
  print(*Array)

### FIXED CODE ###

h,w = map(int,input().split())
Array = [list(map(str,input())) for _ in range(h)]
dx = [1,1,0,-1,-1,-1,0,1]
dy = [0,1,1,1,0,-1,-1,-1]
for i in range(h):
  for j in range(w):
    if Array[i][j]=='#':
      continue
    num=0
    for d in range(8):
      ni = i+dy[d]
      nj = j+dx[d]
      if ni<0 or h<=ni:
        continue
      if nj<0 or w<=nj:
        continue
      if Array[ni][nj]=='#':
        num=num+1
    Array[i][j]=str(num)
    
for i in Array:
  print(*i, sep='')