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

import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    h,w,k = map(int,ipt().split())
    x1,y1,x2,y2 = map(int,ipt().split())
    x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
    ms = [input()+"@" for _ in range(h)]
    ms.append("@"*(w+1))
    hq = []
    al = [[10**18]*w for _ in range(h)]
    al[x1][y1] = 0
    dr = [(0,1),(1,0),(0,-1),(-1,0)]
    hpq.heappush(hq,(0,x1,y1))
    while hq:
        c,x,y = hpq.heappop(hq)
        cn = c+1
        if x == x2 and y == y2:
            print(c)
            exit()
        for dx,dy in dr:
            xx = x
            yy = y
            for i in range(k):
                xx += dx
                yy += dy
                if ms[xx][yy] == "." and al[xx][yy] >= cn:
                    al[xx][yy] = cn
                    hpq.heappush(hq,(cn,xx,yy))
                else:
                    break
    print(-1)

    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    h,w,k = map(int,ipt().split())
    x1,y1,x2,y2 = map(int,ipt().split())
    x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
    ms = [input()+"@" for _ in range(h)]
    ms.append("@"*(w+1))
    hq = []
    al = [[10**18]*w for _ in range(h)]
    al[x1][y1] = 0
    dr = [(0,1),(1,0),(0,-1),(-1,0)]
    hpq.heappush(hq,(0,x1,y1))
    while hq:
        c,x,y = hpq.heappop(hq)
        cn = c+1
        if x == x2 and y == y2:
            print(c)
            exit()
        for dx,dy in dr:
            xx = x
            yy = y
            for i in range(k):
                xx += dx
                yy += dy
                if ms[xx][yy] == "." and al[xx][yy] > cn:
                    al[xx][yy] = cn
                    hpq.heappush(hq,(cn,xx,yy))
                elif ms[xx][yy] == "." and al[xx][yy] == cn:
                    continue
                else:
                    break
    print(-1)

    return

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

from networkx import*
g=Graph()
for a in[*open(x:=0)][1:]:
  a,b=map(int,a.split())
  g.add_edge(a,7**6+b)
for c in connected_components(g):
  a,b=map(len,bipartite.sets(s:=g.subgraph(c)))
  x+=a*b-len(s.edges)
print(x)

### FIXED CODE ###

class UnionFind():
    def __init__(self,size):
        self.table=[-1]*size
    def root(self,x):
        while self.table[x]>=0:
            x=self.table[x]
        return x
    def unite(self,x,y):
        s1=self.root(x)
        s2=self.root(y)
        if s1!=s2:
            if self.table[s1]>self.table[s2]:
                s1,s2=s2,s1
            self.table[s1]+=self.table[s2]
            self.table[s2]=s1
        return
    def same(self,x,y):
        return self.root(x)==self.root(y)
    def size(self,x):
        return -self.table[self.root(x)]
n,*z=map(int,open(0).read().split())
u=UnionFind(10**5*2+1)
for x,y in zip(*[iter(z)]*2):
    u.unite(x,10**5+y)
d=[[0,set(),set()]for _ in range(10**5*2+1)]
for x,y in zip(*[iter(z)]*2):
    t=d[u.root(x)]
    t[0]+=1
    t[1].add(x)
    t[2].add(y)
print(sum(len(x)*len(y)-a for a,x,y in d))
### BUGGY CODE ###

n,m=map(int,input().split())
h=list(map(int,input().split()))
a=[]
b=[]
for i in range(m):
    aa,bb=map(int,input().split())
    a.append(aa-1)
    b.append(bb-1)
ans=0
t=[False]*n
for i in range(n):
    flag=True
    for j in range(m):
        if(a[j]==i):
            if(h[i]<=h[b[j]]):
                flag=False
                break
        if(b[j]==i):
            if(h[i]<=h[a[j]]):
                flag=False
                break
    if(flag):
        ans+=1
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
h=list(map(int,input().split()))
t=[]
for i in range(m):
    t.append(list(map(int,input().split())))
