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

from collections import defaultdict
import math
N=int(input())

div_dic=defaultdict(int)
def add_fact(x):
  for i in range(1,int(x**0.5)+1):
    if x%i==0:
      div_dic[i]+=1
      if i!=x//i:
        div_dic[x//i]+=1
  return

alist=[]
int_list=[]
for _ in range(N):
  a=input()
  if "." in a:
    seisu,shosu=a.split(".")
    seisu=int(seisu)
    shosu=int(shosu.ljust(9,'0'))
    
    bunshi=10**9*seisu+shosu
    bumbo=10**9
    gcd_bb=math.gcd(bunshi,bumbo)
    bunshi//=gcd_bb
    bumbo//=gcd_bb
    
    if bumbo==1:
      int_list.append(bunshi)
      add_fact(bunshi)
    else:
      alist.append((bunshi,bumbo))
  else:
    seisu=int(a)
    int_list.append(seisu)
    add_fact(seisu)
#print(int_list,alist,div_dic)

num_int=len(int_list)
answer=num_int*(num_int-1)//2
for bunshi,bumbo in alist:
  answer+=div_dic[bumbo]

#shosudoshi
def set_fact(x):
  ret=set()
  for i in range(1,int(x**0.5)+1):
    if x%i==0:
      ret.add(i)
      ret.add(x//i)
  return ret

#print(alist)
div_dic2=defaultdict(int)
for bunshi,bumbo in alist:
  div_set=set_fact(bunshi)  
  for d in div_set:    
    answer+=div_dic2[(bumbo,d)]
    
  for d in div_set:    
    div_dic2[(d,bumbo)]+=1
#print(div_dic2)
  
print(answer)

### FIXED CODE ###

from collections import defaultdict
N=int(input())

def pow25(x):
  f2=f5=0
  while x%2==0:
    x//=2
    f2+=1
  while x%5==0:
    x//=5
    f5+=1
  return f2,f5

pow25_dic=defaultdict(int)
for _ in range(N):
  a=input()
  if "." in a:
    seisu,shosu=a.split(".")
    seisu=int(seisu)
    shosu=int(shosu.ljust(9,'0'))    
    bunshi=10**9*seisu+shosu
  else:
    bunshi=10**9*int(a)
    
  pow25_dic[pow25(bunshi)]+=1
#print(pow25_dic)

pow25_key_list=[]
for key in pow25_dic:
  pow25_key_list.append(key)
#print(pow25_key_list)

answer=0
for i in range(len(pow25_key_list)):
  f2,f5=pow25_key_list[i]
  value=pow25_dic[(f2,f5)]
  if f2>=9 and f5>=9:    
    answer+=value*(value-1)//2
    
  for j in range(i+1,len(pow25_key_list)):
    f2_2,f5_2=pow25_key_list[j]
    if f2+f2_2>=18 and f5+f5_2>=18:
      value2=pow25_dic[(f2_2,f5_2)]
      answer+=value*value2
      
print(answer)
### BUGGY CODE ###

from fractions import gcd

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

ans = 0
i = 2
check = False
while c != 1:
    #print(c,i)
    while c % i == 0:
        #print('a')
        c = c // i
        check = True
    i = i + 1
    if check:
        ans += 1
    check = False
    if i > 10000000:
        print(ans+2)
        exit()
print(ans + 1)

### FIXED CODE ###

from fractions import gcd

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

ans = 0
i = 2
check = False
while c != 1:
    #print(c,i)
    while c % i == 0:
        #print('a')
        c = c // i
        check = True
    i = i + 1
    if check:
        ans += 1
    check = False
    if i > 1000000:
        print(ans+2)
        exit()
print(ans + 1)
### BUGGY CODE ###

k,s=map(int, input().split())
ans=0
for x in range(s+1):
    for y in range(s+1-x):
        z=s-x-y
        if x+y<=s and x<=k and y<=k and z<=k:
            ans+=1
print(ans)

### FIXED CODE ###

k,s=map(int, input().split())
ans=0
for x in range(k+1):
    for y in range(min(k+1,s+1-x)):
        z=s-x-y
        if 0<=z<=k:
            ans+=1
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
s = input()

first = s[0]
end = s[-1]
len_list = []

count = 0
pre = first
for i in range(n):
    if s[i] == pre:
        count += 1
    else:
        len_list.append(count)
        pre = s[i]
        count = 1
len_list.append(count)

size = len(len_list)

if size < 2*k + 1:
    print(n)
else:
    ans = 0
    index = 0
    if first == '0':
        index = 1
        ans = sum(len_list[:2*k])
    if end == '0':
        ans = max(sum(len_list[size-2*k:]), ans)

    while index + 2 * k < size:
        ans = max(ans, sum(len_list[index: index+2*k+1]))
        index += 2

    print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
s = input()

first = s[0]
end = s[-1]
len_list = []

count = 0
pre = first
for i in range(n):
    if s[i] == pre:
        count += 1
    else:
        len_list.append(count)
        pre = s[i]
        count = 1
len_list.append(count)
sum_list = [0]
sum_tmp = 0
for i in len_list:
    sum_tmp += i
    sum_list.append(sum_tmp)

size = len(len_list)

if size < 2*k + 1:
    print(n)
else:
    ans = 0
    index = 0
    if first == '0':
        index = 1
        ans = sum_list[2*k] - sum_list[0]
    if end == '0':
        ans = max((sum_list[size] - sum_list[size-2*k]), ans)

    while index + 2 * k < size:
        ans = max(ans, (sum_list[index+2*k+1] - sum_list[index]))
        index += 2

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

#!/usr/bin/env python
# -*- coding:utf-8 -*-
#from __future__ import print_function
import time
import sys
import io
import re
import math
start = time.clock()
i = 0
ans=[]
#n=int(raw_input())
#for _ in range(n):
for _ in range(int(raw_input())):
#    a=sys.stdin.readline().split()
    a=sys.stdin.readline().strip()
#    chk=a[0]
    chk=a[6]
    if a[0]=='i': ans.insert(0,a[7:])
#    elif chk=='deleteFirst': ans.pop(0)
    elif chk=='F': del ans[0]
#    elif chk=='deleteLast': ans.pop()
    elif chk=='L': del ans[-1]
#    else: ans.remove(str(a[1]))
    else:
#        if a[1] in ans:
        if ans.count(a[7:])>0:
            ans.remove(a[7:])
for j in ans:
    print int(j),

### FIXED CODE ###

import sys
import collections
n=int(raw_input())
ans=collections.deque()
while n:
    n-=1
    s=sys.stdin.readline().rstrip().split(' ')
    if s[0][0]=='i':
        ans.appendleft(s[1])
    elif s[0][-3]=='r':
        ans.popleft()
    elif s[0][-3]=='a':
        ans.pop()
    else:
        try:
            ans.remove(s[1])
        except:
            pass
sys.stdout.write(' '.join(ans))
print
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[]
max1=0;max2=0
for i in range(n-1):
  for j in range(i+1,n):
    if a[i]==a[j]:
      if a[i]>max1:
        max2=max1
        max1=a[i]
      elif a[i]>max2:
        max2=a[i]
      a[j]=0
      break
print(max1*max2)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
a.reverse()
max1=0;max2=0
count=0
for i in range(n-3):
  if a[i]==a[i+1]:
    max1=a[i]
    a[i+1]=0
    count=i+1
    break
if count==0:
  print(0)
  exit()
for j in range(count,n-1):
  if a[j]==a[j+1]:
    max2=a[j]
    break
print(max1*max2)
### BUGGY CODE ###

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

maze = [[9]*(w+2)]
for i in range(h):
  s = input()
  tmp = [9]
  for j in s:
    if j == "#":
      tmp.append(9)
    else:
      tmp.append(0)
  tmp.append(9)
  maze.append(tmp)
maze.append([9]*(w+2))
#print(maze)

def bfs(start):
  maze2 = copy.deepcopy(maze)
  #print(maze2)
  pos = [start]
  max_depth = 0
  while len(pos):
    x, y, depth = pos.pop(0)
    max_depth = max(depth, max_depth)
    
    maze2[x][y] = 2
    if maze2[x-1][y] < 2:
      pos.append([x-1,y,depth + 1])
    if maze2[x+1][y] < 2:
      pos.append([x+1,y,depth + 1])
    if maze2[x][y-1] < 2:
      pos.append([x,y-1,depth +1])
    if maze2[x][y+1] < 2:
      pos.append([x,y+1,depth +1])
  return max_depth

ans = 0
for i in range(h):
  for j in range(w):
      start = [i+1,j+1,0]
      if maze[i+1][j+1] != 9:
        #print(bfs(start))
      	ans =max(ans,bfs(start))
print(ans)

    
  


### FIXED CODE ###

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

maze = [[9]*(w+2)]
for i in range(h):
  s = input()
  tmp = [9]
  for j in s:
    if j == "#":
      tmp.append(9)
    else:
      tmp.append(0)
  tmp.append(9)
  maze.append(tmp)
maze.append([9]*(w+2))
#print(maze)

def bfs(start):
  maze2 = copy.deepcopy(maze)
  #print(maze2)
  pos = [start]
  max_depth = 0
  maze2[start[0]][start[1]] = 2
  while len(pos):
    x, y, depth = pos.pop(0)
    max_depth = max(depth, max_depth)
    
    if maze2[x-1][y] < 2:
      pos.append([x-1,y,depth + 1])
      maze2[x-1][y] = 2
    if maze2[x+1][y] < 2:
      pos.append([x+1,y,depth + 1])
      maze2[x+1][y] = 2
    if maze2[x][y-1] < 2:
      pos.append([x,y-1,depth +1])
      maze2[x][y-1] = 2
    if maze2[x][y+1] < 2:
      pos.append([x,y+1,depth +1])
      maze2[x][y+1] = 2
  return max_depth

ans = 0
for i in range(h):
  for j in range(w):
      start = [i+1,j+1,0]
      maze2 = maze
      if maze[i+1][j+1] != 9:
        #print(bfs(start))
        ans = max(ans,bfs(start))
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

from scipy.special import comb

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

a.sort()

value = comb(a[1], a[0], exact=True)
ans = [a[1], a[0]]
index = 0
for i in range(2, n):
    value_tmp = comb(a[i], a[index], exact=True)
    x = a[i]
    y = a[index]
    diff = abs((x-2*y)//2)
    while 1:
        y_new = a[index+1]
        diff_new = abs((x-2*y_new)//2)
        if diff_new > diff:
            break
        else:
            index += 1
    if value_tmp > value:
        ans = [a[i], a[index]]
        # value = value_tmp
print(*ans)


### FIXED CODE ###

#!/usr/bin/env python3

import bisect

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

a.sort()

if n == 2:
    print(a[1], a[0])
    exit()
# value = comb(a[1], a[0], exact=True)
# ans = [a[1], a[0]]
# index = 0
# for i in range(2, n):
#     value_tmp = comb(a[i], a[index], exact=True)
#     x = a[i]
#     y = a[index]
#     diff = abs((x-2*y)//2)
#     while 1:
#         y_new = a[index+1]
#         diff_new = abs((x-2*y_new)//2)
#         if diff_new > diff:
#             break
#         else:
#             index += 1
#     if value_tmp > value:
#         ans = [a[i], a[index]]
#         # value = value_tmp
# print(*ans)

x = a[-1]
index = bisect.bisect_left(a[:n-1], x/2)

ans = []
ans.append([abs(x/2-a[index-1]), a[index-1]])
ans.append([abs(x/2-a[index]), a[index]])
ans.append([abs(x/2-a[index+1]), a[index+1]])

ans.sort()

print(x, ans[0][1])
### BUGGY CODE ###

S = input()
Q = int(input())
QUERY = [input().split(" ") for i in range(Q)]

for query in QUERY:
    #print(query)
    if query[0] == "1":#反転
        S = S[::-1]
    else:#=="2"
        if query[1] == "1":
            S = query[2] + S
        else:#=="2"
            S += query[2]
print(S)

### FIXED CODE ###

from collections import deque


S = deque(input())
Q = int(input())
QUERY = [input().split(" ") for i in range(Q)]
reverse_f = 0

for query in QUERY:
    if query[0] == "1":#反転
        reverse_f = (reverse_f+1)%2
    else:#=="2"
        if query[1] == "1":
            if reverse_f:
                S.append(query[2])
            else:
                S.appendleft(query[2])

        else:#=="2"
            if reverse_f:
                S.appendleft(query[2])
            else:
                S.append(query[2])

if reverse_f:
    S.reverse()
print("".join(list(S)))
### BUGGY CODE ###

from fractions import gcd
N = int(input())
As = list(map(int, input().split()))

lcm = 1
mod = 10**9+7

def getprime(n):
    if not isinstance(n, int):
        raise TypeError("Input int")
    if n < 2:
        raise ValueError("N >= 2")
    prime = []
    # 約数はsqrt(N)まで調べればOK
    data = [i+1 for i in range(1,n)]
    while True:
        p = data[0]
        if p >= int(n**0.5):
            return prime+data
        prime.append(p)
        # pで割り切れないものだけを残す
        data = [d for d in data if d%p != 0]

from collections import defaultdict
def factorization(n):
    factors = defaultdict(int)
    if n == 2 or n == 3:
        factors[n] = 1
        return factors
    primes = getprime(int(n**0.5))
    for prime in primes:
        while n % prime == 0:
            factors[prime] += 1
            n //= prime
            # print(factors,n)
    if n != 1:
        factors[n] += 1
    return factors

d = defaultdict(int)
for a in As:
    if a == 1:
        continue
    factors = factorization(a)
    for f in factors.keys():
        d[f] = max(d[f],factors[f])

for f in d.keys():
    lcm *= f ** d[f]
    # lcm %= mod

As_inv = [pow(a,mod-2,mod) for a in As]
a = sum(As_inv)%mod
print((lcm*a)%mod)


### FIXED CODE ###

from fractions import gcd
N = int(input())
As = list(map(int, input().split()))

lcm = 1
mod = 10**9+7

def getprime(n):
    if not isinstance(n, int):
        raise TypeError("Input int")
    if n < 2:
        raise ValueError("N >= 2")
    prime = []
    # 約数はsqrt(N)まで調べればOK
    data = [i+1 for i in range(1,n)]
    while True:
        p = data[0]
        if p >= int(n**0.5):
            return prime+data
        prime.append(p)
        # pで割り切れないものだけを残す
        data = [d for d in data if d%p != 0]

from collections import defaultdict
def factorization(n):
    factors = defaultdict(int)
    if n == 2 or n == 3:
        factors[n] = 1
        return factors
    primes = getprime(int(n**0.5))
    for prime in primes:
        while n % prime == 0:
            factors[prime] += 1
            n //= prime
            # print(factors,n)
    if n != 1:
        factors[n] += 1
    return factors

d = defaultdict(int)
factors_list = []
cnt_1 = 0
for a in As:
    if a == 1:
        cnt_1 += 1
        continue
    factors = factorization(a)
    factors_list.append(factors)
    for f in factors.keys():
        d[f] = max(d[f],factors[f])

for f in d.keys():
    lcm *= f ** d[f]
    lcm %= mod

As_inv = [pow(a,mod-2,mod) for a in As]
a = sum(As_inv)%mod



print((lcm*a)%mod)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def f(ab: list, parent: list, i: int = 0):
    if len(ab[i]) == 1 and i != 0:
        return
    for j in ab[i]:
        if j != parent[i]:
            parent[j] = i
            f(ab, parent, j)

def g(ab: list, parent: list, ans: list, i: int = 0):
    if len(ab[i]) == 1 and i != 0:
        return
    for j in ab[i]:
        if j != parent[i]:
            ans[j] += ans[i]
            g(ab, parent, ans, j)

def main():
    N, Q = map(int, input().split())
    ab = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        ab[a-1].append(b-1)
        ab[b-1].append(a-1)
    parent = [-1] * N
    f(ab, parent)
    ans = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        ans[p-1] += x
    g(ab, parent, ans)
    print(' '.join(list(map(str, ans))))
    

if __name__ == '__main__': main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def g(ab: list, ans: list, check: list, i: int = 0):
    if len(ab[i]) == 1 and i != 0:
        return
    check[i] = False
    for j in ab[i]:
        if check[j]:
            ans[j] += ans[i]
            g(ab, ans, check, j)

def main():
    N, Q = map(int, input().split())
    ab = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        ab[a-1].append(b-1)
        ab[b-1].append(a-1)
    ans = [0] * N
    check = [True] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        ans[p-1] += x
    g(ab, ans, check)
    print(' '.join(list(map(str, ans))))
    

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

from collections import deque
H, W= map(int, input().split())
CH, CW= map(int, input().split())
DH, DW= map(int, input().split())
S = [list(map(str, input())) for _ in range(H)]
q = deque([(CH-1, CW-1, 0)])
while q:
    h, w, c = q.popleft()
    if S[h][w] == '.':
        S[h][w] = c
        for i in range(-2, 3):
            for j in range(-2, 3):
                if 0<=h+i and h+i<H and 0<=w+j and w+j<W:
                    if abs(i)+abs(j) == 1:
                        q.appendleft((h+i, w+j, c))
                    elif abs(i)+abs(j) >= 2:
                        q.append((h+i, w+j, c+1))
if S[DH-1][DW-1] == '#' or S[DH-1][DW-1] == '.':
    print(-1)
else:
    print(S[DH-1][DW-1])


### FIXED CODE ###

from collections import deque
H, W= map(int, input().split())
CH, CW= map(int, input().split())
DH, DW= map(int, input().split())
S = [list(map(str, input())) for _ in range(H)]
q = deque([(CH-1, CW-1, 0)])
while q:
    h, w, c = q.popleft()
    if S[h][w] == '.':
        S[h][w] = c
        for i in range(-2, 3):
            for j in range(-2, 3):
                if 0<=h+i<H and 0<=w+j<W and S[h+i][w+j] == '.':
                    if abs(i)+abs(j) == 1:
                        q.appendleft((h+i, w+j, c))
                    elif abs(i)+abs(j) >= 2:
                        q.append((h+i, w+j, c+1))
if S[DH-1][DW-1] == '.':
    print(-1)
else:
    print(S[DH-1][DW-1])
### BUGGY CODE ###

import numpy as np
k=int(input())

sum_num=0
for i in range(1,k+1):
  for j in range(1,k+1):
    for l in range(1,k+1):
      s=np.gcd.reduce([i,j,l])
      sum_num+=s
      
print(sum_num)

### FIXED CODE ###

import math
k=int(input())

sum_num=0
for i in range(1,k+1):
  for j in range(1,k+1):
    tmp=math.gcd(j,i)
    for l in range(1,k+1):
      s=math.gcd(l,tmp)
      sum_num+=s
      
print(sum_num)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
F = [int()] * n
F[0] = A[0]
for b in range(1, n):
    F[b] = F[b - 1] + A[b]
res = [0]*4
ans = 10**18
for i in range(1, n - 1):
    for j in range(0, i):
        res[0] = F[j]
        res[1] = F[i] - F[j]
        for k in range(i + 1, n):
            res[2] = F[k] - F[i]
            res[3] = F[n - 1] - F[k]
            ans = min(ans, max(res) - min(res))
            if res[2] > res[3]:
                break
        if res[0] > res[1]:
            break
print(ans)


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
F = [int()] * n
F[0] = A[0]
for b in range(1, n):
    F[b] = F[b - 1] + A[b]


res = [0]*4
data = [10 ** 18] * 2
ex = [0]*4
ans = 10 ** 18
s = 0
t = 2
for i in range(1, n - 2):
    bl = [True, True]
    for j in range(s, i):
        res[0] = F[j]
        res[1] = F[i] - F[j]
        if not bl[0]:
            break
        if data[0] > abs(res[1] - res[0]) or j == s:
            s = j
            ex[0] = res[0]
            ex[1] = res[1]
            data[0] = abs(res[1] - res[0])
        else:
            bl[0] = False
    for k in range(t, n):
        res[2] = F[k] - F[i]
        res[3] = F[n - 1] - F[k]
        if not bl[1]:
            break
        if data[1] > abs(res[3] - res[2]) or k == t:
            t = k
            ex[2] = res[2]
            ex[3] = res[3]
            data[1] = abs(res[3] - res[2])
        else:
            bl[1] = False
    ans = min(ans, max(ex) - min(ex))

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

N=int(input())
ans=1
L=[1 for i in range(N+1)]
for i in range(2,N+1):
    ans+=i*(L[i]+1)
    for j in range(2,N+1):
        if j*i<=N:
            L[i*j]+=1
print(ans)
#print(L)

### FIXED CODE ###

N=int(input())
ans=0
for i in range(1,N+1):
    c=N//i
    ans+=((i+i*c)*c)//2
print(ans)
### BUGGY CODE ###

# -*- 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 = 998244353
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 #
#############

N,S = inputIL()
A = inputIL()

dp = [0] * (S+1)
ans = 0
mod = 998244353


for i in range(N):
 
    ndp = []
    for ll in dp:
        ndp.append(ll)
 
    if A[i] <= S:
        ndp[A[i]] += i+1
        ndp[A[i]] %= mod
 
    for j in range(S):
        if j+A[i] <= S:
            ndp[j+A[i]] += dp[j]
            ndp[j+A[i]] %= mod
 
    ans += ndp[S]
    ans %= mod
 
    dp = ndp

print(ans)

### FIXED CODE ###

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

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

"""
dpなのはそうだろう
普通に行けば、ナップサックdpでいける
S以下のみしか保持しなくていい

始点を保持してしまうと、Sになった時に…？
始点より左にあるやつの個数の和を記録しておけばいい！

連続してなくていいから
"""

dp = [0] * (S+1)
ans = 0
mod = 998244353

for i in range(N):

    ndp = []
    for ll in dp:
        ndp.append(ll)

    if A[i] <= S:
        ndp[A[i]] += i+1
        ndp[A[i]] %= mod

    for j in range(S):

        if j+A[i] <= S:
            ndp[j+A[i]] += dp[j]
            ndp[j+A[i]] %= mod

    ans += ndp[S]
    ans %= mod

    dp = ndp

    #print (dp)

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

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

def segfunc(x, y):
    return min(x, y)

def init(init_val):
    # set_val
    for i in range(n):
        seg[i+num-1] = init_val[i]
    # built
    for i in range(num-2, -1, -1):
        seg[i] = segfunc(seg[2*i+1], seg[2*i+2])

def update(k, x):
    k += num - 1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[2*k+1], seg[2*k+2])

def query(p, q):
    if q <= p:
        return ide_ele
    p += num - 1
    q += num - 2
    res = ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res, seg[p])
        if q&1 == 1:
            res = segfunc(res, seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res, seg[p])
    else:
        res = segfunc(segfunc(res, seg[p]), seg[q])
    return res

# identity element
ide_ele = 10**9+1

# num: n以上の最小の2のべき乗
num = 2**(n-1).bit_length()
seg = [ide_ele]*2*num

init(A)

ans = float('inf')
for k in range(n):
    t = k*x
    for i in range(n):
        if k <= i:
            t += query(i-k, i+1)
        else:
            t += min(query(0, i+1), query(n-(k-i), n))
    ans = min(t, ans)
print(ans)


### FIXED CODE ###

import sys

n, x = map(int,sys.stdin.readline().split())
A = list(map(int,sys.stdin.readline().split()))

ans = 10**18
mins = [a for a in A]
for k in range(n):
    for i in range(n):
        if k <= i:
            mins[i] = min(A[i-k], mins[i])
        else:
            mins[i] = min(A[n-(k-i)], mins[i])
    ans = min(sum(mins)+k*x, ans)
print(ans)
### BUGGY CODE ###

N,K= map(int,input().split())
h = list(map(int,input().split()))
dp =[0]*N
dp[0] = 0
dp[1] = h[0]
for j in range(1,N):
  dp[j] = dp[j-1] + abs(h[j] - h[j-1])
  for i in range(max(j-K,0),j):
    dp[j]=min(dp[i]+ abs(h[j]-h[i]),dp[j]) 
print(dp[-1])

### FIXED CODE ###

N,K= map(int,input().split())
h = list(map(int,input().split()))
dp =[0]*N
dp[0] = 0
dp[1] = h[0]
for j in range(1,N):
  dp[j] = dp[j-1] + abs(h[j] - h[j-1])
  for i in range(max(j-K,0),j):
    dp[j]=min(dp[i]+ abs(h[j]-h[i]),dp[j]) 
print(dp[-1])