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

# ライブラリのインポート
import numpy as np


# メイン関数
def main():
    # 入力データ
    s = np.array(list(input()))
    t = np.array(list(input()))

    # dpテーブルの作成
    dp = np.zeros((len(s) + 1, len(t) + 1), dtype='int')
    for i in range(1, len(s) + 1):
        for j in range(1, len(t) + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # 部分列の復元
    length = dp[len(s)][len(t)]
    ans = ''
    i = len(s)
    j = len(t)
    while length > 0:
        if s[i - 1] == t[j - 1]:
            ans = s[i - 1] + ans
            i -= 1
            j -= 1
            length -= 1
        elif dp[i][j] == dp[i - 1][j]:
            i -= 1
        else:
            j -= 1

    # 解答の出力
    print(ans)
    return


# 実行
if __name__ == '__main__':
    main()


### FIXED CODE ###

# メイン関数
def main():
    # 入力データ
    s = input()
    t = input()

    # dpテーブルの作成
    dp = [[0] * (len(t)+1) for i in range(len(s)+1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

    # 部分列の復元
    ans = ''
    i = len(s)
    j = len(t)
    while i != 0 and j != 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            i -= 1
            j -= 1
            ans = s[i] + ans

    # 解答の出力
    print(ans)
    return


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

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

inf = 10 ** 10
dp = [inf] * n
dp[0] = 0

for i in range(n):
    for j in range(1, k+1):
        if i+j >= n:
            break
        dp[i+j] = min(dp[i+j], dp[i] + abs(h[i] - h[i+j]))
        
print(dp[n-1])

### FIXED CODE ###

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

inf = 10 ** 10
dp = [inf] * n
dp[0] = 0

for i in range(n):
    for j in range(1, k+1):
        if i+j >= n:
            break
        dp[i+j] = min(dp[i+j], dp[i] + abs(h[i] - h[i+j]))
        
print(dp[n-1])
### BUGGY CODE ###

S = input()
Q = int(input())

direction = 1
for i in range(Q):
    T = input()
    if T == '1':
        direction = direction * -1
    else:
        T = T.split()
        if T[1] == '1':
            if direction == 1:
                S = T[2] + S
            else:
                S = S + T[2]
        else:
            if direction == 1:
                S = S + T[2]
            else:
                S = T[2] + S

S = S[::direction]

print(S)

### FIXED CODE ###

S = input()
Q = int(input())

direction = 1
head = []
tail = []
for i in range(Q):
    T = input()
    if T == '1':
        direction = direction * -1
    else:
        T = T.split()
        if T[1] == '1':
            if direction == 1:
                head.append(T[2])
            else:
                tail.append(T[2])
        else:
            if direction == 1:
                tail.append(T[2])
            else:
                head.append(T[2])

head = head[::(-1)]
head.append(S)
head.extend(tail)
S = "".join(head)[::direction]

print(S)
### BUGGY CODE ###

from collections import Counter
li = []
ans = 0
N = int(input())
for i in range(N):
    x = Counter(input())
    for j in li:
        if x == j:
            ans += 1
    li.append(x)

print(ans)


### FIXED CODE ###

dic = {}
ans = 0
N = int(input())
for i in range(N):
    x = sorted(input())
    x = "".join(x)
    if x in dic:
        dic[x] += 1
    else:
        dic[x] = 1

for i in dic:
    x = dic[i]
    if x > 1:
        ans += x*(x-1) // 2
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
d={}
l=[]
for i in range(n):
    if l.count(a[i])==0:
        d[a[i]]=1
        l.append(a[i])
    else:
        d[a[i]]+=1

ans=0
for i in range(len(l)):
    if d[l[i]]>l[i]:
        ans+=d[l[i]]-l[i]
    elif d[l[i]]<l[i]:
        ans+=d[l[i]]
print(ans)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
d={}
l=[]
for i in range(n):
    try:
        d[a[i]]+=1
    except:
        d[a[i]]=1
        l.append(a[i])

ans=0
for i in range(len(l)):
    if d[l[i]]>l[i]:
        ans+=d[l[i]]-l[i]
    elif d[l[i]]<l[i]:
        ans+=d[l[i]]
print(ans)
### BUGGY CODE ###

n=int(input())
al=list(map(int,input().split()))
ans=[]
tl=[0]*n
for i in range(n,0,-1):
    if tl[i-1]%2^al[i-1]:
        ans.append(i)
        for j in range(1,int(i**0.5)+1):
            if i%j==0:
                tl[j-1]^=1
                if j**2==i:
                    continue
                tl[i//j-1]^=1
print(len(ans))
print(*ans)

### FIXED CODE ###

n=int(input())
al=list(map(int,input().split()))
ac=0
ans=set()
tl=[0]*n
for i in range(n,0,-1):
    if tl[i-1]%2!=al[i-1]:
        ac+=1
        ans.add(i)
        for j in range(1,int(i**0.5)+1):
            if i%j==0:
                tl[j-1]+=1
                if j**2==i:
                    continue
                tl[i//j-1]+=1
print(ac)
if ac>0:
    print(' '.join(map(str,ans)))
### BUGGY CODE ###

n, m, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
pa, pb = [0] * (n+1), [0] * (m+1)
for i in range(n):
    pa[i+1] = pa[i] + a[i]
for i in range(m):
    pb[i+1] = pb[i] + b[i]
mx = 0
for i in range(len(pa)):
    j = m
    if pa[i] > k:
        break
    v = k - pa[i]
    while pb[j] > v:
        j -= 1
    mx = max(mx, i+j)
print(mx)


### FIXED CODE ###

n, m, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
pa, pb = [0] * (n+1), [0] * (m+1)
for i in range(n):
    pa[i+1] = pa[i] + a[i]
for i in range(m):
    pb[i+1] = pb[i] + b[i]
mx = 0
j = m
for i in range(n+1):
    if pa[i] > k:
        break
    v = k - pa[i]
    while pb[j] > v:
        j -= 1
    mx = max(mx, i+j)
print(mx)
### BUGGY CODE ###

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


ans_list = []
ans_list.append(0)
sum_a = 0
for i in range(len(a)):
  sum_a += a[i]
  sum_b = 0
  if sum_a > k:
    break
  if sum_a == k:
    temp = i+1
    ans_list.append(temp)
    break
  for j in range(len(b)):
    sum_b += b[j]
    if (sum_a + sum_b) > k:
      temp = i+1+j
      ans_list.append(temp)
      break
    if (sum_a + sum_b) == k:
      temp = i+1+j+1
      ans_list.append(temp)
      break
      
sum_b = 0
for i in range(len(b)):
  sum_b += b[i]
  sum_a = 0
  if sum_b > k:
    break
  if sum_b == k:
    temp = i+1
    ans_list.append(temp)
    break
  for j in range(len(a)):
    sum_a += a[j]
    if (sum_b + sum_a) > k:
      temp = i+1+j
      ans_list.append(temp)
      break
    if (sum_b + sum_a) == k:
      temp = i+1+j+1
      ans_list.append(temp)
      break
      
print(max(ans_list))

### FIXED CODE ###

N, M, K = map(int, input().split())
A = list(map(int,input().split()))
B = list(map(int, input().split()))
a = [0]
b = [0]

ans = 0
j = M

for i in range(N):
  a.append(a[i] + A[i])

for i in range(M):
  b.append(b[i] + B[i])

for i in range(N+1):
  if a[i] > K:
    break
  while a[i] + b[j] > K:
    j -= 1
  ans = max(ans, i+j)

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

s = input()
t = input()
dp = [[0] * (len(t)+1) for _ in range(len(s)+1)]

for i in range(1, len(s)+1):
    for j in range(1, len(t)+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1)
        dp[i][j] = max(dp[i][j], dp[i][j-1])
        dp[i][j] = max(dp[i][j], dp[i-1][j])

ans = ''
i = len(s)
j = len(t)
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans += t[j-1]
        i -= 1
        j -= 1
   
print(ans[::-1])

### FIXED CODE ###

s = input()
t = input()
dp = [[0] * (len(t)+1) for _ in range(len(s)+1)]

for i in range(1, len(s)+1):
    for j in range(1, len(t)+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1)
        dp[i][j] = max(dp[i][j], dp[i][j-1])
        dp[i][j] = max(dp[i][j], dp[i-1][j])

ans = ''
i = len(s)
j = len(t)
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans += t[j-1]
        i -= 1
        j -= 1
   
print(ans[::-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
import math


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


N = z()
ans = 0
for i in range(1, N+1):
    for j in range(1, N+1):
        if (i % j == 0):
            ans += i
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
import math


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


N = z()
yakusu_nums = [0]*(N+1)
for i in range(1, N+1):
    for j in range(i, N+1, i):
        yakusu_nums[j] += 1
ans = 0
for i, yakusu_num in enumerate(yakusu_nums):
    # print(i, yakusu_num)
    ans += i*yakusu_num
print(ans)
### BUGGY CODE ###

from collections import defaultdict
N=input()
L=defaultdict(lambda: 1)
L[1]=1
for skip in range(2,N+1):
    for i in range(skip,N+1,skip):
        L[i]+=1
ans=0
for k in range(1,N+1):
    ans+=k*L[k]

print ans


### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
N=input()
A=[ 2 for _ in range(N+1)]
A[0]=0
A[1]=1

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

ans=0
for i in range(1,N+1):
    ans+=i*A[i]
print ans
### BUGGY CODE ###

from collections import deque
h,w=map(int,input().split())
a=[input() for _ in range(h)]
dxy=[(0,1),(1,0),(-1,0),(0,-1)]
inf=float("inf")

dp=[[inf]*w for _ in range(h)]
q=deque()

for y,l in enumerate(a):
    for x,c in enumerate(l):
        if c=="#":
            dp[y][x]=0
            q.append((x,y))
ans=0
while q:
    x,y=q.popleft()
    d=dp[y][x]
    for dx,dy in dxy:
        nx,ny=x+dx,y+dy
        if not 0<=nx<w: continue
        if not 0<=ny<h: continue
        if dp[ny][nx]<=d+1: continue
        dp[ny][nx]=d+1
        q.append((nx,ny))
        ans=max(ans,d+1)
print(ans)


### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
a=[input() for _ in range(h)]
dxy=[(0,1),(1,0),(-1,0),(0,-1)]
inf=float("inf")

dp=[[inf]*w for _ in range(h)]
q=deque()

for y,l in enumerate(a):
    for x,c in enumerate(l):
        if c=="#":
            dp[y][x]=0
            q.append((x,y))
ans=0
while q:
    x,y=q.popleft()
    d=dp[y][x]
    for dx,dy in dxy:
        nx,ny=x+dx,y+dy
        if not 0<=nx<w: continue
        if not 0<=ny<h: continue
        if dp[ny][nx]<=d+1: continue
        dp[ny][nx]=d+1
        q.append((nx,ny))
        ans=max(ans,d+1)
print(ans)
### BUGGY CODE ###

def parent(n):
    return (n+1)/2-1

def left(n):
    return (n+1)*2-1

def right(n):
    return (n+1)*2

def max_heapify(A, i):
    l = left(i)
    r = right(i)
    largest = i
    if l < len(A) and A[largest] < A[l]:
        largest = l
    if r < len(A) and A[largest] < A[r]:
        largest = r

    if largest != i:
        A[largest],A[i] = A[i],A[largest]
        max_heapify(A,largest)

def build_max_heap(A):
    for i in reversed(xrange((len(A)-1)/2+1)):
        max_heapify(A,i)

def up_heap(A,i):
    p = parent(i)
    if p >= 0 and A[p] < A[i]:
        A[p],A[i] = A[i],A[p]
        up_heap(A,p)

def extract_max(A):
    ret = A[0]
    A[0] = A[len(A)-1]
    del A[len(A)-1]
    max_heapify(A,0)
    return ret


heap = []
while True:
    c = raw_input()
    if c[0] == 'i':
        n = int(c[7:])
        heap.append(n)
        up_heap(heap,len(heap)-1)
    elif c[:2] == 'ex':
        print extract_max(heap)
    else:
        break

### FIXED CODE ###

from sys import stdin

def max_heapify(A, i):
    l = i*2
    r = i*2+1
    largest = i
    if l <= A[0] and A[i] < A[l]:
        largest = l
    else:
        largest = i
    if r <= A[0] and A[largest] < A[r]:
        largest = r

    if largest != i:
        A[largest],A[i] = A[i],A[largest]
        max_heapify(A,largest)

heap = [0]*2000000
for c in stdin:
    if c[0] == 'i':
        heap[0] += 1
        heap[heap[0]] = int(c[7:])
        i = heap[0]
        p = i/2
        while p > 0 and heap[p] < heap[i]:
            heap[p],heap[i] = heap[i],heap[p]
            i = p
            p = i/2
    elif c[1] == 'x':
        print heap[1]
        heap[1] = heap[heap[0]]
        heap[0] -= 1
        max_heapify(heap,1)
    else:
        break
### BUGGY CODE ###

res=0
h,w=map(int,input().split())
m=[[None for j in range(w)] for i in range(h)]
c=[[-1 for j in range(w)] for i in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        if s[j]==".":
            m[i][j]=0
        else:
            m[i][j]=1

for i in range(h):
    j=0
    start=-1
    while(j<w):
        if start==-1:
            if m[i][j]==0:
                start=j
                count=1
        else:
            if m[i][j]==1:
                for k in range(start,j):
                    c[i][k]+=count
                    res=max(res,c[i][k])
                start=-1
            else:
                count+=1
        j+=1
    if start!=-1:
        for k in range(start,w):
            c[i][k]+=count
            res=max(res,c[i][k])
for j in range(w):
    i=0
    start=-1
    while(i<h):
        if start==-1:
            if m[i][j]==0:
                start=i
                count=1
        else:
            if m[i][j]==1:
                for k in range(start,i):
                    c[k][j]+=count
                    res=max(res,c[k][j])
                start=-1
            else:
                count+=1
        i+=1
    if start!=-1:
        for k in range(start,h):
            c[k][j]+=count
            res=max(res,c[k][j])
print(res)

### FIXED CODE ###

h,w=map(int,input().split())
m=[[None for j in range(w)] for i in range(h)]
c=[[-1 for j in range(w)] for i in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        if s[j]==".":
            m[i][j]=0
        else:
            m[i][j]=1

for i in range(h):
    j=0
    start=-1
    while(j<w):
        if start==-1:
            if m[i][j]==0:
                start=j
                count=1
        else:
            if m[i][j]==1:
                for k in range(start,j):
                    c[i][k]+=count
                start=-1
            else:
                count+=1
        j+=1
    if start!=-1:
        for k in range(start,w):
            c[i][k]+=count
for j in range(w):
    i=0
    start=-1
    while(i<h):
        if start==-1:
            if m[i][j]==0:
                start=i
                count=1
        else:
            if m[i][j]==1:
                for k in range(start,i):
                    c[k][j]+=count
                start=-1
            else:
                count+=1
        i+=1
    if start!=-1:
        for k in range(start,h):
            c[k][j]+=count
result=0
for i in range(h):
    for j in range(w):
        result=max(result,c[i][j])
print(result)
### BUGGY CODE ###



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

es = [[] for _ in range(N+1)]

for i in range(M):
    a,b = map(int, input().split())
    es[a].append(b)


for i in range(2,N):
    if i in es[1] and N in es[i]:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

### FIXED CODE ###

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

ship = {}

for i in range(m):
  a,b = (map(int, input().split()))
  if a == 1 or b == n:
    if a in ship: #keyにaがあるばあい
      ship[a].append(b)
    else:
      ship[a] = [b]

if 1 in ship:
  for i in ship[1]:
    if i in ship and n in ship[i]:
      print("POSSIBLE")
      exit()
      


  
  
print("IMPOSSIBLE")
### BUGGY CODE ###

h,w = map(int,input().split())
l=['#'*(w+2)]+['#'+input()+'#' for i in range(h)]+['#'*(w+2)]
dp = [[[0]*4 for i in range(w+2)] for i in range(h+2)]
ans = 0

for i in range(h+2):
  for j in range(w+2):
     if l[i][j] == '#':
      dp[i][j][0] = 0
     else:
      dp[i][j][0] = dp[i][j-1][0] + 1
for i in range(h+2):
  for j in range(w+1,0,-1):
     if l[i][j] == '#':
      dp[i][j][1] = 0
     else:
      dp[i][j][1] = dp[i][j+1][1] + 1
for i in range(h+2):
  for j in range(w+2):
     if l[i][j] == '#':
      dp[i][j][2] = 0
     else:
      dp[i][j][2] = dp[i-1][j][2] + 1
for i in range(h+1,0,-1):
  for j in range(w+2):
     if l[i][j] == '#':
      dp[i][j][3] = 0
     else:
      dp[i][j][3] = dp[i+1][j][3] + 1
for i in range(h+2):
  for j in range(w+2):
    if l[i][j] == '.':
      ans = max(ans, sum(dp[i][j]) - 3)
print(ans)

### FIXED CODE ###

import numpy as np
h,w = map(int,input().split())
ar = np.array([list(input()) for _ in range(h)]) == '.'
#print(ar)
l = np.zeros((h,w),dtype=int)
r = np.zeros((h,w),dtype=int)
u = np.zeros((h,w),dtype=int)
d = np.zeros((h,w),dtype=int)

for i in range(h):
  u[i] = (u[i-1]+1)*ar[i]
  #print(u)
  d[-i-1] = (d[-i]+1)*ar[-i-1]
  #print(d)
  
for j in range(w):
  l[:,j] = (l[:,j-1]+1)*ar[:,j]
  #print(l)
  r[:,-j-1] = (r[:,-j]+1)*ar[:,-j-1]
  #print(r)
print(np.max(u+d+l+r)-3)
### BUGGY CODE ###

N = int(input())
p = tuple(map(float, input().split()))

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

for i in range(1, N + 1):
    for j in range(i + 1):
        dp[i][j] = (dp[i - 1][j] * (1 - p[i - 1])) + (dp[i - 1][j - 1] * p[i - 1])

ans = 0
for j in range(N // 2 + 1, N + 1):
    ans += dp[N][j]
print(ans)
# print(dp)

### FIXED CODE ###

N = int(input())
p = tuple(map(float, input().split()))

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

for i in range(1, N + 1):
    for j in range(i + 1):
        dp[i][j] = (dp[i - 1][j] * (1 - p[i - 1])) + (dp[i - 1][j - 1] * p[i - 1])

ans = 0
for j in range(N // 2 + 1, N + 1):
    ans += dp[N][j]
print(ans)
# print(dp)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import numpy as np

def solve(N: int):
    #9 ** 5 == 59049 < 10 ** 5
    #6 ** 6 == 46656 < 10 ** 5
    dp = [float("inf")]*(N + 1)
    dp[0] = 0
    pull_list_9 = [9**i for i in range(1, 6)]
    pull_list_6 = [6**i for i in range(1, 7)]
    pull_list = np.array(pull_list_9 + pull_list_6 + [1])
    p_s = sorted(pull_list)
    for i in range(1, N + 1):
        for j in p_s:
            if i - j < 0:
                break
            dp[i] = min(dp[i], dp[i-j] + 1)
    print(dp[-1])

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


### FIXED CODE ###

N = int(input())
dp = [float("inf")]*(N + 1)
dp[0] = 0
pull_list_9 = [9**i for i in range(1, 6)]
pull_list_6 = [6**i for i in range(1, 7)]
pull_list = pull_list_9 + pull_list_6 + [1]
p_s = sorted(pull_list)

for i in range(1, N + 1):
  for j in p_s:
    if i - j < 0:
      break
    dp[i] = min(dp[i], dp[i-j] + 1)

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

n,x,y = map(int,input().split())
a = [0]*(n-1)
for i in range(n-1):
    for j in range(i+1,n):
        dist = min(j-i, abs(i-x+1)+1+abs(j-y+1), abs(i-y+1)+1+abs(j-x+1))
        a[dist-1] += 1
for ans in a:
    print(ans)

### FIXED CODE ###

n,x,y = map(int,input().split())
a = [0]*(n-1)
for i in range(n-1):
    for j in range(i+1,n):
        dist = min(j-i, abs(i-x+1)+1+abs(j-y+1))
        a[dist-1] += 1
for ans in a:
    print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    N = int(input())
    S = input().rstrip()
    u = len(set(list(S)))
    tmp = set()
    ans = 0
    for index, i in enumerate(range(N - 2)):
        second = set()
        for j in range(index + 1, N - 1):
            if j in second:
                continue
            if S[i] + S[j] not in tmp:
                second.add(j)
                tmp.add(S[i] + S[j])
                ans += len(set(list(S[j + 1:])))
                if len(tmp) == u ** 2:
                    print(ans)
                    quit()
            if len(second) == u:
                break
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    N = int(input())
    S = input().rstrip()
    ans = 0
    for i in range(1000):
        i = str(i).zfill(3)
        prev = -1
        for s in i:
            pos = S.find(s, prev + 1)
            if pos > prev:
                prev = pos
            else:
                break
        else:
            ans += 1
    print(ans)


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

import sys

def prime_calc(n):
    if n < 2:
        return 0
    else:
        i = 2
        while i*i <= n:
            if n % i == 0:
                return 0
            else:
                i = i + 1

    return 1

def prime(n):
    cnt = 0
    for i in range(1, n+1):
        ans = prime_calc(i)
        if ans == 1:
           cnt = cnt + 1

    return cnt

def main():
    l = []

    for line in sys.stdin:
        l.append(int(line))

    for line in l:
        print(prime(line))

if __name__ == "__main__":
    main()


### FIXED CODE ###

import math
import sys

sup = 1000000

is_prime = [0] * sup

count = [0] * sup

def setup():
    is_prime[2] = 1
    for n in range(3,sup,2):
        flag = True
        for i in range(3, int(math.floor(math.sqrt(n) + 1)), 2):
            if n % i == 0:
                flag = False
                break
        if flag:
            is_prime[n] = 1

def precount():
    for n in range(2, sup):
        count[n] = count[n-1] + is_prime[n]

def main():
    setup()
    precount()

    l = []

    for line in sys.stdin:
        l.append(int(line))

    for line in l:
         print(count[line])

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

N = int(input())
A = list(map(int,input().split()))
c = 0
for i in range(N-1):
    for j in range(i+1,N):
        c += (A[i] * A[j]) %(10**9+7)
print(c%(10**9+7))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
sumA = sum(A)
c = 0

for i in range(N-1):
    c+= A[i]* (sumA-A[i])
    sumA-= A[i]
print(c%(10**9+7))
### BUGGY CODE ###

# coding: utf-8
mod = 998244353
N, S = list(map(int, input().split()))
A = [0] + list(map(int, input().split()))

dp = [[0 for _ in range(S+2)] for i in range(N+1)]

for k in range(0, N):
  for s in range(0, S+1):
    dp[k+1][s] += (2 * dp[k][s] - dp[k-1][s]) % mod
  if S > A[k+1]:
    for s in range(1,S-A[k+1]+1):
      dp[k+1][s+A[k+1]] += (dp[k][s] - dp[k-1][s]) % mod
  if A[k+1] <= S:
    dp[k+1][A[k+1]] += k+1

print(dp[N][S] % mod)

### FIXED CODE ###

# coding: utf-8
import numpy as np
N, S = list(map(int, input().split()))
A = [0]+list(map(int, input().split()))

dt = np.array([[0 for _ in range(S+1)] for x in range(N+1)])

for n in range(1, N+1):
  if A[n] <= S:
    dt[n,A[n]] += n
  if A[n] < S:
    dt[n, A[n]+1:] += dt[n-1,1:S-A[n]+1] - dt[n-2,1:S-A[n]+1]
  dt[n,:] += dt[n-1,:] * 2 - dt[n-2,:]
  dt[n,:] %= 998244353
print(dt[N,S] % 998244353)