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

def count_section_by_zero(data):
  count = 0
  flg = False
  start = 0
  for i, d in enumerate(data):
    if flg is False and d != 0:
      count += 1
      flg = True
      
    if d == 0:
      flg = False
  return count

def input_list():
  return list(map(int, input().split()))

def input_list_str():
  return list(map(str, input().split()))

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

# 2で割り切れる回数
def divide_two(arg):
  c = 0
  while True:
    if c >= 2:
      break
    if arg % 2 != 0:
      break
    arg //= 2
    c += 1
  return c

# 素因数分解
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def main():
  n = int(input())
  if n < 4:
    print(0)
    exit()
  ans = 0
  s = list(input())
  for i, a in enumerate(s):
    j = i+1
    k = i+2
    for bi, b in enumerate(s):
      if bi < j:
        continue
      for ci, c in enumerate(s):
        if ci < k:
          continue
        if i > j:
          continue
        if j > k:
          continue
        if i < bi < ci:
          if a == b or b == c or a == c:
            continue
          if bi - i == ci - bi:
            continue
          ans += 1
  print(ans)          
import math
import fractions
import collections
import itertools
from functools import reduce
main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect


# 持っているビスケットを叩き、1枚増やす
# ビスケット A枚を 1円に交換する
# 1円をビスケット B枚に交換する
def main():
    n = int(input())
    s = input()
    R, G, B = [], [], []
    for i in range(n):
        index = i+1
        if s[i] == "R":
            R.append(index)
        elif s[i] == "G":
            G.append(index)
        elif s[i] == "B":
            B.append(index)
    all_count = len(R)*len(G)*len(B)
    count = 0
    # j - i != k - j
    # k = 2j - i
    for i in range(n):
        for j in range(i+1, n):
            if s[i] == s[j]:
                continue
            k = 2*j - i
            if k >= n:
                continue
            if s[k] == s[i] or s[k] == s[j]:
                continue
            count += 1
    print(all_count - count)

def bi(num, a, b, x):
    print((a * num) + (b * len(str(b))))
    if (a * num) + (b * len(str(b))) <= x:
        return False
    return True

def input_list():
    return list(map(int, input().split()))


def input_list_str():
    return list(map(str, input().split()))


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

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

for i in range(n):
    b=a[:]
    del b[i]
    print(max(b))


### FIXED CODE ###

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

res=max(a)
ans=[res]*n
s=[i for i, x in enumerate(a) if x ==res]
a.sort()
res2=a[-2]
for i in s:
    ans[i]=res2
for i in range(n):
    print(ans[i])
### BUGGY CODE ###

order = list(input())
X, Y = map(int, input().split())
lis = []
now = 0
import sys
sys.setrecursionlimit(4100000)
from functools import lru_cache
for s in order:
    if s=='T':
        now = 0
        lis.append(0)
    else:
        if now:
            lis[-1] += 1
        else:
            lis.append(1)
            now = 1

N = len(lis)
dirc = ((0, 1), (1, 0), (0, -1), (-1, 0))
@lru_cache(maxsize=1000)
def dfs(idx, v, d):
    x, y = v
    if idx==N:
        if x==X and y==Y:
            return 1
        else:
            return 0
    ret = 0
    if lis[idx]==0:
        if d==0:
            nd = [1, 3]
        elif d==3:
            nd = [0, 2]
        else:
            nd = [d-1, d+1]
        for i in nd:
            ret += dfs(idx+1, v, i)
    else:
        num = lis[idx]
        dx, dy = dirc[d]
        ret += dfs(idx+1, (x+dx*num, y+dy*num), d)
    return ret

if dfs(0, (0, 0), 1):
    print('Yes')
else:
    print('No')

### FIXED CODE ###

order = list(input())
X, Y = map(int, input().split())
 
Xs = []
Ys = []
cnt = 0
now_lis = Xs
x_dir = 1
for s in order:
    if s=='T':
        if not cnt==0:
            now_lis.append(cnt)
        now_lis = Ys if x_dir else Xs
        x_dir = not x_dir
        cnt = 0
    else:
        cnt += 1