ans=[True]*n
for i in range(m):
    a,b=t[i]
    if(h[a-1]<=h[b-1]):
        ans[a-1]=False
    if(h[b-1]<=h[a-1]):
        ans[b-1]=False
print(ans.count(True))
### BUGGY CODE ###

N, A, B = map(int, input().split())
round_count = 0

med = N / 2 + 0.5
maxAB = 10 ** 18

Max = max([A, B])
Min = min([A, B])

for i in range(maxAB):
    if (Max - Min) % 2 == 0:
            Max = Max - 1
            Min = Min + 1
    else:
        medAB = (Max + Min) / 2
        if medAB > med:
            Max = Max + 1
            Min = Min + 1

            if Max > N:
                Max = N
            elif Min > N:
                Min = N
        else:
            Max = Max - 1
            Min = Min - 1
        
            if Max < 1:
                Max = 1
            elif Min < 1:
                Min = 1
        

    round_count = round_count + 1

    if Max == Min:
        break

print(round_count)

### FIXED CODE ###

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

med = N / 2 + 0.5
Sub = B - A

if (Sub) % 2 == 0:
    round_count = Sub // 2
else:
    round_count = min(A - 1, N - B) + 1 + (Sub - 1) // 2
            
print(round_count)
### BUGGY CODE ###

from sys import exit
import sys

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

_a = -1
B = []
ans = 0
count = 0

for i in range(M):
    a_ = int(input())
    if _a + 1 == a_:
        print(0)
        exit()
    _a = a_
    N -= 2
    count += 1
    B.append(_a + 2 - 2 * count)


step = [1]

for s in range(1, N + 1):
    if s == 1:
        step.append(1)
        continue
    if s in B:
        step.append(step[s - 1])
        continue
    else:
        step.append((step[s - 1] + step[s - 2]) % 1000000007)

print(step[N] % 1000000007)


### FIXED CODE ###

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

A = [False] * (N + 1)

for _ in range(M):
    A[int(input())] = True

step = [0] * (N + 1)

step[0] = 1

for s in range(1, N + 1):
    if A[s]:
        step[s] = 0
        continue
    if s == 1:
        step[s] = 1
        continue
    else:
        step[s] = step[s - 1] + step[s - 2]
        step[s] %= 1000000007

print(step[N])
### BUGGY CODE ###

cnt = 0
n = int(input())
S = []
for i in range(n):
    s = list(input())
    s.sort()
    S.append(s)
    cnt += S.count(S[i])-1
print(cnt)

### FIXED CODE ###

from collections import Counter

n = int(input())
S = []
for _ in range(n):
    s = sorted(list(input()))
    S.append(''.join(s))

S_cnt = Counter(S)

ans = 0
for k,v in S_cnt.items():
    ans += v*(v-1)//2
print(ans)
### BUGGY CODE ###

def main():
    n = 13
    mod = 1000000007
    r = 5
    in_str = input()

    amari_list = amari(n)
    l = len(amari_list)

    ans_list = initial(in_str[-1:], n)

    for i, s in enumerate(reversed(in_str)):
        if i == 0:
            continue
        if s == "?":
            tmp_list, ans_list = ans_list, [0]*n
            for j in range(10):
                t = j * amari_list[i % l] % n
                ans_list = add(ans_list, shift(t, tmp_list))
        else:
            t = int(s) * amari_list[i % l] % n
            ans_list = shift(t, ans_list)

        ans_list = list(map(lambda x: x % mod, ans_list))

    print(ans_list[r] % mod)


def shift(r, ans_list):
    l = len(ans_list)
    return [ans_list[(i + l - r) % l] for i in range(l)]


def add(list1, list2):
    return list(map(sum, zip(list1, list2)))


def initial(s, n):
    if s == "?":
        return [1 if i < 10 else 0 for i in range(n)]
    else:
        return [1 if i == int(s) else 0 for i in range(n)]


def amari(n):
    ret = []
    for i in range(n+1):
        r = (10**i) % n
        if r in ret:
            return ret
        else:
            ret.append(r)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np


