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

#全体に同じものを足すときは累積和を考えたい

N,Q = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N-1)]
PX = [list(map(int,input().split())) for _ in range(Q)]

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

for a,b in AB:
    graph[a].add(b)
    graph[b].add(a)
#どちらが親か分からないがとりあえずつながっている
#どちらが親かは後で判断

counter = [0 for _ in range(N+1)]
#counter[i]:i番目の頂点のカウンター
check = [False for _ in range(N+1)]
check[1] = True
for p,x in PX:
    counter[p] += x

def dfs(graph,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if check[e]:
                continue
            counter[e] += counter[p]
            stk.append(e)
            check[e] = True

dfs(graph,counter,1)

ans = " ".join(map(str,counter[1:]))
print(ans)


### FIXED CODE ###

#全体に同じものを足すときは累積和を考えたい

N,Q = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N-1)]
PX = [list(map(int,input().split())) for _ in range(Q)]

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

for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
#どちらが親か分からないがとりあえずつながっている
#どちらが親かは後で判断

counter = [0 for _ in range(N+1)]
#counter[i]:i番目の頂点のカウンター
parent = [None for _ in range(N+1)]

for p,x in PX:
    counter[p] += x

def dfs(graph,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

dfs(graph,counter,1)

ans = " ".join(map(str,counter[1:]))
print(ans)
### BUGGY CODE ###

import itertools
N = int(input())
s = [0] * N
answer = 0
for i in range(N):
    s[i] = int(input())
for i in range(1, N+1):  # 何問正解するか、0からN問まで
    for v in itertools.combinations(s, i):
        if sum(v) % 10 != 0 and answer <= sum(v):
            answer = sum(v)
        # print(v, sum(v))

print(answer)
        

### FIXED CODE ###

import itertools
N = int(input())
s = [0] * N
not10 = []
answer = 0
for i in range(N):
    s[i] = int(input())

SUM = sum(s)
if SUM % 10 != 0:
    print(SUM)
    exit()
else:
    for i in range(N):
        if s[i] % 10 != 0:
            not10.append(s[i])
    not10.sort()
    if len(not10) == 0:
        print(0)
    else:
        print(SUM - not10[0])
    exit()
            
# print(not10)

# for i in range(1, N+1):  # 何問正解するか、0からN問まで
#     for v in itertools.combinations(s, i):
#         if sum(v) % 10 != 0 and answer <= sum(v):
#             answer = sum(v)
#         print(v, sum(v))

# print(answer)
### BUGGY CODE ###

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

mod = 1000000007

A = []
for i in range(M):
    A.append(int(input()))
    
DP = [0]*(N+2)
DP[1] = 1

for i in range(2, N+2):
    if i-1 not in A:
        DP[i] =  DP[i-1]%mod + DP[i-2]%mod

print(DP[N+1]%mod)

### FIXED CODE ###

N, M = map(int, input().split())
A = set([int(input()) for i in range(M)])
B = [0]*(N+1)
B[0] = 1
for i in range(1, N+1):
    B[i] = B[i-1] + B[i-2]
    if i in A:
        B[i] = 0
print(B[N]%1000000007)
### BUGGY CODE ###

R,G,B,N=map(int,input().split())

ans=0
for r in range(3000+1):
    for g in range(3000+1):
        for b in range(3000+1):
            if r*R+g*G+b*B==N:
                ans+=1
            elif r*R+g*G+b*B>N:
                b=0
                break
        if r*R+g*G>N:
            g=0
            break
    if r*R>N:
        break
print(ans)

### FIXED CODE ###

R,G,B,N=map(int,input().split())

ans=0
for r in range(3000+1):
    if N < r*R:
        break
    for g in range(3000+1):
        if N < r*R+g*G:
            break
        if (N-r*R-g*G)%B==0:
#            print('({0}-{1}*{2}-{3}*{4})%{5}'.format(N,r,R,g,G,B))
            ans+=1
print(ans)
### BUGGY CODE ###

from collections import deque
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read():
    N = int(input().strip())
    P = list(map(float, input().strip().split()))
    return N, P


def solve(N, P):
    # dp[i, j]: i枚目まで投げて、表がj枚出る確率
    # dp[i, j] = dp[i-1, j-1] * p[j] + dp[i, j-1] * (1-p[j])
    # 2000x(N//2)のテーブルを作るとTLEするので、圧縮して解く
    dp = [[0 for j in range(N+1)] for i in range(2)]
    dp[0][0] = 1
    for j in range(1, N+1):
        dp[0][j] = dp[0][j-1] * (1.0 - P[j-1])
    ans = 0.0
    for i in range(1, N+1):
        b = i % 2
        for j in range(i):
            dp[b][j] = 0.0
        for j in range(i, N+1):
            dp[b][j] = dp[(b-1)%2][j-1] * P[j-1] + dp[b][j-1] * (1.0 - P[j-1])
        if i > N//2:
            ans += dp[b][-1]
    return "{:.10f}".format(ans)


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))


### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read():
    N = int(input().strip())
    P = list(map(float, input().strip().split()))
    return N, P


def solve(N, P):
    # dp[i, j]: i枚目まで投げて、表がj枚出る確率
    # dp[i, j] = dp[i-1, j-1] * p[j] + dp[i, j-1] * (1-p[j])
    # 2000x(N//2)のテーブルを作るとTLEするので、圧縮して解く
    dp = [[0 for j in range(N+1)] for i in range(2)]
    dp[0][0] = 1
    for j in range(1, N+1):
        dp[0][j] = dp[0][j-1] * (1.0 - P[j-1])
    ans = dp[0][-1]
    for i in range(1, N//2+1):
        b = i % 2
        dp[b][i-1] = 0.0
        for j in range(i, N+1):
            dp[b][j] = dp[(b-1)%2][j-1] * P[j-1] + dp[b][j-1] * (1.0 - P[j-1])
        ans += dp[b][-1]
    return "{:.10f}".format(1.0 - ans)


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))
### BUGGY CODE ###

# python3だとTLE,pypy3だとAC

def main():
    N = int(input())
    p = tuple(map(float, input().split()))
    dp = [[0.0] * (N + 1) for _ in range(N + 1)]
    dp[0][0] = 1.0
    for i in range(1, N+1):
        for j in range(0, N+1):
            dp[i][j] = dp[i - 1][j] * \
                (1 - p[i - 1]) + dp[i - 1][j - 1] * p[i - 1]
    print(sum(dp[N][N//2+1:]))


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N = int(input())
    p = list(map(float, input().split()))
    dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
    p_mul = 1
    dp[0][0] = 1
    for i in range(1, N + 1):
        p_mul *= (1-p[i-1])
        dp[i][0] = p_mul
    for i in range(1, N+1):
        for j in range(1, N+1):
            dp[i][j] = dp[i - 1][j] * \
                (1 - p[i - 1]) + dp[i - 1][j - 1] * p[i - 1]
    print(sum(dp[N][N//2+1:]))


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

import sys
import numpy as np
h, w, k = map(int, input().split())
s = [[int(c) for c in l.strip()] for l in sys.stdin]
s = np.array(s)

def count(li):
    if np.max(li) > k:
        return -1
    tmp = np.zeros(len(li), dtype=int)
    cnt = 0
    for i in range(w):
        tmp += li[:, i]
        if np.max(tmp) > k:
            cnt += 1
            tmp = li[:, i]
    return cnt

ans = 1000000
for i in range(2**(h-1)):
    r = 0
    l = []
    for j in range(h-1):
        if (i>>j)&1:
            l.append(np.sum(s[r:j+1, :], axis=0))
            r = j+1
    l.append(np.sum(s[r:, :], axis=0))
    cnt = count(np.vstack(l))
    if cnt>=0:
        ans = min(ans, cnt+len(l)-1)
print(ans)


### FIXED CODE ###

import numpy as np
h, w, k = map(int, input().split())
s = []
for _ in range(h):
    s.append(list(map(int, list(input()))))
s = np.array(s)

def count(li):
    if np.max(li) > k:
        return -1
    tmp = np.zeros(len(li), dtype=int)
    cnt = len(li)-1
    for i in range(w):
        tmp += li[:, i]
        if np.max(tmp) > k:
            cnt += 1
            if cnt >= ans:
                return -1
            tmp = li[:, i]
    return cnt

ans = 1000000
for i in range(2**(h-1)):
    r = 0
    l = []
    for j in range(h-1):
        if (i>>j)&1:
            l.append(np.sum(s[r:j+1, :], axis=0))
            r = j+1
    l.append(np.sum(s[r:, :], axis=0))
    if ans <= len(l)-1:
        continue
    cnt = count(np.vstack(l))
    if cnt>=0:
        ans = min(ans, cnt)
print(ans)
### BUGGY CODE ###

from collections import Counter

def main()->None:
    # a_iに１を足すか、１引くか、何もしないかの操作を行って、ある整数個数最大化をする
    # x を決めるとgreedyに決まる。
    # どうやってxを決めるのか。
    N = int(input())
    a = list(map(int, input().split()))
    set_a = set(a)
    max_count = 0
    for a_compo in set_a:
        X = a_compo
        tmp_count = 0
        for i in set_a:
            if abs(X - i) <= 1:
                tmp_count += a.count(i)
        if tmp_count > max_count:
            max_count = tmp_count
    print(max_count)

if __name__ == "__main__":
    main()
 

### FIXED CODE ###

import sys


def main()->None:
    N = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    max_a = max(a)
    # print(max_a)
    l = [0 for _ in range(max_a+2)] # 配列の初期化、固定長、位置が配列の数字で要素がカウント
    for i in a:
        l[i] += 1
    res = 0
    for i in range(0, max_a+1):
        tmp = l[i-1]+l[i]+l[i+1]
        res = max(res, tmp)
    print(res)


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

e=enumerate
h,w=map(int,input().split())
a=[list(map(int,input().split()))for _ in range(h)]
b=[list(map(int,input().split()))for _ in range(h)]
dp=[[]for _ in range(w)]
for i,(a,b)in e(zip(a,b)):
  for j,(x,y)in e(zip(a,b)):
    x,y=x-y,y-x
    t=set()
    add=t.add
    if j:
      for v in dp[j-1]:
        add(v+x)
        add(v+y)
    if i:
      for v in dp[j]:
        add(v+x)
        add(v+y)
    if i+j:dp[j]=t
    else:dp[j]={x,y}
print(min(map(abs,dp[w-1])))

### FIXED CODE ###

e=enumerate
h,w=map(int,input().split())
a=[list(map(int,input().split()))for _ in range(h)]
b=[list(map(int,input().split()))for _ in range(h)]
dp=[0]*w
c=13000
for i,(a,b)in e(zip(a,b)):
  for j,(x,y)in e(zip(a,b)):
    x=abs(x-y)
    if i==j==0:
      dp[j]=2**c<<x
      continue
    t=0
    if j:
      t|=dp[j-1]<<x
      t|=dp[j-1]>>x
    if i:
      t|=dp[j]<<x
      t|=dp[j]>>x
    dp[j]=t
*a,=map(int,(bin(dp[w-1])[2:]).zfill(26001))
print(min([i for i,f in e(a[13000:])if f]+[i for i,f in e(a[13000::-1])if f]))
### BUGGY CODE ###


import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

N, W = map(int, input().split())
w = []
v = []
for i in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

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

for i in range(1, N+1):
    for j in range(1, W+1):
        if j < w[i-1]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]]+v[i-1])

print(dp[N][W])

### FIXED CODE ###



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


N, W = map(int, input().split())
w = [0] * N
v = [0] * N

for i in range(N):
    a, b = map(int, input().split())
    w[i] = a
    v[i] = b

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

for i  in range(N):
    for sum_w in range(W+1):
        if sum_w - w[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w-w[i]] + v[i])

        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

print(dp[N][W])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import heapq
def prim_heap():
    used = [True] * n #True:不使用
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res

n = int(input())
st = []

from collections import deque
edge = deque([[] for i in range(n)])
for i in range(n):
    x,y = map(int,input().split())
    st_append = st.append
    st_append((i,x,y))
    
from operator import itemgetter
bb = tuple(sorted(st,key=itemgetter(1)))
chk = tuple(sorted(st,key=itemgetter(2)))
#print(bb,chk)

for i in range(n-1):
  x = bb[i][0]
  y = bb[i+1][0]
  z = bb[i+1][1]-bb[i][1]
  edge[x].append([z,y])
  edge[y].append([z,x])
  
for i in range(n-1):
  a = chk[i][0]
  b = chk[i+1][0]
  c = chk[i+1][2]-chk[i][2]
  edge[a].append([c,b])
  edge[b].append([c,a])
  
edge = tuple(edge)
print(prim_heap())

### FIXED CODE ###

import sys
input = sys.stdin.readline
import heapq
def prim_heap():
    used = [True] * n #True:不使用
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res

from collections import deque
n = int(input())
st = deque([])

edge = deque([[] for i in range(n)])
for i in range(n):
    x,y = map(int,input().split())
    st_append = st.append
    st_append((i,x,y))
    
from operator import itemgetter
bb = tuple(sorted(st,key=itemgetter(1)))
chk = tuple(sorted(st,key=itemgetter(2)))
#print(bb,chk)

for i in range(n-1):
  x = bb[i][0]
  y = bb[i+1][0]
  z = bb[i+1][1]-bb[i][1]
  edge[x].append((z,y))
  edge[y].append((z,x))
  
for i in range(n-1):
  a = chk[i][0]
  b = chk[i+1][0]
  c = chk[i+1][2]-chk[i][2]
  edge[a].append((c,b))
  edge[b].append((c,a))
  
edge = tuple(edge)
print(prim_heap())
### BUGGY CODE ###

A,B=map(int,input().split())
def cf(a,b):
  cf=[]
  for i in range(1,min(a,b)+1):
    if a%i==0 and b%i==0:
      cf.append(i)
  return cf
x=[x for x in cf(A,B) if all(x%y!=0 for y in range(2,x))]
print(len(x))

### FIXED CODE ###

from fractions import gcd
A,B=map(int,input().split())
s=set()
x=gcd(A,B)
y=2
while y*y<=x:
  while x%y==0:
    s.add(y)
    x//=y
  y+=1
if x>1:
  s.add(x)
print(len(s)+1)
### BUGGY CODE ###

a,b,x = map(int, input().split())
T = []
for i in range(a,b+1):
	if i%x==0:
		T.append(i)
	else:
		quit
print(len(T))

### FIXED CODE ###

import math
a,b,x = map(int, input().split())
print(b//x-(a+x-1)//x+1)
### BUGGY CODE ###

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

cur=True
for i in range(Q):
  q=list(input().split())
  if q[0]=="1":
    cur^=True
  elif q[0]=="2":
    f,c=q[1],q[2]
    if f=="1":
      if cur:
        S=c+S
      else:
        S=S+c
    elif f=="2":
      if cur:
        S=S+c
      else:
        S=c+S
if not cur:
  S=S[::-1]
  
print(S)
    

### FIXED CODE ###

import sys
readline=sys.stdin.readline

S=readline().rstrip()
Q=int(readline())

cur=True
front=""
back=""
for i in range(Q):
  q=list(readline().rstrip().split())
  if q[0]=="1":
    cur^=True
  elif q[0]=="2":
    f,c=q[1],q[2]
    if f=="1":
      if cur:
        front+=c
      else:
        back+=c
    elif f=="2":
      if cur:
        back+=c
      else:
        front+=c
front=front[::-1]
ans=front+S+back
if not cur:
  ans=ans[::-1]
  
print(ans)
### BUGGY CODE ###

import math
 
 
def gcd(a, b, c):
  d = math.gcd(a, b)
  return math.gcd(c, d)
 
K = int(input())
sum = 0
 
for i in range(1, K+1):
  for j in range(1, K+1):
    for k in range(1, K+1):
      sum += gcd(i, j, k)
      
print(sum)

### FIXED CODE ###

import math
 
 
def gcd(a, b, c):
  d = math.gcd(a, b)
  return math.gcd(c, d)
 
K = int(input())
sum = 0
for i in range(1, K+1):
  sum += gcd(i, i, i)
  
for i in range(1, K+1):
  for j in range(i, K+1):
    for k in range(j, K+1):
      if i == j and j == k:
        sum += 0
      elif i == j or j == k or i == k:
        sum += gcd(i , j , k )*3
      elif i != j and j != k :
        sum += gcd(i, j, k)*6

print(sum)
### BUGGY CODE ###

H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

ans = 0


for i in range(H):
    for j in range(W):
        # print(f"i{i} j{j}")
        cnt = 0
        if S[i][j] == ".":
            #右に進む
            for k in range(j+1, W):
                # print(f"rk{k}")
                if S[i][k] == "#":
                    # print("BBB")
                    break
                if k < W:
                    # print("c")                    
                    cnt += 1
            #左に進む
            for k in range(1, j+1):
                # print(f"lk{k}")
                if S[i][j-k] == "#":
                    # print("BBB")
                    break
                if k >= 0:
                    # print("c")
                    cnt += 1
            #下
            for k in range(i+1, H):
                # print(f"dk{k}")
                if S[k][j] == "#":
                    # print("BBB")
                    break
                if k < H:
                    # print("c")
                    cnt += 1
            #上
            for k in range(1, i+1):
                # print(f"uk{k}")
                if S[i-k][j] == "#":
                    # print("BBB")
                    break
                if k >= 0:
                    # print("c")
                    cnt += 1
        ans = max(ans, cnt+1)
        # print(f"ans{ans}--------------")
print(ans)

### FIXED CODE ###

import numpy as np
h, w = map(int, input().split())
arr = np.array([list(input()) for _ in range(h)]) == "."
# print(arr)
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) * arr[i] #arrがFalseだと0になる
    d[- i - 1] = (d[- i] + 1) * arr[- i - 1]

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

N, K = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

minimumCost = [0 for i in range(N)]

minimumCost[0] = 0
for currentIndex in range(1, N):
  minimumCost[currentIndex] = min(minimumCost[previousIndex] + abs(h[currentIndex] - h[previousIndex]) for previousIndex in range(max(currentIndex - K, 0), currentIndex))

print(minimumCost[N - 1])


### FIXED CODE ###

def solve():
  N, K = [int(i) for i in input().split()]
  H = [int(i) for i in input().split()]
  dp = [0] * N

  for i in range(1, N):
    dp[i] = min(dp[j] + abs(H[i] - H[j]) for j in range(max(i - K, 0), i))

  return dp[N - 1]

print(solve())
### BUGGY CODE ###

s = input()
 
MOD = 2019
d = [0]*MOD
d[0] = 1
r = 0
t = 1
for i in reversed(s):
    r += int(i)*t
    r %= MOD
    t *= 10
    #t %= MOD
    d[r] += 1
    #print (r)
    
print(sum(i*(i-1)//2 for i in d))

### FIXED CODE ###

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10**7)
INF = 10**10

N = 2019
cnt = [0] * N
#print (cnt)

def dec(cnt,s):
    new = [0] * N
    for n in range(N):
        idx = (10 * n + s) % N
        new[idx] += cnt[n]
    return new


S = input()[:-1]
ans = 0
for s in S:
    s = int(s)
    cnt = dec(cnt,s)
    cnt[s] += 1
    ans += cnt[0]
    # if cnt[0] != 0:
    #     print (cnt[0])
print (ans)
### BUGGY CODE ###

div = 10**9 + 7
ans = 0

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

for i in range(N):
    for j in range(i,N):
        #print(str(i) + " : " + str(j))
        ans += A[i]^A[j]

#print(ans)
print(ans%div)


### FIXED CODE ###

div = 10**9 + 7
ans = 0

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

#最大値
A_max = max(A)
#最大値を２進数化
A_max_bin = format(A_max, 'b')
#その桁数
max_digits = len(A_max_bin)

#print(max_digits)

input_format = '0' + str(max_digits) + 'b'

A_bin = [ format(item,input_format) for item in A]

#print(A_bin)

ans = 0

for i in range(1,max_digits+1):
    num0 = 0
    num1 = 0
    #print("桁数 : " + str(i))
    for A_i in A_bin:

        #print(str(A_i) + " : " + str(A_i[-i]))
        #i桁目が0だったら

        #print(type(A_i[-1]))

        if A_i[-i] == '0':
            num0 += 1
        else:
            num1 += 1

    ans += num0 * num1 * 2**(i-1)
    #print(ans)

    num0 = 0
    num1 = 0

#print(ans)
print(ans%div)
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
dp = []
for i in range(N):
  L = [0]*(K+1)
  dp.append(L)
for i in range(A[0]+1):
  dp[0][i] = 1
for i in range(1,N):
  cur = [0]*(K+2)
  for j in range(K+1):
    cur[j+1] = (cur[j]+dp[i-1][j])%(10**9+7)
  for k in range(K+1):
    if k > A[i]:
      dp[i][k] = cur[k+1]-cur[k-A[i]]
    else:
      dp[i][k] = cur[k+1]
print(dp[N-1][K]%(10**9+7))

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
dp = []
for i in range(N):
  L = [0]*(K+1)
  dp.append(L)
for i in range(A[0]+1):
  dp[0][i] = 1
for i in range(1,N):
  cur = [0]*(K+2)
  for j in range(K+1):
    cur[j+1] = (cur[j]+dp[i-1][j])%(10**9+7)
  for k in range(K+1):
    if k > A[i]:
      dp[i][k] = cur[k+1]-cur[k-A[i]]
    else:
      dp[i][k] = cur[k+1]
print(dp[N-1][K]%(10**9+7))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

class HashTable(list):
    def __init__(self, length):
        list.__init__(self)
        self.length = length
        self[:] = [None] * length

    def h1(self, key):
        return key % self.length

    def h2(self, key):
        return 1 + (key % (self.length - 1))

    def h(self, key, i):
        return (self.h1(key) + i*self.h2(key)) % self.length

    def insert(self, key):
        i = 0
        while True:
            j = self.h(key, i)
            if self[j] is None:
                self[j] = key
                return j
            else:
                i += 1
    
    def search(self, key):
        i = 0
        while True:
            j = self.h(key, i)
            if self[j] == key:
                return j
            elif self[j] is None or i >= self.length:
                return None
            else:
                i += 1

def getNum(char):
    char2num = str.maketrans("ACGT", "1234")
    return int(char.translate(char2num))

if __name__ == '__main__':

    n = int(input())
    T = HashTable(n)
    C = map(lambda x:(x[0], getNum(x[1])), [input().split(" ") for i in range(n)])
    
    for command, num in C:
        if command == "insert":
            T.insert(num)
        else:
            if T.search(num) is None:
                print("no")
            else:
                print("yes")



### FIXED CODE ###

# -*- coding: utf-8 -*-

class HashTable(list):
    def __init__(self, length):
        list.__init__(self)
        self.length = length
        self[:] = [None] * length

    def h(self, key, i):
        h1 = key % self.length
        h2 = 1 + (key % (self.length - 1))
        return (h1 + i*h2) % self.length

    def insert(self, key):
        i = 0
        while True:
            h1 = key % self.length
            h2 = 1 + (key % (self.length - 1))
            j = (h1 + i*h2) % self.length
            #j = self.h(key, i)
            if self[j] is None:
                self[j] = key
                return j
            else:
                i += 1
    
    def search(self, key):
        i = 0
        while True:
            h1 = key % self.length
            h2 = 1 + (key % (self.length - 1))
            j = (h1 + i*h2) % self.length
            #j = self.h(key, i)
            if self[j] == key:
                return j
            elif self[j] is None or i >= self.length:
                return None
            else:
                i += 1

def getNum(char):
    char2num = str.maketrans("ACGT", "1234")
    return int(char.translate(char2num), 5)

if __name__ == '__main__':

    n = int(input())
    T = HashTable(1046527)
    C = [input().split(" ") for i in range(n)]
    
    for command, char in C:
        num = getNum(char)
        if command[0] == "i":
            T.insert(num)
        else:
            if T.search(num) is None:
                print("no")
            else:
                print("yes")
### BUGGY CODE ###

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

mod=10**9+7
sum=0
for i in range(N-1):
    for j in range(i+1,N):
       sum+=(A[i]%mod)*(A[j]%mod)
else:
    sum=sum%mod

print(sum)

### FIXED CODE ###

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

mod=10**9+7

B=[0]
for i in range(1,N+1):
    B.append(A[i-1]+B[i-1])

ans=0
for i in range(N-1):
    ans+=A[i]*(B[N]-B[i+1])
    ans%=mod

print(int(ans))