if not cnt==0:
    now_lis.append(cnt)

if order[0]=='T':
    x_start = 0
else:
    x_start = Xs[0]
    del Xs[0]

def dp(start, lis, goal):
    nodes = set([start])
    for x in lis:
        nx = set()
        L = list(nodes)
        for l in L:
            nx.add(l+x)
            nx.add(l-x)
        nodes = nx
    return goal in nodes
 
if dp(x_start, Xs, X) and dp(0, Ys, Y):
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

import math
import numpy as np
N,K=map(int,input().split())
a=[0]*N
a=list(map(int,input().split()))
A=np.array(a)
b=np.zeros(N)
for i in range(K):
    b=np.zeros(N)
    for j in range(N):

        minmin=max(0,math.ceil(j-A[j]-0.5))

        maxmax=min(N,math.floor(j+A[j]+0.5)+1)

        if(minmin==maxmax):
            maxmax=maxmax+1
            if(N<=maxmax):
                minmin=N-1
                maxmax=N

        for k in range(minmin,maxmax):
            b[k]=b[k]+1

    A=b
A=A.astype(np.int)
da=list(A)
L=[str(a) for a in da]

da=" ".join(L)
print(da)


### FIXED CODE ###

import math
N,K=map(int,input().split())
A=[0]*N
A=list(map(int,input().split()))

da=[0 for i in range(N)]
for k in range(K):
    B=[0 for i in range(N)]
    for i in range(N):
        l=max(0,i-A[i])
        r=min(N-1,i+A[i])
        B[l]=B[l]+1
        if(r+1<N):
            B[r+1]=B[r+1]-1
    for i in range(1,N):
        B[i]=min(N,B[i]+B[i-1])
    if(A==B):
        break
    A=B
b=[str(i) for i in B]
b=" ".join(b)
print(b)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))
a=sorted(a)
f=sorted(f,reverse=True)


def is_lessthanK(X):
  ans=0
  for i in range(n):
    if a[i]*f[i]>X:
      ans+=a[i]-X//f[i]
    if ans > k:
      return False
  return True


ng=-1
ok=a[-1]*f[0]
while ok-ng>1:
  mid=(ok+ng)//2
  if is_lessthanK(mid):
    ok=mid
  else:
    ng=mid
print(ok)



### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))
a=sorted(a)
f=sorted(f,reverse=True)


def is_lessthanK(X):
  ans=0
  for A,F in zip(a,f):
    if A*F>X:
      ans+=A-X//F
    if ans > k:
      return False
  return True


ng=-1
ok=a[-1]*f[0]
while ok-ng>1:
  mid=(ok+ng)//2
  if is_lessthanK(mid):
    ok=mid
  else:
    ng=mid
print(ok)
### BUGGY CODE ###

h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=w
while b:
 b-=1;r=t=j=0;d=[0]*h
 while w-j:
  i=c=0;j+=1
  while h-i:
   d[c]+=s[i][~j]>'0';c+=b>>i&1;i+=1
   if max(d)>k:d=[0]*h;r+=1;j-=t<j;t=j;i=h
 m+=r+c,
print(min(m))

### FIXED CODE ###

h,*s=open(0)
h,w,k=map(int,h.split())
s=[list(map(int,t[:w]))for t in s]
m=9e9
for i in range(1<<h-1):
  t=[]
  b=v=l=0
  for j in range(h):
    if i>>j&1:
      t+=s[b:j+1],
      b=j+1
      l+=1
  t+=s[b:],
  l+=1
  c=[0]*l
  for i in range(w):
    f=g=0
    u=[]
    for j in range(l):
      d=sum(t[i]for t in t[j])
      u+=d,
      if d>k:
        g=1
        break
      c[j]+=d
      f|=c[j]>k
    else:
      v+=f
      if f:c=u
    if g:break
  else:m=min(m,v+l-1)
print(m)
### BUGGY CODE ###

n = int(input())
s = input()

s_list = list(s)

ans = 300001
for i in range(n):
    people = s_list[:i].count('W') + s_list[i+1:].count('E')
    if ans > people:
        ans = people

print(ans)


### FIXED CODE ###

