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

# D - Lamp
import numpy as np

h, w = map(int, input().split())
s = []
for i in range(h):
    s.append(list(input()))
s = np.array(s)

# 横について考える
tblW = np.zeros((h, w),dtype=np.int64)
for i in range(h):
    for j in range(w):
        if s[i, j]=='#' or tblW[i, j]>0:
            continue
        else:
            cnt = 1
            while j+cnt<w and s[i, j+cnt]!='#':
                cnt += 1
            tblW[i, j:j+cnt] = cnt
#print(tblW)
    
# 縦について考える
tblH = np.zeros((h, w),dtype=np.int64)
for j in range(w):
    for i in range(h):
        if s[i, j]=='#' or tblH[i, j]>0:
            continue
        else:
            cnt = 1
            while i+cnt<h and s[i+cnt, j]!='#':
                cnt += 1
            tblH[i:i+cnt, j] = cnt
#print(tblH)

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, tblH[i, j]+tblW[i, j]-1)

print(ans)


### FIXED CODE ###

# D - Lamp
import numpy as np

h, w = map(int, input().split())

# 0: 障害物または壁 1: 通路
# 上下左右の壁の分を加味して+2したグリッドを用意する。
g = np.zeros((h+2,w+2),dtype=np.int64)
for i in range(h):
    grid = np.array(list(input()))
    g[i+1, 1:w+1] = (grid=='.')

# 横について考える
gW = np.copy(g)
gW = np.ravel(gW)
tWLeft = np.arange((w+2)*(h+2))
tWRight = np.copy(tWLeft)

tWLeft[gW==1] = 0
tWRight[gW[::-1]==1] = 0

np.maximum.accumulate(tWLeft, out=tWLeft)
np.maximum.accumulate(tWRight, out=tWRight)

tWRight = len(tWRight) - 1 - tWRight[::-1]

tW = tWRight-tWLeft-1
tW[gW==0] = 0
tW = tW.reshape(h+2, w+2)

# 縦について考える
gH = np.copy(g.T)
gH = np.ravel(gH)
tHLeft = np.arange((w+2)*(h+2))
tHRight = np.copy(tHLeft)

tHLeft[gH==1] = 0
tHRight[gH[::-1]==1] = 0

np.maximum.accumulate(tHLeft, out=tHLeft)
np.maximum.accumulate(tHRight, out=tHRight)

tHRight = len(tHRight) - 1 - tHRight[::-1]

tH = tHRight-tHLeft-1
tH[gH==0] = 0
tH = tH.reshape(w+2, h+2).T

#print(tW)
#print(tH)
print(np.max(tW+tH-1))


