Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

s=input()

a=0
ab=0
abc=0
q=0

#if s[0]=="A" :
#  a=1
#elif s[0]=="?":
#  a=1
#  q=1
#print(str(a)+" "+str(ab)+" "+str(abc)+" "+str(q))

for i in range(len(s)):
  if s[i]=="A":
    a=a+3**q
  elif s[i]=="B":
    ab=ab+a
  elif s[i]=="C":
    abc=(abc+ab)%(10**9+7)
  elif s[i]=="?":
    abc=(abc*3+ab)%(10**9+7)
    
    ab=ab*3+a
    a=a*3
    
    a=a+3**q
    q+=1
  #print(str(a)+" "+str(ab)+" "+str(abc)+" "+str(q))
    
print(abc)


### FIXED CODE ###

s=input()

a=0
ab=0
abc=0
q=1
m=10**9+7

for i in range(len(s)):
  if s[i]=="A":
    a=(a+q)%m
  elif s[i]=="B":
    ab=(ab+a)%m
  elif s[i]=="C":
    abc=(abc+ab)%m
  else:
    abc=(abc*3+ab)%m
    ab=(ab*3+a)%m
    a=(a*3+q)%m
    q=(q*3)%m
print(abc)
### BUGGY CODE ###

N,K=map(int,input().split())
A=[list(map(int,input().split())) for i in range(N)]
V=2*N+2
INF=10**14
G=[[] for i in range(V)]
D=[INF]*V
PV,PE=[0]*V,[0]*V
def ae(fr,to,ca,co):
  global G
  G[fr].append([to,ca,co,len(G[to]),0])
  G[to].append([fr,0,-co,len(G[fr])-1,0])

def mcf(s,t,f):
  global G,V,INF,D,PV,PE
  for i in range(V):
    for j in range(len(G[i])):
      G[i][j][4]=0
  r=0
  z=f
  while z>0:
    D=[INF]*V
    D[s]=0
    ud=True
    while ud:
      ud=False
      for x in range(V):
        if D[x]==INF:
          continue
        for i in range(len(G[x])):
          if G[x][i][1]>0 and D[G[x][i][0]]>D[x]+G[x][i][2]:
            D[G[x][i][0]]=D[x]+G[x][i][2]
            PV[G[x][i][0]]=x
            PE[G[x][i][0]]=i
            ud=True
    if D[t]==INF:
      return -INF
    d=z
    x=t
    while x!=s:
      d=min(d,G[PV[x]][PE[x]][1])
      x=PV[x]
    z-=d
    r+=d*D[t]
    x=t
    while x!=s:
      G[PV[x]][PE[x]][1]-=d
      G[PV[x]][PE[x]][4]+=d
      G[x][G[PV[x]][PE[x]][3]][1]+=d
      G[x][G[PV[x]][PE[x]][3]][4]-=d
      x=PV[x]
  return r

s=N*2
t=s+1
for i in range(N):
  ae(s,i,K,0)
  ae(N+i,t,K,0)
  for j in range(N):
    ae(i,N+j,1,10**10-A[i][j])
ae(s,t,N*K,10**10)
print(N*K*10**10-mcf(s,t,N*K))
P=[['.']*N for i in range(N)]
for i in range(N):
  for j in range(len(G[i])):
    if G[i][j][4]>0:
      P[i][G[i][j][0]-N]='X'
  print(''.join(P[i]))

### FIXED CODE ###

N,K=map(int,input().split())
A=[list(map(int,input().split())) for i in range(N)]
V=2*N+2
INF=10**14
G=[[] for i in range(V)]
D=[INF]*V
PV,PE=[0]*V,[0]*V
def ae(fr,to,ca,co):
  global G
  G[fr].append([to,ca,co,len(G[to]),0])
  G[to].append([fr,0,-co,len(G[fr])-1,0])