'''
制約
2 ≤ N ≤ 3×10^5(300,000)

入力例 3
8
WWWWWEEE

出力例 3
3

考え方：
Eを0, Wを1と置くと、
0000000X11111111 と並ぶようにすればよい。
そのために、値を変える数が最小になるリーダーの位置を調べればよい

-> 左端のW(West), 右端のE(East)はほぼ必ず向きを変える必要がある。


A. 全パターン試す
ある地点より左のWの数 + 右のEの数　の合計が最小になるパターンを求める（文字一致でカウント）
-> TLE

B. 全パターン
str.count('W')でやる
-> TLE

C. 「累積和」(cumulative sum)というアルゴリズムを使わないと解けない問題。学習して、使う！


'''

# from collections import deque # キュー、スタックに利用

# sys.stdin.readline() # 標準入力の高速化に利用
import sys
input = sys.stdin.readline

is_debug = False


def main():
    '''メイン処理'''
    n = int(input())
    sss = input()

    s_list = list(sss)

    W_sums = [0] * n # 累積和を入れるリスト
    E_sums = [0] * n # 累積和を入れるリスト
    W_sum = 0 # 左端から数えて、向きを変える必要のあるWの数
    E_sum = 0 # 右端から数えて、向きを変える必要のあるWの数
    
    if is_debug:
        print(W_sums)
    
    for i in range(n):
        if s_list[i] == 'W':
            W_sum += 1
        W_sums[i] = W_sum
        if s_list[n-i] == 'E':
            E_sum += 1
        E_sums[(n-1)-i] = E_sum

    if is_debug:
        print(W_sums)
        print(E_sums)
    
    # W_sums, E_sumsを用いて、向きを変える人数が最小となる値を見つける
    min_cost = float('inf')
    for i in range(n):
        # Wを振り向かせる人数
        if i == 0:
            W_cost = 0
        else:
            W_cost = W_sums[i-1]
        # Eを振り向かせる人数
        if i == n-1:
            E_cost = 0
        else:
            E_cost = E_sums[(i-1)+1]

        if is_debug:
            print(i, W_cost, E_cost)

        cost = W_cost+E_cost
        if cost < min_cost:
            min_cost = cost
    
    print(min_cost)

if __name__ == "__main__":
    # ファイル実行時に、main()関数を実行
    main()
### BUGGY CODE ###

def examE():
    N, T = LI()
    A, B = [0] * N, [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())
    maxT = max(A)
    dp = [[[0 for _ in range(2)] for _ in range(T+ 1)] for _ in range(N + 1)]
    for i in range(N):
        for j in range(T+ 1):
            if j>=1:
                dp[i+1][j][1] = max(dp[i+1][j][1], dp[i][j-1][0] + B[i])
            if A[i] <= j:
                dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j - A[i]][0] + B[i])
                dp[i + 1][j][1] = max(dp[i + 1][j][1], dp[i][j - A[i]][1] + B[i])
            dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j][0])
            dp[i + 1][j][1] = max(dp[i + 1][j][1], dp[i][j][1])

#    print(dp[N][T])
    ans = max(dp[N][T])
    print(ans)

import sys,copy,bisect,itertools
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examE()


### FIXED CODE ###

def examE():
    N, T = LI()
    A, B = [0] * N, [0] * N
    for i in range(N):
        A[i], B[i] = LI()
    dp = [[0 for _ in range(T+ 1)] for _ in range(N + 1)]
    dp2 = [[0 for _ in range(T+ 1)] for _ in range(N + 1)]
    for i in range(N):
        for j in range(A[i],T+1):
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - A[i]] + B[i])
            dp2[i + 1][j] = max(dp2[i + 1][j], dp2[i][j - A[i]] + B[i])
        for j in range(1,T+1):
            dp2[i+1][j] = max(dp2[i+1][j], dp[i][j-1] + B[i], dp2[i][j])
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
#    print(dp[N][T])
    ans = dp2[N][T]
    print(ans)

import sys,copy,bisect,itertools
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examE()
### BUGGY CODE ###