'''
# 横について考える
tblW = np.zeros((h, w),dtype=np.int64)
for i in range(h):
    for j in range(w):
        if grid[i, j]=='#' or tblW[i, j]>0:
            continue
        else:
            cnt = 1
            while j+cnt<w and grid[i, j+cnt]!='#':
                cnt += 1
            tblW[i, j:j+cnt] = cnt
print(tblW)
    
# 縦について考える
tblH = np.zeros((h, w),dtype=np.int64)
for j in range(w):
    for i in range(h):
        if grid[i, j]=='#' or tblH[i, j]>0:
            continue
        else:
            cnt = 1
            while i+cnt<h and grid[i+cnt, j]!='#':
                cnt += 1
            tblH[i:i+cnt, j] = cnt
print(tblH)

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, tblH[i, j]+tblW[i, j]-1)

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

# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    S = input().rstrip()

    N = len(S)
    S = int(S)

    M = [0 for i in range(2019)]

    for i in range(N+1):
        T = S % (10**i)
        M[T%2019] += 1

    res = 0

    for m in M:
        res += m * (m-1) // 2


    print(res)



main()


### FIXED CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit, i8


# @njit(i8[:](i8,i8,i8[:]))
@njit
def loof(a,N):
    M = np.zeros(2019,dtype=np.int16)
    M[0] += 1
    T = 0
    r = 1
    T += a[-1] * r
    T %= 2019
    M[T] += 1
    for i in range(N-2,-1,-1):
        r *= 10
        r %= 2019
        T += a[i] * r
        T %= 2019
        M[T] += 1
    return M


# @njit
# def pow_mod(a,n,mod):
#     memo = np.array([1])
#     if n >= 1:
#         for i in range(n-1):
#             memo = np.append(memo,memo[-1]*a%mod)
#         return memo
#     else:
#         return memo[0]


def main():
    S = input().rstrip()
    S = list(map(int,list(S)))
    a = np.array(S)

    N = len(a)

    # memo = pow_mod(10,N,2019)
    M = loof(a,N)

    res = 0

    for m in M:
        res += m * (m-1) // 2

    print(res)


main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = [int(i) for i in input().split(' ')]

sorted_a = sorted(a)
for value in sorted_a:
    print(a.index(value) + 1, end=' ')
print()


### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = [int(i) for i in input().split(' ')]

dict = {}
for i, value in enumerate(a):
    dict[value] = i + 1

a.sort()

for i in a:
    print(dict[i], end=' ')
print()
### BUGGY CODE ###

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

cnt2 = 0
cnt1 = 1

for i in range(1,n):
    if i in a:
        cnt2, cnt1 = cnt1, 0
    else:
        cnt2, cnt1 = cnt1, cnt2+cnt1
else:
    ans = (cnt2+cnt1)%1000000007

print(ans)


### FIXED CODE ###

n,m = map(int,input().split())
aa = [int(input()) for i in range(m)]

cnt2 = 0
cnt1 = 1
aa.append(-1)
a = aa.pop(0)


for i in range(1,n):
    if i == a:
        cnt2, cnt1 = cnt1, 0
        a = aa.pop(0)
    else:
        cnt2, cnt1 = cnt1, cnt2+cnt1
else:
    ans = (cnt2+cnt1)%1000000007

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

n = int(input())
n_list = list(map(int, input().split()))
q = int(input())

n_dic = {}
for i in n_list:
    n_dic.setdefault(i, 0)
    n_dic[i] += 1

for i in range(q):
    b, c = map(int, input().split())
    if b in n_dic:
        n_dic.setdefault(c, 0)
        n_dic[c] += n_dic[b]
        del n_dic[b]

    result = 0
    for k in n_dic:
        result += k * n_dic[k]
    print(result)


### FIXED CODE ###

n = int(input())
n_list = list(map(int, input().split()))
q = int(input())

n_dic = {}
for i in n_list:
    n_dic.setdefault(i, 0)
    n_dic[i] += 1

result = 0
for k in n_dic:
    result += k * n_dic[k]

for i in range(q):
    b, c = map(int, input().split())
    if b in n_dic:
        n_dic.setdefault(c, 0)
        n_dic[c] += n_dic[b]
        result = result + (c-b)*n_dic[b]
        del n_dic[b]

    print(result)
### BUGGY CODE ###

import math
k=int(input())
k+=1
ans=0
for i in range(1,k):
    for j in range(1,k):
        for z in range(1,k):
            ans+=math.gcd(math.gcd(i,j),z)
print(ans)

### FIXED CODE ###

import math
k=int(input())
k+=1
ans=0
for i in range(1,k):
    for j in range(1,k):
        for z in range(1,k):
            ans+=math.gcd(math.gcd(i,j),z)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2**31-1)
input = sys.stdin.readline
write = sys.stdout.write
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = True

def main():
    N, M = LMIIS()
    dp = [0] * (M+1)

    DV = [[0] for _ in range(M+1)]

    for _ in range(N):
        A,B = LMIIS()
        if A > M:
            continue
        DV[A].append(B)

    for l in DV:
        l.sort(reverse=True)
    ans = 0
    tmpL = []
    for i in range(1,M+1):
        tmpL += DV[i][:M-i+1]
        tmpL.sort(reverse=True)
        ans += tmpL.pop(0)
    print(ans)
        
        



    pass
if __name__ == '__main__':
    main()


### FIXED CODE ###


import sys
sys.setrecursionlimit(2**31-1)
input = sys.stdin.readline
write = sys.stdout.write
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = True

def main():
    N, M = LMIIS()
    dp = [0] * (M+1)

    DV = [[0] for _ in range(M+1)]

    for _ in range(N):
        A,B = LMIIS()
        if A > M:
            continue
        DV[A].append(B)


    from heapq import heappush, heappop
    ans = 0
    h = []
    for l in DV:
        for item in l:
            heappush(h,-item)
        ans -= heappop(h)
    print(ans)
        
        



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

from itertools import combinations

n, x, y = map(int, input().split())

cnt = [0] * n
for i, j in combinations(range(n), 2):
    i, j = i + 1, j + 1
    dist = min(abs(j - i), abs(i - x) + abs(j - y) + 1,
               abs(i - y) + abs(j - x) + 1)
    cnt[dist] += 1

for i in range(1, n):
    print(cnt[i])


### FIXED CODE ###

from itertools import combinations

n, x, y = map(int, input().split())

cnt = [0] * n
for i, j in combinations(range(n), 2):
    i, j = i + 1, j + 1
    dist = min(abs(j - i), abs(i - x) + abs(j - y) + 1,
               abs(i - y) + abs(j - x) + 1)
    cnt[dist] += 1

for i in range(1, n):
    print(cnt[i])
### BUGGY CODE ###

n = int(input())
s = str(input())
ans = float('Inf')
for i in range(n):
    w = s[:i].count("W")
    e = s[i:].count("E")
    ans = min(ans,w+e)
print(ans)

### FIXED CODE ###

from itertools import accumulate
n = int(input())
s = str(input())
tt = [1 if i  == "W" else 0 for i in s]
B = [0] + tt
B = list(accumulate(B))
#print(B)
ans = float('Inf')
for i in range(0,n+1):
    #w = s[:i].count("W")
    ##W = sum(tt[:i])
    w = B[i]
    #print(W,w)
    #e = s[i:].count("E")
    #E = len(tt[i:]) - sum(tt[i:])
    e = n - i - B[-1] + B[i]
    #print(E,e)
    #ans = min(ans,W+E)
    ans = min(ans,w+e)
print(ans)
### BUGGY CODE ###


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
k = int(input())
if  k%2==0 or k%5==0:
    print(-1)
else:
    se = prime_factorize(k)
    k_ = k
    if not 7 in se:
        k_ = k*7

    K = int(str(k_)[-1])
    # print(K)
    if K==1:
        # print("a")
        x = 7
    elif K==3:
        x=9
    elif K==7:
        x = 1
    elif K==9:
        x = 3
    z = 0
    # print(x)
    while True:
        s = 10*z + x
        q = k_ * s
        # print(q)
        if str(q)=="7"*len(str(q)):
            print(len(str(q)))
            break
        z+=1

### FIXED CODE ###

k = int(input())
c = 0
if k%2 ==0 or k%5==0:
    print(-1)
    c=1
elif k==1:
    print(1)
    c=1
if c==0:
    t = 7

    for i in range(k):
        if int(t)%k==0 :
            print(i+1)
            break
        t = (10*t+7)%k
### BUGGY CODE ###

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

for i in range(N):
  if i<K:
    temp*=A[i]
  else:
    score=(temp//A[i-K])*A[i]
    if temp<score:
      print('Yes')
    else:
      print('No')
    temp=score

### FIXED CODE ###

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

for i in range(K,N):
  if A[i]>A[i-K]:
      print('Yes')
  else:
      print('No')
### BUGGY CODE ###

import sys
from itertools import combinations as combi
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
cs = [[0] * 61 for _ in range(N + 1)]
mod = 10 ** 9 + 7
for i in range(N):
  for j in range(61):
    t = 1 << j
    #print(a[i], t, a[i] & t)
    cs[i + 1][j] = cs[i][j] + (a[i] & t)
res = 0
#print(cs[-1])
#print(cs[2])
for i in range(N):
  t = 0
  for j in range(61):
    if a[i] & (1 << j) != 0:
      #if i == 1: print((1 << j) * (N - i - 1), (cs[-1][j] - cs[i + 1][j]))
      t += (1 << j) * (N - i - 1) - (cs[-1][j] - cs[i + 1][j])
    else:
      #if i == 1: print(a[i] & (1 << j), (cs[-1][j] - cs[i + 1][j]))
      t += (cs[-1][j] - cs[i + 1][j])
    #if i == 1: print(t)
    t %= mod
  res += t
  res %= mod
print(res % mod)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
mxbit = 0
for i in range(N):
  mxbit = max(mxbit, a[i].bit_length())
cs = [0] * mxbit
for i in range(N):
  for j in range(mxbit):
    t = 1 << j
    #print(a[i], t, a[i] & t)
    x = (a[i] & t) > 0
    cs[j] += x
res = 0
#print(cs[-1])
#print(cs)
for i in range(N):
  t = 0
  for j in range(mxbit):
    x = 1 << j
    if a[i] & x != 0:
      x %= mod
      #if i == 1: print((1 << j) * (N - i - 1), (cs[-1][j] - cs[i + 1][j]))
      t += x * (N - (cs[j]))
    else:
      x %= mod
      #if i == 1: print(a[i] & (1 << j), (cs[-1][j] - cs[i + 1][j]))
      t += x * cs[j]
    #print(t)
    t %= mod
  res += t
  res %= mod
print(res % mod * pow(2, mod - 2, mod) % mod)
### BUGGY CODE ###

import collections

n = int(input())
a = list(map(int, input().split()))
l = []
ans = 0

for i in range(n):
    if {i+1, a[i]} in l:
        ans += 1
    else:
        l.append({i+1, a[i]})

print(ans)


### FIXED CODE ###

import collections

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

for i in range(n):
    if i+1 == a[a[i]-1]:
        ans += 1

print(ans//2)
### BUGGY CODE ###

import math

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

'''
factorial_list = [1] * (N+1)
for i in range(1,N+1):
    factorial_list[i] = factorial_list[i-1] * i