def main():
    n = 13
    mod = 1000000007
    r = 5
    in_str = input()

    amari_l = amari_list(n)
    amari_m = amari_matrix(n, amari_l)

    ans_list = initial(in_str[-1:], n)

    for i, s in enumerate(reversed(in_str)):
        if i == 0:
            continue
        if s == "?":
            ans_list = np.dot(ans_list, amari_m[i % len(amari_m)]) % mod
        else:
            t = int(s) * amari_l[i % len(amari_l)] % n
            ans_list = np.roll(ans_list, t)

    print(int(ans_list[r] % mod))


def initial(s, n):
    if s == "?":
        return np.array([1 if i < 10 else 0 for i in range(n)], dtype='int64')
    else:
        return np.array([1 if i == int(s) else 0 for i in range(n)], dtype='int64')


def shift(n, r):
    return np.array([[1 if (i - j + r) % n == 0 else 0 for j in range(n)] for i in range(n)])


def amari_list(n):
    ret = []
    for i in range(n + 1):
        r = 10**i % n
        if r in ret:
            return ret
        else:
            ret.append(r)


def amari_matrix(n, amari_list):
    ret = np.zeros((len(amari_list), n, n))
    for i, j in enumerate(amari_list):
        tmp = np.zeros((n, n))
        for k in range(10):
            tmp += shift(n, j * k % n)
        ret[i] = tmp
    return ret


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

A, B, C, K = map(int, input().split())
num = 10**18

for i in range(K):
    A, B, C = B+C, A+C, A+B
    if A == B == C:
        print(0)
        exit()

if (A - B) > num:
    print('Unfair')
else:
    print(A - B)

### FIXED CODE ###

A, B, C, K = map(int, input().split())
num = 10**18

if K % 2 == 0:
    ans = A - B
else:
    ans = B - A

if ans > num:
    print('Unfair')
else:
    print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

def solve(index: int, dp: list, footing: list, K: int) -> int:
    if dp[index] != -1:
        return dp[index]

    if index == 0:
        return 0
    elif index == 1:
        return abs(footing[1]-footing[0])

    tmp = 10 ** 10
    for k in range(1, min(K+1,index+1)):
        tmp = min(tmp, solve(index-k, dp, footing, K)+abs(footing[index]-footing[index-k]))

    #print(f'{tmp=}')
    dp[index] = tmp
    return tmp

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

dp = [-1] * N

ans = solve(N-1, dp, footing, K)

print(ans)

### FIXED CODE ###

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


dp = [10 ** 10] * N
dp = dp + [10 ** 10] * 1000
dp[0] = 0

footing = footing + [0] * 1000
# give
'''
for i in range(N-1):
    for k in range(1, K+1):
        if dp[i+k] > dp[i] + abs(footing[i+k] - footing[i]):
            dp[i+k] = dp[i] + abs(footing[i+k] - footing[i])

print(dp[N-1])
'''
# get
for i in range(1,N):
    for j in range(1,min(K+1, i+1)): 
        dp[i] = min(dp[i],dp[i-j] + abs(footing[i]-footing[i-j])) 

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

h,*s=open(0)
s=[tuple(t[:-1])for t in s]
h,w=map(int,h.split())
a,b,c,d=[],[],[],[]
for t in s:
    e=[t[0]=='.']
    for u in t[1:]:
        e.append(-~e[-1]*(u=='.'))
    a.append(tuple(e))
    e=[t[-1]=='.']
    for u in t[-2::-1]:
        e.append(-~e[-1]*(u=='.'))
    b.append(tuple(e[::-1]))
for t in zip(*s):
    e=[t[0]=='.']
    for u in t[1:]:
        e.append(-~e[-1]*(u=='.'))
    c.append(tuple(e))
    e=[t[-1]=='.']
    for u in t[-2::-1]:
        e.append(-~e[-1]*(u=='.'))
    d.append(tuple(e[::-1]))
print(max(sum(u)-3for t in zip(a,b,tuple(zip(*c)),tuple(zip(*d)))for u in zip(*t)))

### FIXED CODE ###