import bisect,collections,copy,heapq,itertools,math,numpy,string
#from operator import itemgetter
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
N, M = LI()
AB = [LI() for _ in range(M)]
path = [[] for _ in range(N+1)]
mp = []
ans = [0] * (N+1)

for ab in AB:
	a = ab[0]
	b = ab[1]
	path[a].append(b)
	path[b].append(a)
	#print(a,b)

def bfs(tree, st, endlist, endnum):
	queue = collections.deque()
	queue.append([-1,st])
	endlist[st] -= 1
	now = [-1,-1,-1]
	pre = []
	depth = 0
	histind = -1
	node = -1
	hist = []
	res = []
	allres = []
	while queue:
		pre = now[:]
		now = queue.popleft()
		histind = now[0]
		node = now[1]
		hist.append([histind,node])
		#来たときは絶対に初回
		res = [node]
		ident = histind
		while res[len(res)-1]!=1:
			res.append(hist[ident][1])
			ident = hist[ident][0]
		allres.append(res[::-1])
		endnum -= 1
		if endnum == 0:
			return allres
		for v in path[node]:
			if endlist[v] > 0:
				queue.append([len(hist)-1,v])
				#endlist更新
				endlist[v] -= 1
		continue
	return None

#print_map(path)
result = bfs(path, 1, [1] * (N+1), N)
#print(result)
if result is None:
	print("No")
	exit(0)
print("Yes")
execnum = N-1
maxlen = len(result[len(result)-1])
for i in result[::-1]:
	for ind,v in enumerate(i[::-1]):
		if v == 1:
			break
		if ans[v] == 0:
			ans[v] = i[len(i)-2-ind]
			execnum-=1
			if execnum == 0:
				break

for i in ans[2:]:
	print(i)


### FIXED CODE ###

import bisect,collections,copy,heapq,itertools,math,numpy,string
#from operator import itemgetter
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
N, M = LI()
AB = [LI() for _ in range(M)]
path = [[] for _ in range(N+1)]
mp = []
ans = [0] * (N+1)

for ab in AB:
	a = ab[0]
	b = ab[1]
	path[a].append(b)
	path[b].append(a)
	#print(a,b)

def bfs(tree, st, endlist, endnum):
	queue = collections.deque()
	queue.append([-1,st])
	endlist[st] -= 1
	now = [-1,-1,-1]
	pre = []
	depth = 0
	histind = -1
	node = -1
	hist = []
	res = []
	allres = []
	while queue:
		pre = now[:]
		now = queue.popleft()
		histind = now[0]
		node = now[1]
		hist.append([histind,node])
		#来たときは絶対に初回
		res = [node,hist[histind][1]]
		allres.append(res[::])
		endnum -= 1
		if endnum == 0:
			return allres
		for v in path[node]:
			if endlist[v] > 0:
				queue.append([len(hist)-1,v])
				#endlist更新
				endlist[v] -= 1
		continue
	return None

#print_map(path)
result = bfs(path, 1, [1] * (N+1), N)
#print("[TO, FROM] = {0}".format(result))
if result is None:
	print("No")
	exit(0)
print("Yes")
execnum = N
maxlen = len(result[len(result)-1])
for i in result:
	#print(i)
	if ans[i[0]] == 0:
		ans[i[0]] = i[1]
		execnum-=1
		if execnum == 0:
			break

for i in ans[2:]:
	print(i)
### BUGGY CODE ###

import numpy as np
from numba import njit, i8, u1, void, b1
import heapq

@njit(void(i8,i8,i8,i8,b1[:,:]),cache=True)
def solve(ch,cw,dh,dw,road_map):

    h,w = road_map.shape

    queue = [[0,ch*w+cw]]
    used_map = np.full(h*w,-1,dtype=np.int64)

    #move walk
            
    while used_map[dh*w+dw] == -1 and len(queue) != 0:
        dot = heapq.heappop(queue)
        tl,n = dot[0],dot[1]
        th,tw = divmod(n,w)
        used_map[n] = tl
        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if x == y == 0:
                    continue
                if abs(x)+abs(y) <= 1:
                    loop = tl
                else:
                    loop = tl+1
                tx = th + x
                ty = tw + y
                next_n  = (th+x)*w+tw+y
                if tx < 0 or ty < 0 or tx >= h or ty >= w or road_map[tx][ty] == True:
                    continue
                check = used_map[next_n]
                if check == -1 or check > loop:
                    heapq.heappush(queue,[loop,next_n])

    print(used_map[dh*w+dw])