def combinations_count(n, r):
    return factorial_list[n] // (factorial_list[n - r] * factorial_list[r])
'''

def nCk(n, k):
    ret = 1
    mo = 10**9 + 7
    for i in range(k):
        ret = ret * (n - i) * pow(i + 1, mo - 2, mo) % mo
    return ret

def one_two_comb(N):
    two_n = N//2
    comb_list = []
    for i in range(1,two_n+1):
        comb_list.append([N-i,i])
    return comb_list

def sum_comb(comb_list):
    comb_sum = 0
    for val in comb_list:
        comb_sum += nCk(val[0],val[1])
    return comb_sum
    

diff_list = []
current_num = 0
max_diff = -1
for a in An:
    diff = a - current_num
    if diff == 0:
        print(0)
        exit(0)
    diff_list.append(diff)
    current_num = a +1
diff = N+1 - current_num
diff_list.append(diff)
#print(diff_list)


all_sum = 1
for idx,diff in enumerate(diff_list):
    if idx == 0 or len(diff_list):
        diff -= 1
    '''
    else:
        diff -= 2
    '''

    if diff == 0:
        all_sum *= 1
    else:
        internal_comb_list = one_two_comb(diff)
        comb_count = sum_comb(internal_comb_list) + 1
        if all_sum > 10**9+7:
            all_sum = all_sum%(10**9+7)
        all_sum *= comb_count
print(all_sum%(10**9+7))



### FIXED CODE ###

import math

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

'''
factorial_list = [1] * (N+1)
for i in range(1,N+1):
    factorial_list[i] = factorial_list[i-1] * i