def main():
    h,*s=open(0)
    h,w=map(int,h.split())
    a=tuple([0]*w for _ in range(h))
    b=tuple([0]*w for _ in range(h))
    c=tuple([0]*w for _ in range(h))
    d=tuple([0]*w for _ in range(h))
    for i in range(h*w):
        i,j=divmod(i,w)
        a[i][j]=a[i][j-1]+1if s[i][j]=='.'else 0
        b[i][~j]=b[i][-j]+1if s[i][-j-2]=='.'else 0
        c[i][j]=c[i-1][j]+1if s[i][j]=='.'else 0
        d[~i][j]=d[-i][j]+1if s[~i][j]=='.'else 0
    print(max(a[i][j]+b[i][j]+c[i][j]+d[i][j]-3for i in range(h)for j in range(w)))
main()
### BUGGY CODE ###

import sys
import numpy as np
import bisect

N, M = map(int, sys.stdin.readline().split())
A = np.array(list(map(int, sys.stdin.readline().split())))
A.sort()

max = A[N - 1]

count = 0

while count < M:
    c = bisect.bisect_left(A, int(max / 2))
    add = N - c
    if count + add > M:
        d = M - count
        A[-d:] = A[-d:] // 2
        break
    else:
        A[c:] = A[c:] // 2
        count += add
    
ans = int(sum(A))

print(ans)

### FIXED CODE ###

import sys
import numpy as np
import bisect

N, M = map(int, sys.stdin.readline().split())
A = np.array(list(map(int, sys.stdin.readline().split())))
A.sort()

max = A[N - 1]

count = 0

while count < M:
    max = A[N - 1]
    c = bisect.bisect_left(A, int(max / 2))
    add = N - c
    if count + add > M:
        d = M - count
        A[-d:] = A[-d:] // 2
        break
    else:
        A[c:] = A[c:] // 2
        count += add
        if count == M:
            break
    A.sort()
    
ans = int(sum(A))

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

N = int(input())
A = list(input().split())
B = [0 for i in range(N)]
for i in range (N-1):
  for j in range (1,N+1):
    if int(A[i])==j:
      B[j-1]=B[j-1]+1
      break
[print(i) for i in B]
 

### FIXED CODE ###

import collections
N = int(input())
A = list(input().split())
c=collections.Counter(A)
for i in range (1,N+1):
    print(c[str(i)])
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]
for k in range(n):
    s[k]=sorted(list(s[k]))
count = 0

for x in range (n-1):
    for y in range (x+1,n):
        if s[x]==s[y]:
            count += 1
print(count)


### FIXED CODE ###

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

n = int(input())
s = [input() for i in range(n)]
for k in range(n):
    s[k]=sorted(list(s[k]))
s=sorted(s)

c = 1
count = 0

for x in range (n-1):
        if s[x]==s[x+1]:
            c += 1
        else:
            if c>= 2:
                count += cmb(c,2)
            c = 1
if c >=2:
    count += cmb(c,2)
print(count)
### BUGGY CODE ###

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

diff = [0] * (N)
diffsum = 0
for i in range(N):
    diff[i] = A[i] - B[i]
    diffsum += diff[i]
if diffsum < 0:
    print("-1")
    exit()
diff.sort()
change = [0] * (N)
for i in range(N):
    if diff[i] < 0:
        change[i] = 1
        for j in range(N)[::-1]:
            if diff[j] > 0:
                change[j] = 1
                ch = min(-diff[i], diff[j])
                diff[i] += ch
                diff[j] -= ch
                if diff[i] == 0:
                    break
print(sum(change))

### FIXED CODE ###

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

diff = [0] * (N)
diffsum = 0
for i in range(N):
    diff[i] = A[i] - B[i]
    diffsum += diff[i]
if diffsum < 0:
    print("-1")
    exit()
diff.sort()
count = 0
sumn = 0
for i in range(N):
    if diff[i] < 0:
        count += 1
        sumn -= diff[i]
    else:
        break
for j in range(N)[::-1]:
    if sumn > 0:
        count += 1
        sumn -= diff[j]
print(count)
### BUGGY CODE ###

from math import ceil #切り上げ
import numpy as np
 