def mcf(s,t,f):
  global G,V,INF,D,PV,PE
  for i in range(V):
    for j in range(len(G[i])):
      G[i][j][4]=0
  r=0
  z=f
  while z>0:
    D=[INF]*V
    D[s]=0
    ud=True
    while ud:
      ud=False
      for x in range(V):
        if D[x]==INF:
          continue
        for i in range(len(G[x])):
          if G[x][i][1]>0 and D[G[x][i][0]]>D[x]+G[x][i][2]:
            D[G[x][i][0]]=D[x]+G[x][i][2]
            PV[G[x][i][0]]=x
            PE[G[x][i][0]]=i
            ud=True
    if D[t]==INF:
      return -INF
    d=z
    x=t
    while x!=s:
      d=min(d,G[PV[x]][PE[x]][1])
      x=PV[x]
    z-=d
    r+=d*D[t]
    x=t
    while x!=s:
      G[PV[x]][PE[x]][1]-=d
      G[PV[x]][PE[x]][4]+=d
      G[x][G[PV[x]][PE[x]][3]][1]+=d
      G[x][G[PV[x]][PE[x]][3]][4]-=d
      x=PV[x]
  return r

s=N*2
t=s+1
for i in range(N):
  ae(s,i,K,0)
  ae(N+i,t,K,0)
  for j in range(N):
    ae(i,N+j,1,10**10-A[i][j])
ae(s,t,N*K,10**10)
print(N*K*10**10-mcf(s,t,N*K))
P=[['.']*N for i in range(N)]
for i in range(N):
  for j in range(len(G[i])):
    if G[i][j][4]>0:
      P[i][G[i][j][0]-N]='X'
  print(''.join(P[i]))
### BUGGY CODE ###

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

if d != 0:
    top = 2*(n-d)*pow(n,m-2)*(m-1)
else:
    top = n*pow(n,m-2)*(m-1)
bottom = pow(n,m)

print(top/bottom)

### FIXED CODE ###

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

if d != 0:
    top = 2*(n-d)*(m-1)
else:
    top = n*(m-1)
bottom = pow(n,2)

print(top/bottom)
### BUGGY CODE ###

n = int(input())
s = input()
c = 0
for i in range(n):
    for j in range(i, n):
        for k in range(j, n):
            if s[i] != s[j] and s[j] != s[k] and s[i] != s[k] and (j + 1) - (i + 1) != (k + 1) - (j + 1):
                c += 1
print(c)


### FIXED CODE ###

n = int(input())
s = input()
r = set()
g = set()
b = set()
for i in range(n):
    if s[i] == "R":
        r.add(i)
    if s[i] == "G":
        g.add(i)
    if s[i] == "B":
        b.add(i)
a = len(r) * len(b) * len(g)
for i in r:
    for j in b:
        k = abs(i - j)
        if i + k in g:
            a -= 1
        if i - k in g:
            a -= 1
        if j + k in g:
            a -= 1
        if j - k in g:
            a -= 1
        if (i + j) / 2 in g:
            a -= 1
print(a)
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
import random
from heapq import heappop, heappush
#input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def graphm():
    n=inp()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((b,w))
        g[b].append((a,w))
    return n,g
def dijkstra(s,to,n,g): # sからの最短距離 頂点数n
    s -= 1
    que = []
    d = [10**15 for _ in range(n)]
    d[s] = 0
    heappush( que,(0,s) )
    while len(que)>0:
        p =  heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                heappush( que,(d[edge[0]] , edge[0]) )
    return d[to-1]

def main():
    n,graph = graphm()
    q,k = inpm()
    for _ in range(q):
        x,y = inpm()
        print( dijkstra(x,k,n,graph) + dijkstra(k,y,n,graph) )    

if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import Counter,defaultdict,deque
import sys
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    n=int(input())
    graph = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b,w=map(int,input().split())
        a-=1
        b-=1
        graph[a].append((b,w))
        graph[b].append((a,w))
    graph = tuple(graph)
    q,k = map(int,input().split())
    que = deque([k-1])
    dis = [-1 for _ in range(n)]
    dis[k-1]=0
    while que:
        i = que.pop()
        for j in range(len(graph[i])):
            go = graph[i][j][0]
            d = graph[i][j][1]
            if dis[go]==-1:
                dis[go] = dis[i] + d
                que.append(go)
    for _ in range(q):
        x,y = map(int,input().split())
        print( dis[x-1] + dis[y-1] ) 

if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(input())
S = list(input())

ans = 0

for l2 in range(1, N):
    same_len = 0
    for i in range(N):
        if N - 1 < l2 + i:
            continue

        if S[i] == S[l2 + i]:
            same_len += 1
        else:
            same_len = min(l2, same_len)
            ans = max(ans, same_len)
            same_len = 0
    same_len = min(l2, same_len)
    ans = max(same_len, ans)

print(ans)


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(input())
S = list(input())

