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

import itertools


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

ans = 0
for i in range(2, N):
    if tuple([1, i]) in AB and tuple([i, N]) in AB:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')


### FIXED CODE ###

n, m = map(int, input().split())
sa = set()
sb = set()
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        sb.add(b)
    if b == n:
        sa.add(a)

print('POSSIBLE' if len(sa&sb) != 0 else 'IMPOSSIBLE')
### BUGGY CODE ###

def distances(tree: list, treeSize: int, root: int)->list:
    dists = [0] * treeSize

    q = [(root, -1, 0)]

    while len(q) > 0:
        v, prev, d2v = q[0]
        q = q[1:]

        dists[v] = d2v
        for u, dv2u in tree[v]:
            if prev == u:
                continue
            q.append((u, v, d2v + dv2u))

    return dists


def transit_tree_path(
        N: int, edges: list, Q: int, K: int, queries: list)->list:
    tree = [[] for _ in range(N)]
    for u, v, c in edges:
        tree[u-1].append((v-1, c))
        tree[v-1].append((u-1, c))

    d = distances(tree, N, K-1)

    return [d[x-1]+d[y-1] for x, y in queries]


if __name__ == "__main__":
    N = int(input())
    edges = [tuple(map(int, input().split())) for _ in range(N-1)]
    Q = 0
    Q, K = map(int, input().split())
    queries = [tuple(map(int, input().split())) for _ in range(Q)]

    ans = transit_tree_path(N, edges, Q, K, queries)
    for a in ans:
        print(a)


### FIXED CODE ###

from queue import Queue


def distances(tree: list, treeSize: int, root: int)->list:
    dists = [0] * treeSize

    q = Queue()
    q.put((root, -1, 0))

    while not q.empty():
        v, prev, d2v = q.get()

        dists[v] = d2v
        for u, dv2u in tree[v]:
            if prev == u:
                continue
            q.put((u, v, d2v + dv2u))

    return dists


def transit_tree_path(
        N: int, edges: list, Q: int, K: int, queries: list)->list:
    tree = [[] for _ in range(N)]
    for u, v, c in edges:
        tree[u-1].append((v-1, c))
        tree[v-1].append((u-1, c))

    d = distances(tree, N, K-1)

    return [d[x-1]+d[y-1] for x, y in queries]


if __name__ == "__main__":
    N = int(input())
    edges = [tuple(map(int, input().split())) for _ in range(N-1)]
    Q = 0
    Q, K = map(int, input().split())
    queries = [tuple(map(int, input().split())) for _ in range(Q)]

    ans = transit_tree_path(N, edges, Q, K, queries)
    for a in ans:
        print(a)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(5000)
input = sys.stdin.readline

TIME = 0
VAL = 1

N, T = [int(a) for a in input().split()]
time_value = [(-1, -1)]
for i in range(1, N + 1):
    time_value.append(tuple(int(a) for a in input().split()))

# Sort the array in the increasing order of value
time_value.sort(key = lambda x:x[VAL])


# table for knapsack problem
# maximum possible time is T-1
dp_table = {}

def knapsack(n, t):
    '''
    Input: n ... the number of elements to choose from
                 n means items 1, 2, ..., n can be chosen
           t ... time limit
    Output: total value
    '''
    if n <= 0 or t <= 0:
        return 0
    elif (n, t) in dp_table:
        return dp_table[(n, t)]
    elif time_value[n][TIME] > t:
        ans = knapsack(n - 1, t)
    else:
        ans = max(knapsack(n - 1, t),
                  time_value[n][VAL] + knapsack(n - 1, t - time_value[n][TIME]))

    dp_table[(n, t)] = ans
    return ans

def all_you_can_eat(N, T):
    val_acum = time_value[N][VAL]
    t = T - 1
    max_val = val_acum + knapsack(N - 1, t)

    for n in range(N - 1, 0, -1):  # food to eat at the end
        val_acum += time_value[n][VAL] # value[N] + value[N-1] + ... + value[n]
        t -= time_value[n + 1][TIME] # T - 1 - (time[N] + time[N-1] + ... + time[n + 1])
        if t < 0: break
        tmp = val_acum + knapsack(n - 1, t)
        max_val = max(max_val, tmp)

    return max_val

print(all_you_can_eat(N, T))


### FIXED CODE ###

import sys
from operator import itemgetter

sys.setrecursionlimit(5000)
input = sys.stdin.readline


TIME = 0
VAL = 1

