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

import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def bfs(maze, H, W):
    visited = [[-1] * W for _ in range(H)]
    q = deque([])
    for h in range(H):
        for w in range(W):
            if maze[h][w] == "#":
                visited[h][w] = 0
                q.append((h, w))

    res = 0
    while q:
        h, w = q.popleft()

        for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W:
                if visited[nh][nw] == -1 and maze[nh][nw] == ".":
                    visited[nh][nw] = visited[h][w] + 1
                    if res < visited[nh][nw]:
                        res = visited[nh][nw]
                    q.append((nh, nw))

    return res


def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    ans = bfs(S, H, W)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def bfs(dist, black, H, W):
    q = deque(black)

    res = 0
    while q:
        h, w = q.pop()

        for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W:
                if dist[nh][nw] == -1:
                    dist[nh][nw] = dist[h][w] + 1
                    if res < dist[nh][nw]:
                        res = dist[nh][nw]
                    q.appendleft((nh, nw))

    return res


def main():
    H, W = map(int, input().split())
    A = [input() for _ in range(H)]
    black = []
    dist = [[-1] * W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#":
                black.append((h, w))
                dist[h][w] = 0

    ans = bfs(dist, black, H, W)
    print(ans)


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

n,q=map(int,input().split())
s=input()
l,r=[],[]
for _ in range(q):
    L,R=map(int,input().split())
    l.append(L)
    r.append(R)
for i in range(q):
    k=s[l[i]-1:r[i]]
    print(k.count("AC"))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
ans,c=[0]*q,[0]*n
k=0
for i in range(1,n):
    if s[i-1]=="A" and s[i]=="C":
        k+=1
    c[i]=k

for i in range(q):
    l,r=map(int,input().split())
    ans[i]=c[r-1]-c[l-1]
for i in ans:
    print(i)
### BUGGY CODE ###

N,K=map(int,input().split())
while N>=0:
    N=N-K
if abs(N)<abs(N+K):
    print(abs(N))
else:
    print(abs(N+K))

### FIXED CODE ###

N,K=map(int,input().split())
if abs(N-(N//K)*K)<abs((N-(N//K)*K)-K):
    print(N-(N//K)*K)
else:
    print(abs((N-(N//K)*K)-K))
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
s = 1
ans=[]
for i in range(k):
    s *= a[i]
ans.append(s)
for i in range(k, n):
    ans.append(ans[i - k] * a[i] // a[i - k])
    # print(ans)
    if ans[i - k] < ans[i - k + 1]:
        print("Yes")
    else:
        print("No")
    # print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(k, n):
    if a[i - k] < a[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    H, N = NMI()
    M = [NLI() for _ in range(N)]
    # dp[i] はiダメージ与えたときの最小の魔力
    dp = [10**10] * (H+10)
    dp[0] = 0
    for i in range(H):
        for m in M:
            dp[min(i+m[0], H)] = min(dp[min(i+m[0], H)], dp[i] + m[1])
    print(dp[H])



if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    H, N = NMI()
    M = [NLI() for _ in range(N)]
    # dp[i] はiダメージ与えたときの最小の魔力
    dp = [10**10] * (H+10)
    dp[0] = 0
    for i in range(H):
        for m in M:
            dp[min(i+m[0], H)] = min(dp[min(i+m[0], H)], dp[i] + m[1])
    print(dp[H])



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

n=int(input())
l=list(map(int,input().split()))
ans=[-1]*n
l.sort()
for i in range(n):
    if ans[i]==-1:
        ans[i]=1
        if i!=n-1:
          if l[i]==l[i+1]:
            ans[i]=0
        for j in range(i+1,n):
            if l[j]%l[i]==0:
                ans[j]=0
print(sum(ans))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
M = 10**6 + 1
cnt = [0] * M
for a in A:
    if cnt[a] != 0:
        cnt[a] += 1
        continue
    for b in range(a, M, a):
        cnt[b] += 1
ans = 0
for a in A:
    if cnt[a] == 1:ans += 1
print(ans)
### BUGGY CODE ###

import time
start=time.time()
import random
d=int(input())
c=list(map(int, input().split()))
s=[list(map(int, input().split())) for _ in range(d)]
t=[0]*26
ans=0
solution=[]
for i in range(1,d+1):
  tmp=s[i-1].index(max(s[i-1]))
  solution.append(tmp)
  t[tmp]=i
  ans+=s[i-1][tmp]
  for j in range(26):
    ans-=c[j]*(i-t[j])
now=time.time()
while now-start<1.95:
  di=random.randrange(1,d+1)
  qi=random.randrange(1,27)
  old=solution[di-1]
  solution[di-1]=qi-1
  tmp2=ans
  for _ in range(26):
    tmp2=tmp2-s[di-1][old]+s[di-1][qi-1]
  if ans-tmp2>=0:
    solution[di-1]=old
  else:
    ans=tmp2
  now=time.time()
for k in solution:
  print(k+1)

### FIXED CODE ###

d=int(input())
c=list(map(int, input().split()))
s=[list(map(int, input().split())) for _ in range(d)]
t=[0]*26
ans=0
for i in range(1,d+1):
  tmp=s[i-1].index(max(s[i-1]))
  print(tmp+1)
### BUGGY CODE ###

import sys
def 解():
    L,N=[int(_) for _ in input().split()]
    aX=[int(_) for _ in sys.stdin.readlines()]
    iMax = max(aX[0],L-aX[0],aX[-1],L-aX[-1])
    if 1 < N:
        for i in range(N-1):

            lN = min(i,N-i-1)
            rN = min(i+1,N-i-1)
            R1 = aX[i]+ 2*sum(aX[i-lN:i]) + 2*(rN*L-(sum(aX[i+1:i+rN+1])))

            i += 1
            lN = min(i,N-i)
            rN = min(i,N-i-1)
            R2 = (L- aX[i])+ 2*sum(aX[i-lN:i]) + 2*(rN*L-(sum(aX[i+1:i+rN+1])))

            iMax = max(R1,R2,iMax)
    print(iMax)
解()


### FIXED CODE ###

import sys
def 解():
    L,N=[int(_) for _ in input().split()]
    aX=[int(_) for _ in sys.stdin.readlines()]
    iMax = max(aX[0],L-aX[0],aX[-1],L-aX[-1])
    accX = [0]*(N+1)
    accX[0]=aX[0]
    for i in range(1,N):
        accX[i]=accX[i-1]+aX[i]

    if 1 < N:
        for i in range(N-1):

            lN = min(i,N-i-1)
            rN = min(i+1,N-i-1)
            #R1 = aX[i]+ 2*sum(aX[i-lN:i]) + 2*(rN*L-(sum(aX[i+1:i+rN+1])))
            R1 = aX[i]+ 2*(accX[i-1]-accX[i-lN-1]) + 2*(rN*L-(accX[i+rN]-accX[i]))

            i += 1
            lN = min(i,N-i)
            rN = min(i,N-i-1)
            #R2 = (L- aX[i])+ 2*sum(aX[i-lN:i]) + 2*(rN*L-(sum(aX[i+1:i+rN+1])))
            R2 = (L- aX[i])+ 2*(accX[i-1]-accX[i-lN-1]) + 2*(rN*L-(accX[i+rN]-accX[i]))

            iMax = max(R1,R2,iMax)
    print(iMax)
解()
### BUGGY CODE ###

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

array = [list(map(int, input().split())) for i in range(m)]
array_ans = []
myset = set()

for i in range(m):
    myset.add(array[i][0])


for i in myset:
    array_temp = [[array[j][0], array[j][1], j] for j in range(m) if array[j][0] == i]
    array_temp = sorted(array_temp, key=lambda x: x[1])
    for j in range(len(array_temp)):
        array_temp[j][1] = j + 1
    array_ans.extend(array_temp)

array_ans = sorted(array_ans, key=lambda x: x[2])


for i in range(m):
    out = '%06d' % array_ans[i][0] + '%06d' % array_ans[i][1]
    print(out)


### FIXED CODE ###

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

array = []
for i in range(m):
    temp = list(map(int, input().split()))
    temp.append(i)
    array.append(temp)

array = sorted(array, key=lambda x: (x[0], x[1]))

count = 1
eq = True

for i in range(m):
    if eq is False:
        count = 1
    array[i][1] = count
    count += 1
    if i != m - 1:
        if array[i][0] == array[i + 1][0]:
            eq = True
        else:
            eq = False

array = sorted(array, key=lambda x: x[2])

for i in range(m):
    out = '%06d' % array[i][0] + '%06d' % array[i][1]
    print(out)
### BUGGY CODE ###

from operator import add,mul,sub,truediv,floordiv
from functools import reduce

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

mul = reduce(lambda x,y:x*y, A)
if mul > 10**18:
    print('-1')
else:
    print(mul)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
m = A[0]
if 0 in A:
    print('0')
else:
    for i in range(1,N):
        m *= A[i]
        if m > 10**18:
            print('-1')
            break
    else:
        print(m)
### BUGGY CODE ###

N = int(input())

A = list(input().split())

Q = int(input())

for _ in range(Q):
    B, C = input().split()
    A = [s.replace(B, C) for s in A]
    print(sum([int(i) for i in A]))

### FIXED CODE ###

from collections import defaultdict
 
d = defaultdict(int)
 
N = input()
A = list(map(int, input().split())) 
for i in A:
    d[i] += 1

ans = sum(A)
 
Q = int(input())

for _ in range(Q):
    B, C = map(int, input().split())
    ans = ans - B*d[B] + C*d[B]
    print(ans)
    d[C] += d[B]
    d[B] = 0
### BUGGY CODE ###

X,Y=map(int,input().split())
x=2*X-Y
y=2*Y-X
over=1
under=1
i=x+y
if x%3!=0 or y%3!=0:
    print(0)
else:
    x=x//3
    y=y//3
    n=x+y
    r=min(x,y)
    for i in range(max(x,y)):
        over*=(n-i)
        under*=(n-r-i)
    ans=over//under
    print(ans%(10**9+7))

### FIXED CODE ###

X,Y=map(int,input().split())
mod=10**9+7
MAX=X+Y+1

fac=[1,1]
inv_t=[0,1]
finv=[1,1]
for i in range(2,MAX):
    fac.append(fac[-1]*i%mod)
    inv_t += [inv_t[mod % i] * (mod - mod // i) % mod]
    finv.append(finv[i-1]*inv_t[i]%mod)

x=2*X-Y
y=2*Y-X

if x%3!=0 or y%3!=0 or x*y<0:
    print(0)
else:
    x=x//3
    y=y//3
    n=x+y
    r=min(x,y)
    print((fac[n]*finv[r]*finv[n-r])%mod)
### BUGGY CODE ###

N = int(input())
import copy
import math
def nP2(N):
    return (math.factorial(N)/((math.factorial(2))*math.factorial(N-2)))
L = list(map(int,input().split()))
Count = [0 for _ in range(N+1)]
for el in L:
    Count[el]+=1
for balls in L:
    res = 0
    Count[balls]-=1
    for i in Count:
        if i >= 2:
            res += nP2(i)
    Count[balls] += 1
    print(int(res))

### FIXED CODE ###

N = int(input())
import copy
import math
def nP2(N):
    return (math.factorial(N)/((math.factorial(2))*math.factorial(N-2)))
L = list(map(int,input().split()))
Count = [0 for _ in range(N+1)]
for el in L:
    Count[el]+=1
res = 1
for i in Count:
    if i>=2:
        res += nP2(i)
for balls in L:
    print(int(res-Count[balls]))
### BUGGY CODE ###

n = int(input())

x = []

for i in range(n):
	x.append(list(map(int,input().split())))
a = x[0][2]
b = 0
for i in range(101):
	for j in range(101):
		for k in range(a,a+201):
			for l in x:
				if l[2] == max(0,k-abs(i-l[0])-abs(j-l[1])):
					b += 1
			if b == n:
				print(i,j,k)
			b = 0


### FIXED CODE ###

n = int(input())

x = []

for i in range(n):
	a,b,c = map(int,input().split())
	x.append([c,a,b])
x.sort()
x.reverse()
a = 0
b = 0
for i in range(101):
	for j in range(101):
		for k in range(n):
			if x[k][0] != 0:
				if k == 0:
					a = x[k][0] + abs(i-x[k][1]) + abs(j-x[k][2])
					b += 1
				else:
					if a == x[k][0] + abs(i-x[k][1]) + abs(j-x[k][2]):
						b += 1
			else:
				if a- abs(i-x[k][1]) - abs(j-x[k][2]) <= 0:
					b += 1
		if b == n:
			print(i,j,a)
		b = 0
### BUGGY CODE ###

"""
明らかに無理→最小が2つ無い or 最小同士がペアになってない
(最小から接続する頂点に最小がない)

満たしてる→最小の辺を置いちゃおう
小さい奴からGreedyに置いてく？

自分の周りにendしてるやつ or 大きさが同じやつがあったら繋げちゃう
そのとき白黒はどうでも良さそう？

"""
import sys

N,M = map(int,input().split())

D = list(map(int,input().split()))

dic = [[] for i in range(N)]

for i in range(M):

    U,V = map(int,input().split())
    U -= 1
    V -= 1

    dic[U].append([V,i])
    dic[V].append([U,i])

for i in range(N):
    dic[i].sort()

end = [False] * N
color = [0] * N
q = []
ans = [10**9] * M

for i in range(N):
    q.append([D[i],i])
q.sort()
#print (q)

for i in range(N):
    if end[q[i][1]]:
        continue
    flag = False
    for vi in dic[q[i][1]]:
        nexv = vi[0]
        mind = vi[1]
        nowd = q[i][0]
        nowp = q[i][1]
        #print (vi,q[i])

        if end[nexv]:
            flag = True
            color[nowp] = color[nexv] ^ 1
            end[nowp] = True
            ans[mind] = nowd
            break
        elif D[nexv] == nowd:
            
            flag = True
            color[nowp] = color[nexv] ^ 1
            end[nowp] = True
            end[nexv] = True
            ans[mind] = nowd
            break
    #print (ans)

    if not flag:
        print (-1)
        sys.exit()


S = ""
for i in color:
    if i == 0:
        S += "B"
    else:
        S += "W"

print (S)

print (" ".join(map(str,ans)))
        

### FIXED CODE ###

"""
明らかに無理→最小が2つ無い or 最小同士がペアになってない
(最小から接続する頂点に最小がない)

満たしてる→最小の辺を置いちゃおう
小さい奴からGreedyに置いてく？

自分の周りにendしてるやつ or 大きさが同じやつがあったら繋げちゃう
そのとき白黒はどうでも良さそう？

"""
import sys

N,M = map(int,input().split())

D = list(map(int,input().split()))

dic2 = [[] for i in range(N)]

for i in range(M):

    U,V = map(int,input().split())
    U -= 1
    V -= 1

    if len(dic2[U]) == 0 or dic2[U][0][0] > D[V]:
        dic2[U] = []
        dic2[U].append([D[V],V,i])
    if len(dic2[V]) == 0 or dic2[V][0][0] > D[U]:
        dic2[V] = []
        dic2[V].append([D[U],U,i])


dic = [[] for i in range(N)]
for i in range(N):
    for j in dic2[i]:
        dic[i].append([j[1],j[2]])

#print (dic)

end = [False] * N
color = [0] * N
q = []
ans = [10**9] * M

for i in range(N):
    q.append([D[i],i])
q.sort()
#print (q)

for i in range(N):
    if end[q[i][1]]:
        continue
    flag = False
    for vi in dic[q[i][1]]:
        nexv = vi[0]
        mind = vi[1]
        nowd = q[i][0]
        nowp = q[i][1]
        #print (vi,q[i])

        if end[nexv]:
            flag = True
            color[nowp] = color[nexv] ^ 1
            end[nowp] = True
            ans[mind] = nowd
            break
        elif D[nexv] == nowd:
            
            flag = True
            color[nowp] = color[nexv] ^ 1
            end[nowp] = True
            end[nexv] = True
            ans[mind] = nowd
            break
        break
    #print (ans)

    if not flag:
        print (-1)
        sys.exit()


S = []
for i in color:
    if i == 0:
        S.append("B")
    else:
        S.append("W")

print ("".join(S))

print (" ".join(map(str,ans)))
### BUGGY CODE ###

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

dp = [10 ** 9 + 7] * (n + k + 10)
dp[0] = 0

for i in range(n):
    for j in range(1, k + 1):
        if i + j < n:
            if dp[i + j] == 10 ** 9 + 7:
                dp[i + j] = dp[i] + abs(h[i] - h[i + j])
            else:    
                dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]))
        else:
            break
        
print(dp[n - 1])


### FIXED CODE ###

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [float('inf')] * (n + k + 10)
dp[0] = 0

for i in range(n):
    for j in range(1, k + 1):
        if i + j < n:
            if dp[i + j] == float('inf'):
                dp[i + j] = dp[i] + abs(h[i + j] - h[i])
            else:
                dp[i + j] = min(dp[i + j], dp[i] + abs(h[i + j] - h[i]))
        else:
            break


print(dp[n-1])
### BUGGY CODE ###

s = input()[::-1]

sum_of_digits = 0

cnts = [0] * 2019
cnts[0] = 1

d = 1

for c in s:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
    d % 2019
    cnts[sum_of_digits] += 1

ans = 0

for cnt in cnts:
    ans += cnt * (cnt - 1) // 2
 
print(ans)

### FIXED CODE ###

s = input()[::-1]

sum_of_digits = 0

cnts = [0] * 2019
cnts[0] = 1

d = 1

for c in s:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
    d %= 2019
    cnts[sum_of_digits] += 1

ans = 0

for cnt in cnts:
    ans += cnt * (cnt - 1) // 2
 
print(ans)
### BUGGY CODE ###

N,K =  map(int,input().split())
l = list(map(int,input().split()))
score=[]
for i in range(K-1,N):
    tmp_score = 1
    for j in range(0,K):
        tmp_score *= l[i-j]
    score.append(tmp_score)
for i in range(len(score)-1):
    if score[i] < score[i+1]:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

N,K =  map(int,input().split())
l = list(map(int,input().split()))
score=[]
for i in range(K,N):
    if l[i-K] < l[i]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
cnt = 0
for index, i in enumerate(A):
    #print("index:{}".format(index))
    for j in range(index + 1):
        if i > A[j]:
            #print("break:{}".format(j))
            break
        elif index == j:
            ans += 1
            break
        #print("j:{}".format(j))




print(ans)

### FIXED CODE ###

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


for index, i in enumerate(A):
    if index == 0:
        ans += 1
        small = i


    elif small >= i:
        ans += 1
        small = i      

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

L, R = map(int, input().split())
ans = 2019

for i in range(L, R):
    for j in range(i+1, R+1):
        a = i % 2019
        b = j % 2019
        x = (a * b) % 2019
        ans = min(ans, x)

print(ans)

### FIXED CODE ###

L, R = map(int, input().split())
R = min(L+2019, R)
ans = 2019
Flag = False

for i in range(L, R):
    for j in range(i+1, R+1):
        x = (i * j) % 2019
        ans = min(ans, x)
        if ans == 0:
            Flag = True
            break
    if Flag:
        break

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

from itertools import accumulate
N, M, K = map(int,input().split())
A_list = [0] + list(map(int,input().split()))
B_list = [0] + list(map(int,input().split()))
A_sums_list = list(accumulate(A_list))
B_sums_list = list(accumulate(B_list))

for n in range(N + 1):
    if A_sums_list[n] > K:
        break
    A_max = n
for m in range(M + 1):
    if B_sums_list[m] > K:
        break
    B_max = m
ans = max(A_max, B_max)
for i in reversed(range(A_max + 1)):
    for j in reversed(range(B_max + 1)):
        if i + j > ans:
            if A_sums_list[i] + B_sums_list[j] <= K:
                ans = i + j
        else:
            break
print(ans)

### FIXED CODE ###

import itertools
n, m, k = map(int, input().split())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))

sa = list(itertools.accumulate(a))
sb = list(itertools.accumulate(b))

output = 0
j = m
for i in range(n + 1):
    if sa[i] > k:
        break
    while sa[i] + sb[j] > k:
        j -= 1
    if output < i + j:
        output = i + j
print(output)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=998244353
def input(): return sys.stdin.readline().rstrip()

def main():
    N,S=map(int,input().split())
    A=list(map(int,input().split()))
    dp=[[[0]*3 for _ in range(S+1)] for _ in range(N+1)]
    dp[0][0][0]=1
    for i in range(N):
        for j in range(S+1):
            dp[i+1][j][0]+=dp[i][j][0]
            dp[i+1][j][0]%=MOD
            dp[i+1][j][1]+=dp[i][j][0]+dp[i][j][1]
            dp[i+1][j][1]%=MOD
            dp[i+1][j][2]+=dp[i][j][0]+dp[i][j][1]+dp[i][j][2]
            dp[i+1][j][2]%=MOD
            if j+A[i]<=S:
                dp[i+1][j+A[i]][1]+=dp[i][j][0]+dp[i][j][1]
                dp[i+1][j+A[i]][1]%=MOD
                dp[i+1][j+A[i]][2]+=dp[i][j][0]+dp[i][j][1]
                dp[i+1][j+A[i]][2]%=MOD
    print(dp[-1][-1][2])

if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=998244353
def input(): return sys.stdin.readline().rstrip()

def main():
    N,S=map(int,input().split())
    A=list(map(int,input().split()))
    dp0=[[0 if i!=0 else 1 for i in range(S+1)] for _ in range(N+1)]
    dp1=[[0]*(S+1) for _ in range(N+1)]
    dp2=[[0]*(S+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(S+1):
            b=int(j==0)
            dp1[i+1][j]+=dp1[i][j]+b
            dp2[i+1][j]+=dp1[i][j]+dp2[i][j]+b
            dp1[i+1][j]%=MOD
            dp2[i+1][j]%=MOD
            if j+A[i]<=S:
                dp1[i+1][j+A[i]]+=dp1[i][j]+b
                dp2[i+1][j+A[i]]+=dp1[i][j]+b
                dp1[i+1][j+A[i]]%=MOD
                dp2[i+1][j+A[i]]%=MOD
    print(dp2[-1][-1])

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

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

a.sort()

import collections
c = collections.Counter(a)

d=[]
for ck,cv in c.items():
    if cv>=2:
       d.append(ck) 
dset=set(d)
    
aa=[]

icnt=0
while True:
    aa.append(a[0])
    a2=[]
    for i in range(1,len(a)):
        if a[i]%a[0]!=0:
            a2.append(a[i])
    a=a2.copy()
#    print(aa,a)     
    if len(a2)==0:
        break
    icnt+=1
#    if icnt>10:break

aaset=set(aa)
aaset=aaset-dset    
print(len(aaset))

### FIXED CODE ###

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

a.sort()
amax=max(a)
dp=[True]*(amax+1)

import collections
c = collections.Counter(a)

d=[]
for ck,cv in c.items():
    if cv>=2:
       d.append(ck) 
dset=set(d)
    
aa=set()
for ai in a:
    if dp[ai]:
        aa.add(ai)
        for aj in range(ai*2,amax+1,ai):
            dp[aj]=False

aa=aa-dset    
print(len(aa))
### BUGGY CODE ###

from sys import stdin
import math
import itertools
import re


def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix


def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix


def makeInt(line):
    return int(line.rstrip())


def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]


def solve(input_string):
    S = input_string[1]
    intMatrix = makeIntMatrix(input_string[2:])
    #print(input_string[2:])
    for line in intMatrix:
        l, r = line
        #print(l, r)
        #print(S[l:r+1])
        cnt = len(re.findall(r'AC', S[l-1:r]))
        print(cnt)
    return


def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    #print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t=[0]*(N+1)
for i in range(N):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
  l, r = map(int, input().split())
  print(t[r-1] - t[l-1])
### BUGGY CODE ###



N = int(input())
S = input()
#N = 8
#S = 'WWWWWEEE'


min = 1000000
for i in range(1,N-1):
    l = S[i]
    if l == 'W':
        left = S[0:i-1].count('W')
        right = S[i+1:].count('E')
    else:
        left = S[0:i-1].count('W')
        right = S[i+1:].count('E')
    sum = right + left
    #print(l, sum, left, right)
    if min > sum:
        min = sum
print(min)



### FIXED CODE ###



N = int(input())
S = input()
#N = 12
#S = 'WEWEWEEEWWWE'


min = 1000000
e = S.count('E')
w = 0

for i in range(0,N):
    flag = 0
    now = S[i]
    if now == 'E':
        e = e - 1
    else:
        flag = 1
    sum = w + e
    if min > sum:
        min = sum
    if flag:
        w = w + 1
print(min)
### BUGGY CODE ###

s = input()
cnt = 0
while True:
    idx = s.find("01")
    if idx != -1:
        cnt += 2
        s = s[:idx] + s[idx+2:]
    idxx = s.find("10")
    if idxx != -1:
        cnt += 2
        s = s[:idxx] + s[idxx+2:]
    if idx == -1 and idxx == -1:
        break
print(cnt)

### FIXED CODE ###

s = input()
cntB = s.count("0")
cntR = s.count("1")
print(min(cntR, cntB)*2)