h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch,cw = ch-1,cw-1
dh,dw = map(int,input().split())
dh,dw = dh-1,dw-1
road_map = np.array([[c=="#" for c in input()] for _ in range(h)])

solve(ch,cw,dh,dw,road_map)



### FIXED CODE ###

#shotoyooさんのコードをお借りしてテスト

import numpy as np
from numba import njit, b1, i4, i8, f8
from heapq import heappop as hpp, heappush as hp

@njit((b1[:, :],i8,i8,i8,i8), cache=True)
def main(ss,ch,cw,dh,dw):
    inf = 1<<30
    h,w = ss.shape
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
    while q:
        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        if pu==goal:
            break
        for xx in range(-2, 3):
            for yy in range(-2, 3):
                if xx==yy==0:
                    continue
                if abs(xx)+abs(yy)<=1:
                    vv = 0
                else:
                    vv = 1
                x,y = ux+xx, uy+yy
                u = x*w + y
                num = pnum+vv
                if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                    continue
        #         print(x,y)
                if seen[u]>num:
                    seen[u] = num
                    hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val
      

h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
ss = np.array([[c=="#" for c in input()] for _ in range(h)])

print(main(ss,ch,cw,dh,dw))
### BUGGY CODE ###

import sys

x = []

for line in sys.stdin.readlines():
    x.append(int(line.strip()))

length = int(x[0])

del x[0]

max = -(10 ** 9)

for i in range(0, length - 1):
    for j in range(i + 1, length):
        sa = int(x[j]) - int(x[i])
        if max < sa:
            max = sa

print max

### FIXED CODE ###

import sys

x = []

for line in sys.stdin.readlines():
    x.append(int(line.strip()))

length = int(x[0])

del x[0]

max = -(10 ** 9)
min =  x[0]

for i in range(1, length):
    sa = x[i] - min

    if sa > max:
        max = sa

    if x[i] < min:
        min = x[i]
   
print max
### BUGGY CODE ###

time = 0
people = int(input())
capacity = []
for i in range(5):
    capacity.append(int(input()))
city = [0]*6
city[0] = people

while city[5] < people:
    time += 1
    for i in range(5):
        t = min(capacity[4-i],city[4-i])
        city[4-i] -= t
        city[5-i] += t

print(time)

### FIXED CODE ###

import math
time = 5
people = int(input())
capacity = []
for i in range(5):
    capacity.append(int(input()))

time += math.ceil(people/min(capacity)) - 1
print(time)
### BUGGY CODE ###

class SegmentTree():
    def __init__(self, n):
        self.n = n
        self.dp = [0 for _ in range(2 * n)]
        
    def update(self, k, a):
        k += self.n
        self.dp[k] = a
        while (k > 1):
            self.dp[k >> 1] = max(self.dp[k], self.dp[k ^ 1])
            k >>= 1
        
    def query(self, l, r):
        res = 0
        l, r = l + self.n, r + self.n
        while l < r:
            if l & 1:
                res = max(res, self.dp[l])
                l += 1
            if r & 1:
                res = max(res, self.dp[r - 1])
            l, r = l >> 1, r >> 1
        return res
    
    
n, k = map(int, input().split())
A = []
for _ in range(n):
    a = int(input())
    A.append(a)
num = max(A) + k + 1

st = SegmentTree(num)
for i in range(n):
    x = A[i]
    l = max(x - k, 0)
    r = min(x + k + 1, num)
    now = st.query(l, r) + 1
    st.update(x, now)
print(max(st.dp))    

### FIXED CODE ###