ans = 0

for l2 in range(1, N):
    same_len = 0
    for i in range(N):
        if N - 1 < l2 + i:
            continue

        if S[i] == S[l2 + i]:
            same_len += 1
        else:
            same_len = min(l2, same_len)
            ans = max(ans, same_len)
            same_len = 0
    same_len = min(l2, same_len)
    ans = max(same_len, ans)

print(ans)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline

    n = int(input())
    a = list(map(int, input().split()))
    A = []
    A_append = A.append
    cnt = 0

    for i in range(n-1):
        A_append((a[i]))
        x = sum(A) + a[i+1]
        if sum(A) > 0 and x > 0:
            y = abs(x)+1
            cnt += y
            a[i+1] -= y

        elif sum(A) < 0 and x < 0:
            y = abs(sum(A) - a[i+1])-1
            cnt += y
            a[i+1] += y

    if sum(a) == 0:
        cnt += 1

    print(cnt)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

def Chk(a, pos):
    cnt = 0
    tmp = 0

    for a in A:
        tmp += a

        if pos and tmp < 1:
            cnt += 1 - tmp
            tmp = 1
        elif not pos and tmp > -1:
            cnt += 1 + tmp
            tmp = -1

        pos = not pos
    return cnt

print(min(Chk(A, True), Chk(A, False)))
### BUGGY CODE ###

import sys, math, itertools, collections, bisect
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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
n = int(input())
A = list(map(int,input().split()))
data = [0] * (10**6+1)
for i in range(n):
  data[A[i]] += 1
for i in range(n):
  divisors = make_divisors(A[i])
  for divi in divisors:
    if  data[divi] != (1 if A[i] == divi else 0):
      # print(i,divi)
      break
  else:
    count += 1
    # print(i)
print(count)

# print(data[:25])


### FIXED CODE ###

import sys, math, itertools, collections, bisect
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

def primes(array,n):
    C = collections.Counter(array)
    count = 0
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    for i in array:
      if is_prime[i]:
        if C[i] == 1: count += 1
        for j in range(i, n + 1, i):
            is_prime[j] = False
    return count

n = int(input())
A = list(map(int,input().split()))
A.sort()
data = [0] * (10**6+1)


print(primes(A,10**6))
### BUGGY CODE ###

def expected_value(x):
    a = int(x)
    e = 0
    for i in range(1, a+1):
        e += i / a
    return e

n, k = [int(x) for x in input().split()]
evs = list(map(expected_value, input().split())) 

# initialize
left = 0
max_ev = 0
ev = 0
for i in range(k):
    ev += evs[i]

max_ev = ev
for i in range(k, n):
    ev = ev - evs[left] + evs[i]
    left += 1
    if ev > max_ev:
        max_ev = ev
print('{:.7f}'.format(max_ev))

### FIXED CODE ###

def expected_value(x):
    a = int(x)
    s = (a+1) * (a/2)
    # e = 0
    # for i in range(1, a+1):
    #     e += i / a
    return s / a

n, k = [int(x) for x in input().split()]
evs = list(map(expected_value, input().split())) 

# initialize
left = 0
max_ev = 0
ev = 0
for i in range(k):
    ev += evs[i]

max_ev = ev
for i in range(k, n):
    ev = ev - evs[left] + evs[i]
    left += 1
    if ev > max_ev:
        max_ev = ev
print('{:.7f}'.format(max_ev))
### BUGGY CODE ###

def chk_agc(cur):
    l=len(cur)
    result = True
    if l>2:
        for_chk_3 = cur[l-3]+cur[l-2]+cur[l-1]
        if for_chk_3 == "AGC" or for_chk_3 == "ACG" or for_chk_3 == "GAC":
            #print(for_chk_3)
            result=False
        if l>3:
            for_chk_4 = cur[l-4]+cur[l-3]+cur[l-2]+cur[l-1]
            if for_chk_4[3]=="C" and for_chk_4[0]=="A" and (for_chk_4[1]=="G" or for_chk_4[2]=="G"):
                #print(for_chk_4)
                result=False
    return result

def count_agc(i,n,ans,cur,already):
    if i==n+1:
        if not already:
            ans+=1
        return ans
    for char in ["A","G","C","T"]:
        next_already = True
        temp_str = cur
        temp_str+=char
        #文字列の長さはNじゃないといけない
        if already:
            if not chk_agc(temp_str):
                next_already=False
        else:
            next_already=False
        ans = count_agc(i+1,n,ans,temp_str,next_already)
    return ans