N, T = [int(a) for a in input().split()]
time_value = [None] * (N + 1)
time_value[0] = (-1, -1)
for i in range(1, N + 1):
    time_value[i] = tuple(int(a) for a in input().split())

# Sort the array in the increasing order of value
time_value.sort(key = itemgetter(VAL))


# T by (N + 1) table for knapsack problem
# maximum possible time is T-1
dp_table = [[-1] * T for _ in range(N + 1)]

# Fill in dp_table i.e. solve knapsack problem
for t in range(0, T):
    dp_table[0][t] = 0

for n in range(1, N + 1):
    dp_table[n][0] = 0
    for t in range(1, T):
        if time_value[n][TIME] > t:
            dp_table[n][t] = dp_table[n - 1][t]
        else:
            dp_table[n][t] = max(dp_table[n - 1][t],
                             time_value[n][VAL] + dp_table[n - 1][t - time_value[n][TIME]])


val_acum = time_value[N][VAL]
t = T - 1
max_val = val_acum + dp_table[N - 1][t]

for n in range(N - 1, 0, -1):  # food to eat at the end
    val_acum += time_value[n][VAL] # value[N] + value[N-1] + ... + value[n]
    t -= time_value[n + 1][TIME] # T - 1 - (time[N] + time[N-1] + ... + time[n + 1])
    if t < 0: break
    tmp = val_acum + dp_table[n - 1][t]
    max_val = max(max_val, tmp)

print(max_val)
### BUGGY CODE ###

l, r = map(int, input().split())

m = 2019
mod_min = m

for j in range(l,r+1,1):
    #j_ = j % m
    #if j_ == 0:
        #break
    for i in range(l,j,1):
        #i_ = i % m
        i_j = (i * j) % m
        
        if i_j < mod_min:
            mod_min = i_j
            
        if i_j == 0:
            break
            
print(mod_min)

### FIXED CODE ###

l, r = map(int, input().split())

m = 2019
mod_min = m

is_return = False

for j in range(l,r+1,1):
    #j_ = j % m
    #if j_ == 0:
        #break
        
    if is_return:
        break
    for i in range(l,j,1):
        #i_ = i % m
        i_j = (i * j) % m
        
        if i_j < mod_min:
            mod_min = i_j
            
        if i_j == 0:
            is_return = True
            break
            
print(mod_min)
### BUGGY CODE ###

import sys

K = int(input())

seven = 7
for i in range(10**7):
    if seven % K == 0:
        print(i+1)
        sys.exit()
    else:
        seven = seven * 10 + 7

print(-1)

### FIXED CODE ###

import sys

K = int(input())

seven = 7
mod = 7 % K
for i in range(10**6):
    seven = seven % K
    if seven == 0:
        print(i+1)
        sys.exit()
    else:
        seven = seven * (10 % K) + mod