class SegmentTree():
    def __init__(self, n):
        self.n = n
        self.dp = [0 for _ in range(2 * n)]
        
    def update(self, k, a):
        k += self.n
        self.dp[k] = a
        while (k > 1):
            self.dp[k >> 1] = max(self.dp[k], self.dp[k ^ 1])
            k >>= 1
        
    def query(self, l, r):
        res = 0
        l, r = l + self.n, r + self.n
        while l < r:
            if l & 1:
                res = max(res, self.dp[l])
                l += 1
            if r & 1:
                res = max(res, self.dp[r - 1])
            l, r = l >> 1, r >> 1
        return res
    
    
n, k = map(int, input().split())
A = []
for _ in range(n):
    a = int(input())
    A.append(a)
num = max(A) + k + 1

st = SegmentTree(num)
for i in range(n):
    x = A[i]
    l = max(x - k, 0)
    r = min(x + k + 1, num)
    now = st.query(l, r) + 1
    st.update(x, now)
print(max(st.dp))
### BUGGY CODE ###

import sys

input = sys.stdin.readline


def dot(a, b):
    an = len(a)
    bn = len(b[0])
    c = [[0] * bn for _ in range(an)]
    for i in range(an):
        ai = a[i]
        for j in range(bn):
            ck = 0
            for ak, bk in zip(ai, [bi[j] for bi in b]):
                ck += (ak * bk)
                c[i][j] = ck % md
    return c


def pwr(a, k):
    c = None
    while k > 0:
        if k & 1:
            if c:
                c = dot(a, c)
            else:
                c = a
        a = dot(a, a)
        k >>= 1
    return c


md = 10 ** 9 + 7
n, k = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
print(sum([sum(pk) % md for pk in pwr(a, k)]) % md)


### FIXED CODE ###

import sys

input = sys.stdin.readline


def dot(a, b):
    c = [[0] * n for _ in range(n)]
    for i, ai in enumerate(a):
        for j, bj in enumerate(zip(*b)):
            c[i][j] = sum(ak * bk for ak, bk in zip(ai, bj)) % md
    return c


def pwr(a, k):
    c = None
    while c == None:
        if k & 1:
            c = a
        a = dot(a, a)
        k >>= 1

    while k > 0:
        if k & 1:
            c = dot(a, c)
        a = dot(a, a)
        k >>= 1
    return c


md = 10 ** 9 + 7
n, k = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
print(sum([sum(pk) % md for pk in pwr(a, k)]) % md)
### BUGGY CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
N, D, A = map(int, input().split())

ys = []
for _ in range(N):
    X, H = map(int, input().split())
    ys.append((X, 0, -(-H//A)))
    ys.append((X+2*D, 1, -(-H//A)))

ys = sorted(ys, key=lambda x : (x[0],x[1]))
d1 = dict()
d2 = dict()
ls = []
c = 0
hs = [0]
for i, (y, f, h) in enumerate(ys):
    if f:
        d1[y-2*D] = c
    else:
        c += 1
        d2[y] = c
        ls.append(y)
        hs.append(h)

lls = []
for i in range(N):
    lls.append(d1[ls[i]]-d2[ls[i]]+1)

X = Bit(N+1)

r = 0
for i in range(N):
    n = lls[i]
    x = hs[i+1] + X.sum(i+1)
    if x <=0:
        continue
    r += x
    X.add(i+1, -x)
    X.add(i+1+n, x)
print(r)


### FIXED CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
N, D, A = map(int, input().split())

ys = []
for _ in range(N):
    X, H = map(int, input().split())
    ys.append((2*X, -(-H//A)))
    ys.append((2*X+4*D+1, -(-H//A)))

ys = sorted(ys, key=lambda x : x[0])
d1 = dict()
d2 = dict()
ls = []
c = 0
hs = [0]
for i, (y, h) in enumerate(ys):
    if y%2:
        d1[y-1-4*D] = c
    else:
        c += 1
        d2[y] = c
        ls.append(y)
        hs.append(h)

lls = []
for i in range(N):
    lls.append(d1[ls[i]]-d2[ls[i]]+1)

X = Bit(N+1)

r = 0
for i in range(N):
    n = lls[i]
    x = hs[i+1] + X.sum(i+1)
    if x <=0:
        continue
    r += x
    X.add(i+1, -x)
    X.add(i+1+n, x)
print(r)