n=int(input())
print((pow(4,n)-count_agc(1,n,0,"",True))%10000000007)

### FIXED CODE ###

n=int(input())
mod = 10**9+7
memo=[{} for i in range(n)]
#indexに文字列がそのまま使える
def chk_agc(char):
    l=len(char)
    #print(char)
    result=True
    if l>2:
        last3=char[l-3:l]
        if last3=="AGC" or last3=="ACG" or last3=="GAC":
            result=False
    if l>3:
        if char[l-4]=="A" and char[l-1]=="C":
            if char[l-3]=="G" or char[l-2]=="G":
                result=False
    return result
def count_agc(i,n,last4):
    if i==n:
        return 1
    if last4 in memo[i]:
        return memo[i][last4]
    ret=0
    if i>3:
        last3=last4[1:4]
    else:
        last3=last4
    for char in ["A","G","C","T"]:
        next_last4 = last3+char
        if chk_agc(next_last4):
            ret += count_agc(i+1,n,next_last4)
    if i>2:
        memo[i][last4]=ret
    return ret
print(count_agc(0,n,"")%mod)
### BUGGY CODE ###

import numpy as np

# N, M = 10, 3
# ARR = [1, 8, 5, 7, 100, 4, 52, 33, 13, 5]
# BRR = [
#     [3, 10],
#     [4, 30],
#     [1, 4]
# ]
N,M = map(int,input().split())
ARR = list(map(int,input().split()))
BRR = []
for i in range(M):
    BRR.append(list(map(int,input().split())))

def calculate(n, m, arr, brr):
    arr = np.array(arr)
    brr = sorted(brr, key=lambda x: -x[1])
    for br in brr:
        arr.sort()
        sIndex = min(sum(arr < br[1]), br[0])
        if sIndex == 0:
            break
        arr[0:sIndex] = br[1]

    print(sum(arr))


calculate(N, M, ARR, BRR)

### FIXED CODE ###

# N, M = 10, 3
# ARR = [1, 8, 5, 7, 100, 4, 52, 33, 13, 5]
# BRR = [
#     [3, 10],
#     [4, 30],
#     [1, 4]
# ]


N,M = map(int,input().split())
ARR = list(map(int,input().split()))
BRR = []
for i in range(M):
    BRR.append(list(map(int,input().split())))

def calculate(n, m, arr, brr):
    raw = []
    for ar in arr:
        raw.append([ar, 1])
    for br in brr:
        raw.append([br[1], br[0]])

    raw = sorted(raw,key=lambda x:-x[0])
    # print(raw)

    offset = 0
    sum = 0
    for ra in raw:
        if offset + ra[1] <= n:
            sum = sum + ra[1] * ra[0]
            offset = offset + ra[1]
        else:
            sum = sum + (n - offset) * ra[0]
            offset = n
            break
    print(sum)

calculate(N, M, ARR, BRR)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
s=[]
cnt=0
for i in range(n):
    while a[i]%2==0:
        cnt+=1
    s.append(cnt)
print(min(s))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
s=[]
i=0
cnt=0
for i in range(n):
    while a[i]%2==0:
        cnt+=1
        a[i]=a[i]//2
    else:
        s.append(cnt)
        i+=1
        cnt=0
print(min(s))
### BUGGY CODE ###



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

answer = 0
mod = 10**9 + 7
for i in range(N):
  for j in range(i+1, N):
    multi = (A[i] * A[j])
    answer += multi
    answer = answer % mod
print(int(answer))

### FIXED CODE ###

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

answer = 0
a_sum = sum(A)
mod = 10**9+7

for i in range(N-1):
  a_sum -= A[i]
  answer += a_sum * A[i]
print(str(answer % mod))
### BUGGY CODE ###

n=int(input())
MOD=10**9+7
a=list(map(int,input().split()))
x=[0 for i in range(60)]
for i in range(n):
    s=(bin(a[i])[2:])[::-1]
    for j in range(len(s)):
        if s[j]=='1': x[j]+=1

ans=0
for i in range(60):
    ans+=( (n-x[i] )*x[i]*(2**i) ) %MOD
    ans=ans%MOD
print(ans)

### FIXED CODE ###