print(-1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Dec 30 21:52:40 2017

@author: kanako_note
"""

N = int(input())

C = [0] * (N-1)
S = [0] * (N-1)
F = [0] * (N-1)

for i in range(N-1):
    C[i], S[i], F[i] = map(int, input().split())

for start in range(N-2):
    next = start + 1
    reach = S[start] + C[start]
    while(next < N-1):
        temp = S[next]
        while(1):
            if temp >= reach:
                leave = temp
                break
            temp += F[next]
        reach = leave + C[next]
        next += 1
    print(reach)
    
print(S[-1]+ C[-1])
print(0)


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Dec 31 12:25:16 2017

@author: kanako_note
"""

N = int(input())

C = [0] * (N-1)
S = [0] * (N-1)
F = [0] * (N-1)

for i in range(N-1):
    C[i], S[i], F[i] = map(int, input().split())

for i in range(N):
    t = 0
    for j in range(i, N-1):
        if t<S[j]:  t = S[j]
        elif t%F[j]==0: pass
        else:   t = t+F[j]-t%F[j]
        t += C[j]
    print(t)
### BUGGY CODE ###

import bisect
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
BC = []
for _ in range(M):
  B,C = map(int,input().split())
  BC.append((B,C))
BC.sort(key=lambda x: x[1], reverse=True)
for i in BC:
  b,c = i[0],i[1]
  index = bisect.bisect_left(A,c)
  index = min(index,b)
  if index==0:
    continue
  for j in range(index):
    A[j] = c
  A.sort()
print(sum(A))

### FIXED CODE ###

import bisect
N,M = map(int,input().split())
A = list(map(int,input().split()))
D = []
for _ in range(M):
  D.append(list(map(int,input().split())))
D.sort(key=lambda x:x[1], reverse=True)
cnt = 0
ans = []
for d in D:
  b,c = d[0],d[1]
  ans += [c for _ in range(b)]
  cnt += b
  if cnt>=N:
    break
ans = ans[:min(cnt,N)] + A
ans.sort(reverse=True)
print(sum(ans[:N]))
### BUGGY CODE ###

import sys
from collections import deque

def input():
    return sys.stdin.readline().strip()

def main():
    H,W = map(int,input().split())
    S = [list(input()) for _ in range(H)]
    dp = [[float('inf') for _ in range(W)] for _ in range(H)]

    def bfs(x,y):
        que = deque()
        que.append((x,y))
        if S[y][x] == '.':
            dp[y][x] = 0
        else:
            dp[y][x] = 1
        while que.__len__():
            x,y = que.popleft()
            for dx,dy in ((1,0),(0,1)):
                sx = x + dx
                sy = y + dy
                if sx >= W or sy >= H:
                    continue
                if S[y][x] == '.' and S[sy][sx] == '#':
                    tmp = 1
                else:
                    tmp = 0
                dp[sy][sx] = min(dp[y][x]+tmp,dp[sy][sx])
                que.append((sx,sy))
    bfs(0,0)
    print(dp[H-1][W-1])
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from collections import deque

def input():
    return sys.stdin.readline().strip()

def main():
    H,W = map(int,input().split())
    S = [list(input()) for _ in range(H)]
    dp = [[float('inf') for _ in range(W)] for _ in range(H)]

    def bfs(x,y):
        que = deque()
        que.append((x,y))
        if S[y][x] == '.':
            dp[y][x] = 0
        else:
            dp[y][x] = 1
        while que.__len__():
            x,y = que.popleft()
            for dx,dy in ((1,0),(0,1)):
                sx = x + dx
                sy = y + dy
                if sx == W or sy == H:
                    continue
                if S[y][x] == '.' and S[sy][sx] == '#':
                    tmp = 1
                else:
                    tmp = 0
                dp[sy][sx] = min(dp[y][x]+tmp,dp[sy][sx])
                if (sx,sy) not in que:
                    que.append((sx,sy))
    bfs(0,0)
    print(dp[H-1][W-1])
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    i1_sub=n-i1
    for l1 in range(i1_sub,1,-1):
        for i2 in range(n):
            i2_sub=n-i2
            for l2 in range(i2_sub,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    s=(x_sub2-x_sub1)*(y_sub2-y_sub1)
                    if s<ans:
                        ans=s
                else:
                    break
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(n):
  a = i + 1
  for j in range(n):
    b = j + 1
    c = n - a * b
    if c <= 0:
      break
    ans += 1
print(ans)

### FIXED CODE ###

import math
n = int(input())
ans = 0
for i in range(n):
  a = i + 1
  b = 1
  c = n - a * b
  ans += math.ceil(c / a)
print(ans)
### BUGGY CODE ###

n=int(input())
lamp = [int(input()) for i in range(n)]
lst = []
cnt = 0
select = lamp[0]
while True:
  if select in lst:
    print(-1)
    break;
  elif select == 2:
    cnt += 1
    print(cnt)
    break;
  else:
    lst.append(select)
    select = lamp[select-1]
    cnt += 1

### FIXED CODE ###

n=int(input())
lamp = [int(input()) for i in range(n)]
cnt = 0
select = lamp[0]
while True:
  if cnt>n:
    print(-1)
    break;
  elif select == 2:
    cnt += 1
    print(cnt)
    break;
  else:
    select = lamp[select-1]
    cnt += 1
### BUGGY CODE ###

N = int(input())

l = []
for _ in range(N):
    a = int(input())
    if a in l:
        l.remove(a)
    else:
        l.append(a)
print(len(l))

### FIXED CODE ###

N = int(input())

l = set([])
for _ in range(N):
    a = int(input())
    if a in l:
        l.remove(a)
    else:
        l.add(a)
print(len(l))
### BUGGY CODE ###

import bisect
import itertools
s = input()
K = int(input())
table = []
for i, j in itertools.combinations(range(len(s) + 1), 2):
    index = bisect.bisect_left(table, s[i:j])
    if len(table) == index:
        table += [s[i:j]]
    elif table[index] != s[i:j]:
        bisect.insort_left(table, s[i:j])
print(table[K - 1])

### FIXED CODE ###

import itertools
s = input()
K = int(input())
dp = []

def substr(x):
    table = {}
    for i, j in itertools.combinations(range(len(x) + 1), 2):
        table[x[i:j]] = 1
    return sorted(table.keys())[:5]

dp = []

if len(s) < 6:
    dp = substr(s)
else:
    dp = substr(s[-5:])
    for i in range(-6, -len(s) -1, -1):
        for j in range(1, 6):
            if not s[i : i + j] in dp:
                dp = sorted(dp + [s[i : i + j]])[:5]
print(dp[K - 1])
### BUGGY CODE ###

n,m=map(int,input().split())
flag=False
one = []
enu = []
for i in range(m):
  a,b=map(int,input().split())
  if a==1:
    one.append(b)
  elif b==n:
    enu.append(a)

for i in one:
  if i in enu:
    flag=True

if flag: print('POSSIBLE')
else: print('IMPOSSIBLE')

### FIXED CODE ###

n,m=map(int,input().split())
li = []
for i in range(m):
  a,b=map(int,input().split())
  if a==1:
    li.append(b)
  elif b==n:
    li.append(a)

if len(set(li))==len(li): print('IMPOSSIBLE')
else: print('POSSIBLE')
### BUGGY CODE ###

from collections import deque

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

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs(sx, sy):
    s = [[-1] * W for _ in range(H)]
    d = [[0] * W for _ in range(H)]

    que = deque([])
    que.append((sx, sy))
    s[sy][sx] = 1

    res = 0
    while que:
        x, y = que.popleft()
        s[y][x] = 1

        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]

            if 0 <= nx < W and 0 <= ny < H and s[ny][nx] == -1 and c[ny][nx] == '.':
                que.append((nx, ny))
                d[ny][nx] = d[y][x] + 1
                res = max(res, d[ny][nx])

    return res

ans = 0
for i in range(H):
    for j in range(W):
        if c[i][j] == '.':
            tmp = bfs(j, i)
            ans = max(ans, tmp)

print(ans)


### FIXED CODE ###

from collections import deque

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

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs(sx, sy):
    d = [[-1] * W for _ in range(H)]

    que = deque([])
    que.append((sx, sy))
    d[sy][sx] = 0

    res = 0
    while que:
        x, y = que.popleft()

        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]

            if 0 <= nx < W and 0 <= ny < H and d[ny][nx] == -1 and c[ny][nx] == '.':
                que.append((nx, ny))
                tmp = d[y][x] + 1
                d[ny][nx] = tmp
                res = max(res, tmp)

    return res