def inp(): return int(input()) #一個だけ読み取り
def inpm(): return map(int,input().split()) #mapオブジェクトで呼び出し
def inpl(): return list(map(int, input().split())) #数字リストをintで
def inpls(): return list(input().split()) #リストをstrで

A,B,N = inpl()
x = 0
for i in range(0,N+1):
  if B > i:
    x = i
  else:
    break
    
print(A*x//B)

### FIXED CODE ###

from math import ceil #切り上げ
import numpy as np
 
def inp(): return int(input()) #一個だけ読み取り
def inpm(): return map(int,input().split()) #mapオブジェクトで呼び出し
def inpl(): return list(map(int, input().split())) #数字リストをintで
def inpls(): return list(input().split()) #リストをstrで

A,B,N = inpl()
if B <= N:
  x = B-1
else:
  x = N
    
print(A*x//B)
### BUGGY CODE ###

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

for i in range(n):
    print(a.index(i+1) + 1, end=' ')


### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]

a = sorted(range(n), key=lambda x: a[x])
a = [print(i+1, end=' ') for i in a]
### BUGGY CODE ###

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

def sub_sort(list,num):
    for i,elem in enumerate(list):
        if num >= elem:
            list.insert(i,num)
            return list
        elif i == len(list) - 1:
            list.append(num)
            return list

if n == 1:
    for i in range(m):
        a_list[0] = a_list[0] // 2
    print(a_list[0])
else:
    a_list.sort(reverse=True)
    for i in range(m):
        a_list = sub_sort(a_list[1:],a_list[0]//2)
    print(sum(a_list))

### FIXED CODE ###

import heapq

# O(MlogN)
n,m = map(int,input().split())
a_list = list(map(lambda x: int(x)*(-1),input().split()))
heapq.heapify(a_list)

for _ in range(m):
    tmp_min = heapq.heappop(a_list)
    heapq.heappush(a_list, (-1)*(-tmp_min//2)) 

print(-sum(a_list))
### BUGGY CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=998244353
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  s=S()
  n=len(s)
  t=S()
  n2=len(t)

  d={}
  for i,x in enumerate(s):
    if x in d:
      y=d[x]
      y.append(i)
      d[x]=y
    else:
      d[x]=[i]

  # print(d)
  i=0
  j=0
  ans=1
  while j<n2:
    check=t[j]
    if check not in d:
      return -1
    l=d[check]
    if i<l[0]:
      ans+=l[0]-i+1
      i=l[0]+1
      j+=1
    elif l[-1]<i:
      ans+=n-(i+1)+l[0]+2
      i=l[0]+1
      j+=1
    else:
      if i==l[0]:
        ans+=1
        i+=1
        j+=1
      elif i==l[-1]:
        ans+=1
        i+=1
        j+=1
      else:
        left=0
        right=len(l)
        while right-left>1:
          m=(right-left)//2
          if l[m]>=i:
            right=m
          else:
            left=m
        ans+=l[right]-i+1
        i=l[right]+1
        j+=1

    # print(i,ans)

    i%=n

  return ans-1

# main()
print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=998244353
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  s=S()
  n=len(s)
  t=S()
  n2=len(t)

  d={}
  for i,x in enumerate(s):
    if x in d:
      y=d[x]
      y.append(i)
      d[x]=y
    else:
      d[x]=[i]

  # print(d)
  i=0
  j=0
  ans=1
  while j<n2:
    check=t[j]
    if check not in d:
      return -1
    l=d[check]
    if i<l[0]:
      ans+=l[0]-i+1
      i=l[0]+1
      j+=1
    elif l[-1]<i:
      ans+=n-(i+1)+l[0]+2
      i=l[0]+1
      j+=1
    else:
      if i==l[0]:
        ans+=1
        i+=1
        j+=1
      elif i==l[-1]:
        ans+=1
        i+=1
        j+=1
      else:
        left=0
        right=len(l)
        while right-left>1:
          m=(right+left)//2
          if l[m]>=i:
            right=m
          else:
            left=m
          # print(right,left,m,i)
        ans+=l[right]-i+1
        i=l[right]+1
        j+=1

    # print(i,ans)

    i%=n

  return ans-1

# main()
print(main())
### BUGGY CODE ###

h, n = map(int, input().split())
a, b = [], []
for i in range(n):
    a_, b_  = map(int, input().split())
    a.append(a_)
    b.append(b_)
dp = [0] * (max(a) + h)
for i in range(1, max(a) + h):
    dp[i] = min(dp[i - a[j]] + b[j] for j in range(n))
print(min(dp[h:]))

### FIXED CODE ###

h, n = map(int, input().split())
a, b = [], []
for i in range(n):
    a_, b_  = map(int, input().split())
    a.append(a_)
    b.append(b_)
dp = [0] * (max(a) + h)
for i in range(1, max(a) + h):
    dp[i] = min(dp[i - a[j]] + b[j] for j in range(n))
print(min(dp[h:]))
### BUGGY CODE ###

R, C, K = map(int, input().split())

V = [[0]*(C+1) for _ in range(R+1)]
for _ in range(K):
    r, c, v = map(int, input().split())
    V[r][c] = v

pre0 = [0]*(C+1)
pre1 = [0]*(C+1)
pre2 = [0]*(C+1)
pre3 = [0]*(C+1)
for i in range(R+1):
    now0 = [0]*(C+1)
    now1 = [0]*(C+1)
    now2 = [0]*(C+1)
    now3 = [0]*(C+1)
    for j in range(C+1):
        v = V[i][j]
        la = lb = 0
        if j > 0:
            la = now0[j-1]
            lb = now1[j-1]
            now2[j] = max(now2[j], now2[j-1], lb + v)
            now3[j] = max(now3[j], now3[j-1], now2[j-1] + v)
        if i > 0:
            max_p = max(pre0[j], pre1[j], pre2[j], pre3[j])
            now0[j] = max(now0[j], max_p, la)
            now1[j] = max(now1[j], max_p + v, la + v, lb)
    pre0 = now0
    pre1 = now1
    pre2 = now2
    pre3 = now3

print(max(now0[C], now1[C], now2[C], now3[C]))


### FIXED CODE ###

R, C, K = map(int, input().split())

V = [[0]*(C+1) for _ in range(R+1)]
for _ in range(K):
    r, c, v = map(int, input().split())
    V[r][c] = v

pre = [[0]*(3+1) for _ in range(C+1)]
for i in range(R+1):
    now = [[0]*(3+1) for _ in range(C+1)]
    for j in range(C+1):
        for k in range(3+1):
            if i-1 >= 0:
                now[j][0] = max(now[j][0], pre[j][k])
                now[j][1] = max(now[j][1], pre[j][k] + V[i][j])

            if j-1 >= 0:
                now[j][k] = max(now[j][k], now[j-1][k])
                if k-1 >= 0:
                    now[j][k] = max(now[j][k], now[j-1][k-1] + V[i][j])
    pre = now

print(max(now[C]))
### BUGGY CODE ###

def p_m():
    n, k = map(int, input().split())
    *a, = map(int, input().split())
    mod = 10 ** 9 + 7
    # dp[i][j]はi番目の子にj個の飴を配る方法が何通りかどうか
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 1

    count = 0
    for i in range(n):
        for j in range(min(k + 1, count + 1)):
            count += a[i]
            for m in range(a[i] + 1):
                if j + m > k:
                    break
                dp[i + 1][j + m] += dp[i][j]
                dp[i + 1][j + m] %= mod
    print(dp[n][k])


if __name__ == '__main__':
    p_m()

### FIXED CODE ###

def p_m():
    n, k = map(int, input().split())
    *a, = map(int, input().split())
    mod = 10 ** 9 + 7
    # dp[i][j]はi番目の子にj個の飴を配る方法が何通りかどうか
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = 1

    for i in range(1, n + 1):
        for j in range(1, k + 1):
            if j - 1 - a[i - 1] >= 0:
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1 - a[i - 1]]) % mod
            else:
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod
    print(dp[n][k])


if __name__ == '__main__':
    p_m()