def main():
    MOD=10**9+7
    n=int(input())
    x=[0 for i in range(60)]
    a=list(map(int,input().split()))

    for i in range(n):
        k=0
        while a[i]>0:
            if a[i]&1:
                x[k]+=1
            a[i]>>=1
            k+=1
    ans=0
    b=1
    for i in range(60):
        ans+=x[i]*(n-x[i])*b
        ans%=MOD
        b=(b*2)%MOD
    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input())
B = [[int(x), i] for i, x in enumerate(input().split())]
B.sort()
C = [0] * N
cnt = 0
def lsearch(s, t):
  if s > t:
    return -1
  if s == t:
    return s if C[s] == 1 else -1
  else:
    m = (s + t) // 2
    return max(lsearch(s, m), lsearch(m + 1, t))
def rsearch(s, t):
  if s > t:
    return len(C)
  if s == t:
    return s if C[s] == 1 else len(C)
  else:
    m = (s + t) // 2
    return min(rsearch(s, m), rsearch(m + 1, t))
for b, i in B:
  l = i - lsearch(0, i - 1)
  r = rsearch(i + 1, N - 1) - i
  C[i] = 1
  cnt += b * l * r
print(cnt)

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
B = [0] * (N + 1)
for i in range(N):
  B[A[i]] = i + 1
L = list(range(N + 2))
R = list(range(N + 2))
cnt = 0
for i in range(N, 0, -1):
  l = L[B[i]]
  r = R[B[i]]
  cnt += i * (B[i] - l + 1) * (r - B[i] + 1)
  L[r + 1] = l
  R[l - 1] = r
print(cnt)
### BUGGY CODE ###

N, K, C = list(map(int, input().split(" ")))
S = input()

F_list = []
B_list = []

count = 0
add_count = 0
S_len = len(S)
while count < S_len and add_count < K:
    if S[count] == "o":
        add_count += 1
        F_list.append(count+1)
        count += C+1
    else:
        count += 1

count = 0
add_count = 0

while count < S_len and add_count < K:
    if S[-(count+1)] == "o":
        add_count += 1
        B_list.append(S_len-count)
        count += C+1
    else:
        count += 1


for i in F_list:
    if i in B_list:
        print(i)


### FIXED CODE ###

N, K, C = list(map(int, input().split(" ")))
S = input()

F_list = []
B_list = []

f_count = 0
b_count = 0
f_rest = 0
b_rest = 0
S_len = len(S)
# o
for i in range(S_len):
    if f_count == K and b_count == K:
        break

    if f_count < K:
        if S[i] == "o" and f_rest == 0:
            f_rest += C
            f_count += 1
            F_list.append(i+1)
        else:
            if f_rest > 0:
                f_rest -= 1
    if b_count < K:
        if S[-(i+1)] == "o" and b_rest == 0:
            b_rest += C
            b_count += 1
            B_list.append(S_len-i)
        else:
            if b_rest > 0:
                b_rest -= 1

for i in range(K):
    if F_list[i] == B_list[-(i+1)]:
        print(F_list[i])
### BUGGY CODE ###

import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
d = dd(int)
a = []
for i in range(N):
  t = input()[: -1]
  x, y = "", ""
  z = 0
  if "." in t:
    x, y = t.split(".")
    y = y.ljust(9, "0")
    z = int(x) * 10 ** 9 + int(y)
  else: z = int(t) * 10 ** 9
  zz = 1
  while z % 2 == 0:
    z //= 2
    zz *= 2
  while z % 5 == 0:
    z //= 5
    zz *= 5
  d[zz] += 1
  a.append(zz)
ks = sorted(d.keys())
table = dd(int)
for k in ks:
  for kk in ks:
    z = k * kk
    c = 0
    while z % 10 == 0:
      z //= 10
      c += 1
    table[k * kk] = c >= 18
res = 0
for i in range(N):
  x = a[i]
  cc = N
  for k in ks:
    z = x * k
    if table[z]:
      cc -= x == k
      continue
    cc -= d[k]
  res += cc