ans = 0
for i in range(H):
    for j in range(W):
        if c[i][j] == '.':
            tmp = bfs(j, i)
            ans = max(ans, tmp)

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

from bisect import bisect
N = int(input())
sides = sorted(map(int, input().split()))
print(sum(sum(N - j - bisect(sides, sides[-i] - sides[-j], hi=N-j) for j in range(i + 1, N + 1)) for i in range(1, N - 1)))


### FIXED CODE ###

from bisect import bisect
N = int(input())
sides = sorted(map(int, input().split()))

ans = 0
for i in range(1, N - 1):
    for j in range(i + 1, N + 1):
        ans += N - j - bisect(sides, sides[-i] - sides[-j], hi=N-j)
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
k = min(n - 1, k)
h = [0] + list(map(int, input().split())) + [0 for _ in range(k - 2)]
cost = [0 for _ in range(n + 1)]
for i in range(2, n + 1):
    cost_i = []
    for di in range(1, k + 1):
        cost_i += [cost[i - di] + abs(h[i] - h[i - di])]
    cost[i] = min(cost_i)

print(cost[n])


### FIXED CODE ###

n, k = map(int, input().split())
k = min(n - 1, k)
h = list(map(int, input().split()))
cost = [0 for _ in range(n)]
for i, hi in enumerate(h):
    if i == 0: continue
    st = i - k if i > k else 0
    cost[i] = min([ck + abs(hi - hk) for ck, hk in zip(cost[st:i], h[st:i])])
print(cost[-1])
### BUGGY CODE ###

import math
n=int(input())
a=list(map(int,input().split()))
s=[0 for _ in range(30)]
p=[]
for j in range(30):
  p.append(pow(2,j))