def combinations_count(n, r):
    return factorial_list[n] // (factorial_list[n - r] * factorial_list[r])
'''

feruma_list = [1] * (N+1)
for i in range(2,N+1):
    feruma_list[i] = feruma_list[i-2] + feruma_list[i-1]


def nCk(n, k):
    ret = 1
    mo = 10**9 + 7
    for i in range(k):
        ret = ret * (n - i) * pow(i + 1, mo - 2, mo) % mo
    return ret

def one_two_comb(N):
    two_n = N//2
    comb_list = []
    for i in range(1,two_n+1):
        comb_list.append([N-i,i])
    return comb_list

def sum_comb(comb_list):
    comb_sum = 0
    for val in comb_list:
        comb_sum += nCk(val[0],val[1])
    return comb_sum
    

diff_list = []
current_num = 0
max_diff = -1
for a in An:
    diff = a - current_num
    if diff == 0:
        print(0)
        exit(0)
    diff_list.append(diff)
    current_num = a +1
diff = N+1 - current_num
diff_list.append(diff)
#print(diff_list)


all_sum = 1
for idx,diff in enumerate(diff_list):
    
    if idx == 0 or len(diff_list):
        diff -= 1
    '''
    if diff == 0:
        all_sum *= 1
    else:
        internal_comb_list = one_two_comb(diff)
        comb_count = sum_comb(internal_comb_list) + 1
        if all_sum > 10**9+7:
            all_sum = all_sum%(10**9+7)
        all_sum *= comb_count
    '''

    comb_count = feruma_list[diff]
    if all_sum > 10**9+7:
        all_sum = all_sum%(10**9+7)
    all_sum *= comb_count

print(all_sum%(10**9+7))
### BUGGY CODE ###

a,b=map(int,input().split())
l = [x+y+z for x in range(a+1) for y in range(a+1) for z in range(a+1)]
print(l.count(b))

### FIXED CODE ###

k,s=map(int,input().split())
print(len([1 for z in range(k+1) for y in range(k+1) if 0<=s-y-z<=k]))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
mod=pow(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
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1]
for i in range( 2, n + 2 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
# 二つあるやつはどの場所にあるか検索
f=[-1]*(n+1)
l,r=0,0
for i in range(n):
  ai=a[i]
  if f[ai]==-1:
    f[ai]=i
  else:
    l=f[ai]
    r=n-i
    break
for k in range(1,n+2):
  a=cmb(n+1,k,mod)
  for i in range(k+1):
    a-=cmb(l,i,mod)*cmb(r,k-i-1,mod)
  print(a)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
mod=pow(10,9)+7
#ans=[int(input()) for _ in range(n+1)]
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
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1]
for i in range( 2, n + 2 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
# 二つあるやつの左の方の左にl個、右のやつの右のほうにr個数字がある
f=[-1]*(n+1)
l,r=0,0
for i in range(n+1):
  ai=a[i]
  if f[ai]==-1:
    f[ai]=i
  else:
    l=f[ai]
    r=n-i
    break
for k in range(1,n+2):
  a=cmb(n+1,k,mod)
  if l+r>=k-1:
	  a-=cmb(l+r,k-1,mod)
  #print(a==ans[k-1],a,ans[k-1])
  print(a%mod)
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
p_min = []
for ind in range(1,n+1):
    p_min.append(min(p[:ind]))
# print(p_min)
cnt = 0
for ind in range(n):
    if p[ind] <= p_min[ind]:
        cnt += 1  
print(cnt)


### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
p_min = p[0]
cnt = 0
for ind in range(n):
    if p[ind] <= p_min:
        cnt += 1
    p_min = min(p[ind],p_min)
print(cnt)
### BUGGY CODE ###

# D Anything Goes to Zero

import copy

def main():
  n = int(input())
  x = input()
  for i in range(n):
    xi = copy.copy(x)
    if xi[i] == "1":
      xi = xi[:i] + "0" + xi[i+1:]
    else:
      xi = xi[:i] + "1" + xi[i+1:]
    xi = int(xi, 2)

    ans = 0
    while xi != 0:
      xi = xi % popcount(xi)
      ans += 1
    print(ans)

        
def popcount(x):
  n = bin(x)[2:]
  cnt = 0
  for i in n:
    if i == "1":
      cnt += 1
  return cnt


if __name__ == "__main__":
  main()

### FIXED CODE ###

# D Anything Goes to Zero

n = int(input())
x = input()

original_pop_count = x.count("1")
one_pop_count = original_pop_count - 1
zero_pop_count = original_pop_count + 1

one_mod = 0
zero_mod = 0
for b in x:
  if one_pop_count != 0:
    one_mod = (one_mod * 2 + int(b)) % one_pop_count
  zero_mod = (zero_mod * 2 + int(b)) % zero_pop_count

#fの前計算
f = [0] * 220000
pop_count = [0] * 220000
for i in range(1, 220000):
  pop_count[i] = pop_count[i//2] + i % 2
  f[i] = f[i % pop_count[i]] + 1

#pow2の前計算
one_pow2 = [1] * 220000
zero_pow2 = [1] * 220000
for i in range(1, 220000):
  if one_pop_count != 0:
    one_pow2[i] = one_pow2[i-1] * 2 % one_pop_count
  zero_pow2[i] = zero_pow2[i-1] * 2 % zero_pop_count

for i in range(n-1, -1, -1):
  if x[n-1-i] == "1":
    if one_pop_count != 0:
      nxt = one_mod
      nxt -= one_pow2[i]
      nxt %= one_pop_count
      print(f[nxt] + 1)
    else:
      print(0)
  if x[n-1-i] == "0":
    nxt = zero_mod
    nxt += zero_pow2[i]
    nxt %= zero_pop_count
    print(f[nxt] + 1)
### BUGGY CODE ###

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353
N, S = lr()
A = lr()
# dp[i][j][k] i番目まで見て和がjとなる総数
# k=0がL,Rが決まっていない、k=1がLだけ決定、k=2がLとRが決定
dp = [[[0] * 3 for _ in range(S+1)] for _ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    a = A[i]
    for j in range(S+1):
        dp[i+1][j][0] += dp[i][j][0]
        dp[i+1][j][1] += dp[i][j][0] + dp[i][j][1]
        dp[i+1][j][2] += dp[i][j][0] + dp[i][j][1] + dp[i][j][2]
        if a + j <= S: # A[i]を加える時
            dp[i+1][j+a][1] = dp[i][j][0] + dp[i][j][1]
            dp[i+1][j+a][2] = dp[i][j][0] + dp[i][j][1]
        dp[i+1][j][1] %= MOD
        dp[i+1][j][2] %= MOD

answer = dp[N][S][2] % MOD
print(answer)


### FIXED CODE ###

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353
N, S = lr()
A = lr()
dp = [0] * (S+1)
answer = 0
for a in A:
    dp[0] += 1 # Lの数は１個ずつ加わる
    prev = dp.copy()
    for i in range(S-a+1):
        dp[i+a] += prev[i]
    answer += dp[-1] # その位置Rとした時

print(answer % MOD)
# 26
### BUGGY CODE ###

row = input().split()
K = int(row[0])
S = int(row[1])
count = 0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if S == x+y+z:
                count += 1

print(count)

### FIXED CODE ###

row = input().split()
K = int(row[0])
S = int(row[1])
count = 0
for x in range(K+1):
    for y in range(K+1):
        if 0 <= S - x - y <= K:
            count += 1

print(count)
### BUGGY CODE ###

import collections

n = int(input())
s = [input() for i in range(n)]

for i in range(n):
    s[i] = [s[i][j] for j in range(10)]
    s[i] = collections.Counter(s[i])

count = 0

for i in range(n):
    for j in range(i+1, n):
        if s[i] == s[j]:
            count += 1

print(count)


### FIXED CODE ###

import collections
n = int(input())

s = ["".join(sorted(input())) for i in range(n)]

a = collections.Counter(s)

ans = 0

for i in a.values():
    ans += i*(i-1)//2

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

def bi(x):
    x = int(x)
    i = 0
    o = [0]*61
    while x > 0:
        o[i] = x % 2
        x //= 2
        i += 1
    return o

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

# print(*A,sep='\n')
a = 0
ruijoo = 1
bbb = 0
for h in range(61):
    B = [A[x][h] for x in range(N)]
    isOne = sum(B)
    isZero = N - isOne
    C = [isOne,isZero]
    bbb += sum([C[B[x]] for x in range(N)])*ruijoo
    ruijoo *= 2
    ruijoo %= 1000000007

bbb *= 500000004
bbb %= 1000000007
print(bbb)

### FIXED CODE ###

def bi(x):
    x = int(x)
    i = 0
    o = [0]*61
    while x > 0:
        o[i] = x % 2
        x //= 2
        i += 1
    return o

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

# print(*A,sep='\n')
a = 0
ruijoo = 1
bbb = 0
B = [0]*N
h = 0
while h < 61:
    i = 0
    isOne = 0
    while i < N:
        aaaa = A[i][h]
        isOne += aaaa
        B[i] = aaaa
        i += 1
    isZero = N - isOne
    C = [isOne,isZero]
    bbbb = 0
    i = 0
    while i < N:
        bbbb += C[B[i]]
        i += 1
    bbbb *= ruijoo
    bbb += bbbb
    bbb %= 1000000007
    ruijoo *= 2
    ruijoo %= 1000000007
    h += 1

bbb *= 500000004
bbb %= 1000000007
print(bbb)
### BUGGY CODE ###

n, m = map(int, input().split())
ans1 = []

for i in range(m):
    a, b = map(int, input().split())
    ans2 = [i for i in range(a, b+1)]
    if ans1 == []:
        ans1 = ans2
    else:
        ans1 = list(set(ans1) & set(ans2))

print(len(ans1))

### FIXED CODE ###

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

maxNum = 0
minNum = 0

for i in range(m):
    a, b = map(int, input().split())
    if maxNum == 0:
        maxNum = b
    else:
        if maxNum > b:
            maxNum = b

    if minNum == 0:
        minNum = a
    else:
        if minNum < a:
            minNum = a

if maxNum - minNum >= 0:
    print(maxNum - minNum + 1)
else:
    print(0)
### BUGGY CODE ###

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
mod = 10**9 + 7

dp = [0]*(n+1)
dp[0] = 1
    
for i in range(1,n+1):
    if i in a:
        continue
    x = dp[i-1] 
    if i > 1:
        x += dp[i-2]
    dp[i] = x
ans = dp[n] % mod
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
a = {int(input()) for _ in range(m)}
mod = 10**9 + 7

dp = [0]*(n+1)
dp[0] = 1
    
for i in range(1,n+1):
    if i in a:
        continue
    x = dp[i-1] 
    if i > 1:
        x += dp[i-2]
    dp[i] = x % mod
ans = dp[n]
print(ans)
### BUGGY CODE ###

#-------------
A,B,C = map(int, input().split())
K = int(input())
#-------------
 
while True :
  if A > B :
    B = B*2
    K -= 1
  if B > C :
    C = C*2
    K -= 1
  if K == 0 :
    break

if A<B<C :
  print("Yes")
else:
  print("No")

### FIXED CODE ###

#-------------
A,B,C = map(int, input().split())
K = int(input())
#-------------
card = []
for i in range(K):
  B_x = B*(2**i)
  C_x = C*(2**(K-i))
  card.append([A,B_x,C_x])

cnt = 0
for i in range(len(card)):
  if card[i][2] > card[i][1] > card[i][0] :
    cnt +=1

if cnt >= 1:
  print("Yes")
else:
  print("No")