print(res // 2)

### FIXED CODE ###

import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
d = dd(int)
a = []
for i in range(N):
  t = input()[: -1]
  x, y = "", ""
  z = 0
  if "." in t:
    x, y = t.split(".")
    y = y.ljust(9, "0")
    z = int(x) * 10 ** 9 + int(y)
  else: z = int(t) * 10 ** 9
  zz = 1
  while z % 2 == 0:
    z //= 2
    zz *= 2
  while z % 5 == 0:
    z //= 5
    zz *= 5
  d[zz] += 1
  a.append(zz)
ks = sorted(d.keys())
table = dd(int)
for k in ks:
  for kk in ks:
    z = k * kk
    c = 0
    while z % 10 == 0:
      z //= 10
      c += 1
    table[k * kk] = c >= 18
res = 0
for x in ks:
  cc = N
  for k in ks:
    z = x * k
    if table[z]:
      cc -= x == k
      continue
    cc -= d[k]
  res += cc * d[x]
print(res // 2)
### BUGGY CODE ###

def cmb(a,b,c):
    b = min(b,a-b)
    num = 1
    for i in range(b):
        num = num*(a-i) % c
    den = 1
    for i in range(b):
        den = den*(i+1) % c
    return num * pow(den,c-2,c) % c
n,m,k = map(int,input().split())
mod = 10**9+7
ans = 0
for i in range(1,n):
    ans += i*(n-i)*m**2*cmb(n*m-2,k-2,mod)
    ans %= mod
for i in range(1,m):
    ans += i*(m-i)*n**2*cmb(n*m-2,k-2,mod)
    ans %= mod
print(ans)


### FIXED CODE ###

def cmb(a,b,c):
    b = min(b,a-b)
    num = 1
    for i in range(b):
        num = num*(a-i) % c
    den = 1
    for i in range(b):
        den = den*(i+1) % c
    return num * pow(den,c-2,c) % c
n,m,k = map(int,input().split())
mod = 10**9+7
ans = 0
C = cmb(n*m-2,k-2,mod)
for i in range(1,n):
    ans += i*(n-i)*m**2*C
    ans %= mod
for i in range(1,m):
    ans += i*(m-i)*n**2*C
    ans %= mod
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
s = str(input())
now = n
ans = []
while now != 0:
    for num in range(min(m,now),0,-1):
        if s[now-num] == "0":
            now -= num
            ans.insert(0,num)
            break
        else:
            if num == 1:
                print(-1)
                exit()
print(" ".join(map(str,ans)))

### FIXED CODE ###

n,m = map(int,input().split())
s = str(input())
now = n
ans = ""
while now != 0:
    for num in range(min(m,now),0,-1):
        if s[now-num] == "0":
            now -= num
            ans=str(num)+" "+ans
            break
        else:
            if num == 1:
                print(-1)
                exit()
print(ans)
### BUGGY CODE ###

from bisect import bisect_left


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

dp1 = [[0] * (K + 1) for _ in range(N + 1)]

for i in range(N + 1):
    dp1[i][0] = 1
for i in range(N):
    a = A[i]
    d = K if a >= K else a - 1
    for j in range(K, d, -1):
        dp1[i + 1][j] = dp1[i][j] | dp1[i][j - a]

dp2 = [[0] * (K + 1) for _ in range(N + 1)]
for i in range(N + 1):
    dp2[i][0] = 1
for i in range(N):
    a = A[N - 1 - i]
    d = K if a >= K else a - 1
    for j in range(K, d, -1):
        dp2[i + 1][j] = dp2[i][j] | dp2[i][j - a]


def solve(i):
    d1 = []
    d2 = []
    n = A[i]
    for j, k in enumerate(dp1[i]):
        if k:
            d1.append(j)
    for j, k in enumerate(dp2[N - 1 - i]):
        if k:
            d2.append(j)
    for a in d1:
        l = bisect_left(d2, K - n - a)
        r = bisect_left(d2, K - a)
        if r - l >= 1:
            return True
    return False


# [ok, ng) - Maximum
# (ng, ok] - Minimum
# ok が 最終的な答え
ok = N
ng = -1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid


print(ok)


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()


    # [ok, ng) - Maximum
    # (ng, ok] - Minimum
    # ok が 最終的な答え
    ok = N
    ng = -1
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        n = mid
        dp = [0] * (K + 1)
        dp[0] = 1
        for i in range(N):
            a = A[i]
            if i == n or a >= K:
                continue
            for j in range(K, -1, -1):
                dp[min(K, j + a)] |= dp[j]
        rst = any(dp[k] for k in range(max(0, K - A[n]), K))
        if rst:
            ok = mid
        else:
            ng = mid
    print(ok)


main()