for i in range(n):
  for j in range(30):
    s[j]=(s[j]+(a[i]//p[j]%2))
for i in range(n):
  ans=0
  for j in range(30):
    ans=ans+p[j]*((a[i]//p[j]+s[j])%2)
  print(ans,end=" ")


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
p=[]
for j in range(30):
  p.append(pow(2,j))
t=0
for i in range(n):
  t=t^a[i]
for i in range(n):
  ans=0
  for j in range(30):
    ans=ans+p[j]*(((a[i]^t)//p[j])%2)
  print(ans,end=" ")
### BUGGY CODE ###

import numpy as np

n, m = map(int, input().split())
a = [0 for i in range(m)]
b = [0 for i in range(m)]
c = []
for i in range(m):
    a[i], b[i] = map(int, input().split())
    c.append(list(map(int, input().split())))

dp = [[np.inf for i in range(2**n)] for j in range(m)]
for i in range(m):
    dp[i][0] = 0

string = [0 for i in range(n)]
for i in c[0]:
    string[i-1] = 1
string = ''.join(map(str, string))
num = int(string, 2)
dp[0][num] = a[0]

for i in range(1, m):
    string = [0 for i in range(n)]
    for j in c[i]:
        string[j-1] = 1
    string = ''.join(map(str, string))
    di = int(string, 2)
    for j in range(2**n):
        dp[i][j|di] = min(dp[i][j|di], dp[i-1][j|di], dp[i-1][j]+a[i])
    for j in range(2**n):
        if dp[i][j] == np.inf and dp[i-1][j] != np.inf:
            dp[i][j] = dp[i-1][j]

if dp[m-1][2**n-1] != np.inf:
    print(dp[m-1][2**n-1])
else:
    print(-1)

### FIXED CODE ###

n, m = map(int, input().split())
a = [0 for i in range(m)]
b = [0 for i in range(m)]
c = []
for i in range(m):
    a[i], b[i] = map(int, input().split())
    c.append(list(map(int, input().split())))

dp = [10**6 for i in range(2**n)]
dp[0] = 0

string = [0 for i in range(n)]
for i in c[0]:
    string[i-1] = 1
string = ''.join(map(str, string))
num = int(string, 2)
dp[num] = a[0]

for i in range(1, m):
    string = [0 for i in range(n)]
    for j in c[i]:
        string[j-1] = 1
    string = ''.join(map(str, string))
    di = int(string, 2)
    for j in range(2**n):
        dp[j|di] = min(dp[j|di], dp[j]+a[i])

if dp[2**n-1] != 10**6:
    print(dp[2**n-1])
else:
    print(-1)
### BUGGY CODE ###

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

import sys
import numpy as np

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, K = MAP()
A = LIST()

# dp[この子までの範囲で][飴を配る総数] = 場合の数
dp = np.zeros((N+1, K+1), dtype=np.int64)
# 0番目まで(誰もいない)の範囲で0個配る場合の数は1通り
dp[0,0] = 1

for i, a in enumerate(A):
    for k in range(a+1):
        # k個配る場合をまとめて遷移
        dp[i+1,k:K+1] += dp[i,:K+1-k]
        dp[i+1,k:K+1] %= MOD

print(dp[N][K])


### FIXED CODE ###

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

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, K = MAP()
aN = LIST()

# dp[この子までの範囲で][飴を配る総数] = 場合の数
dp = [[0] * (K+1) for i in range(N+1)]
# 0番目まで(誰もいない)の範囲で0個配る場合の数は1通り
dp[0][0] = 1

for i in range(N):
    sm = [0] * (K+2)
    # 今回送るi行について累積和を取る
    for j in range(1, K+2):
        sm[j] = sm[j-1] + dp[i][j-1]
        sm[j] %= MOD
    for j in range(K+1):
        # iが送る予定の長さに応じた区間和を取る
        dp[i+1][j] = sm[j+1] - sm[max(j-aN[i], 0)]
        dp[i+1][j] %= MOD
        # for k in range(aN[i]+1):
        #     dp[i+1][j+k] += dp[i][j]
print(dp[N][K])
### BUGGY CODE ###

from sys import stdin

n = int(stdin.readline().rstrip())
li = list(map(int,stdin.readline().rstrip().split()))

from itertools import combinations
lin = list(combinations(li, 3))

point = 0
for i in range(len(lin)):
    if lin[i][0] < (lin[i][1] + lin[i][2]) and lin[i][1] < (lin[i][2] + lin[i][0]) and lin[i][2] < (lin[i][1] + lin[i][0]):
        point += 1
print(point)

### FIXED CODE ###

from sys import stdin
import bisect

n = int(stdin.readline().rstrip())
li = list(map(int,stdin.readline().rstrip().split()))

li.sort()

point = 0

for i in range(n-2):
    for j in range(i+1,n-1):
        bi = bisect.bisect_left(li,li[i]+li[j])
        point += bi-j-1
print(point)