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

import sys

input = sys.stdin.readline

def main():
    n, m, l = map(int, input().split())
    wf = [[0 for i in range(n)] for j in range(n)]
    for i in range(m):
        a, b, c = map(int, input().split())
        wf[a-1][b-1] = c
        wf[b-1][a-1] = c
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if (wf[i][k] != 0 and wf[k][j] != 0) and (wf[i][j] > wf[i][k] + wf[k][j] or wf[i][j] == 0):
                    wf[i][j] = wf[i][k] + wf[k][j]
    for i in range(n):
        for j in range(n):
            if wf[i][j] <= l and wf[i][j] != 0:
                wf[i][j] = 1
            else:
                wf[i][j] = 301
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if wf[i][j] > wf[i][k] + wf[k][j]:
                    wf[i][j] = wf[i][k] + wf[k][j]
    q = int(input())
    ans = [None] * q
    for i in range(q):
        s, t = map(int, input().split())
        if wf[s-1][t-1] < 301:
            ans[i] = wf[s-1][t-1]
        else:
            ans[i] = 0
    for i in range(q):
        print(ans[i] - 1)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall, shortest_path

input = sys.stdin.readline

def main():
    n, m, l = map(int, input().split())
    wf = [[0 for i in range(n)] for j in range(n)]
    for _ in range(m):
        a, b, c = map(int, input().split())
        wf[a-1][b-1] = wf[b-1][a-1] = c
    wf = np.array(wf)
    for i in range(n):
        wf[i][i] = 0
    wf = shortest_path(wf, method='FW')
    for i in range(n):
        for j in range(n):
            if wf[i][j] <= l:
                wf[i][j] = 1
            else:
                wf[i][j] = 301
    wf = shortest_path(wf, method='FW')
    q = int(input())
    ans = [None] * q
    for i in range(q):
        s, t = map(int, input().split())
        if wf[s-1][t-1] < 301:
            ans[i] = int(wf[s-1][t-1])
        else:
            ans[i] = 0
    for i in range(q):
        print(ans[i] - 1)

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

import sys
sys.setrecursionlimit(10**7)
N,Q =  map(int,input().split())
graph = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

val = [0 for i in range(N)]
for i in range(Q):
    a,b = map(int,input().split())
    val[a-1] += b 

def dps(i,parent): 
    for j in graph[i]:
        if j == parent:
            continue
        val[j] += val[i]
        dps(j,i)
                
dps(0,-1)
print(*val)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
readline = sys.stdin.readline
N,Q =  map(int,input().split())
graph = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,readline().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

val = [0 for i in range(N)]
for i in range(Q):
    a,b = map(int,readline().split())
    val[a-1] += b 

def dps(i,parent): 
    for j in graph[i]:
        if j == parent:
            continue
        val[j] += val[i]
        dps(j,i)
                
dps(0,-1)
print(*val)
### BUGGY CODE ###

n = int(input())

dishes = list()
for i in range(0, n):
    a, b = input().split()
    a = int(a)
    b = int(b)
    diff = b - a
    dishes.append([a, b, diff])

takahashi = 0
aoki = 0
diff_flag = True
for i in range(0, n):
    if i % 2 == 0:
        if diff_flag:
            dishes.sort(key=lambda x: x[2], reverse=True)
            j = dishes[0]
            if j[2] == 0:
                diff_flag = False
        if not diff_flag:
            dishes.sort(key=lambda x: x[0], reverse=True)

        j = dishes[0]
        dishes.pop(0)
        takahashi = takahashi + j[0]
    else:
        dishes.sort(key=lambda x: x[1], reverse=True)
        j = dishes[0]
        dishes.pop(0)
        aoki = aoki + j[1]

print(takahashi - aoki)


### FIXED CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-
import os
import re
import sys
import math


n = int(input())

dishes = list()

for i in range(0, n):
    a, b = raw_input().split()
    a = int(a)
    b = int(b)
    sum = a + b
    dishes.append([a, b, sum])

takahashi = 0
aoki = 0
dishes.sort(key=lambda x: x[2], reverse=True)

for i in range(0, n):
    if i % 2 == 0:
        j = dishes[0]
        dishes.pop(0)
        takahashi = takahashi + j[0]
    else:
        j = dishes[0]
        dishes.pop(0)
        aoki = aoki + j[1]

print takahashi - aoki
### BUGGY CODE ###

import math as np
K=int(input())
P=0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            l=np.gcd(i,j)
            m=np.gcd(l,k)
            P=m+P
print(P)

### FIXED CODE ###

import math as np
K=int(input())
P=0
for i in range(1,K+1):
    for j in range(1,K+1):
        l=np.gcd(i,j)

        for k in range(1,K+1):
            m=np.gcd(l,k)
            P=m+P
print(P)
### BUGGY CODE ###

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

c = 1

X = []
for i in range(N):
	for j in range(M):
		if A[i] != B[j]:
			X.append(min(A[i], B[j]))
X = sorted(X)

a = A[0]
for i in range(N - 1):
	if A[i + 1] == a:
		c = 0
		break
	a = A[i + 1]

b = B[0]
for i in range(M - 1):
	if B[i + 1] == b:
		c = 0
		break
	b = B[i + 1]

AA = []
BB = []
CC = []

for i in range(N):
	if A[i] in B:
		CC.append(A[i])
		B.remove(A[i])
	else:
		AA.append(A[i])

BB = B

xB = sorted(BB + CC)
xA = sorted(AA + CC)

for i in range(len(AA)):
	cc = 0
	for j in range(len(xB)):
		if xB[-1 - j] <= AA[i]:
			break
		else:
			cc += 1
	c = c * cc

for i in range(len(BB)):
	cc = 0
	for j in range(len(xA)):
		if xA[-1 - j] <= BB[i]:
			break
		else:
			cc += 1
	c = (c * cc) % 1000000007

for i in range(len(AA)):
	if c != 0:
		X.remove(AA[i])

for i in range(len(BB)):
	if c != 0:
		X.remove(BB[i])

if X != []:
	x = 0
m = 0
cnt = 0
for i in range(len(X)):
	if X[i] != x:
		m += 1
	c = (c * (X[i] - cnt - m)) % 1000000007
	cnt += 1
	x = X[i]

print(c)

### FIXED CODE ###

import heapq
from collections import defaultdict

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

D = defaultdict(int)
c = 1
hh = 0
for i in range(N):
	for j in range(M):
		if A[i] != B[j]:
			d = min(A[i], B[j])
			D[d] += 1
			hh += 1

ds = sorted(D.items())
X = []
for i in range(len(ds)):
	X += [ds[i][0]] * ds[i][1]


a = A[0]
for i in range(N - 1):
	if A[i + 1] == a:
		c = 0
		break
	a = A[i + 1]

b = B[0]
for i in range(M - 1):
	if B[i + 1] == b:
		c = 0
		break
	b = B[i + 1]

AA = []
BB = []
CC = []

for i in range(N):
	if A[i] in B:
		CC.append(A[i])
		B.remove(A[i])
	else:
		AA.append(A[i])

BB = B

xB = sorted(BB + CC)
xA = sorted(AA + CC)

for i in range(len(AA)):
	cc = 0
	for j in range(len(xB)):
		if xB[-1 - j] <= AA[i]:
			break
		else:
			cc += 1
	c = c * cc

for i in range(len(BB)):
	cc = 0
	for j in range(len(xA)):
		if xA[-1 - j] <= BB[i]:
			break
		else:
			cc += 1
	c = (c * cc) % 1000000007

if c != 0:
	if X != []:
		x = 0
	m = 0
	cnt = 0
	for i in range(hh):
		zzz = X[i]
		j = "G"
		if AA != []:
			if zzz == AA[0]:
				AA.remove(zzz)
				j = "N"
		if BB != []:
			if zzz == BB[0]:
				BB.remove(zzz)
				j = "N"

		if j == "G":
			if zzz != x:
				m += 1
			c = (c * (zzz - cnt - m)) % 1000000007
			cnt += 1
			x = zzz

print(c)
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict
import math
def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()
def IIR(n): return [II() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
mod = 1000000007

#A
"""
t,x = LI()
print(t/x)
"""

#B
"""
n= II()
a = LI()
m = max(a)
if m >= sum(a)-m:
    print("No")
else:
    print("Yes")
"""
#C
n,m = LI()
x = LI()
x.sort()
l = [x[i+1]-x[i] for i in range(m-1)]
l.sort()
l = l[::-1]
for i in range(n-1):
    if len(l) == 0:
        print(0)
        quit()
    l.pop(0)
print(sum(l))
#D
"""
n,k = LI()
a = LI()
l = 0
b = [0 for i in range(n)]
for i in range(n):
    b[i] = list(bin(a[i]))[2:]
    l = max(l,len(b[i]))
s = [0 for i in range(l)]
for i in range(n):
    for j in range(l-len(b[i])):
        b[i].insert(0,"0")
for i in range(n):
    for j in range(l):
        s[j] += 1-int(b[i][j])
ke = 1
for i in range(l)[::-1]:
    if s[i] <= n//2:
        s[i] = [(n-s[i])*ke,0,float("inf")]
    else:
        s[i] = [(n-s[i])*ke,s[i]*ke,ke]
    ke *= 2
s.sort(key = lambda x:x[0])
d = 0
ans = 0
key = len(list(bin(k)))-2
key -= l
ke = 2**l
print(s)
for i in range(key):
    d += ke
    ans += n*ke
    ke *= 2
for i in range(l):
    r,q,p = s[i]
    if d+p <= k:
        d += p
        ans += q
    else:
        ans += r
print(ans)
"""
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict
import math
def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()
def IIR(n): return [II() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
mod = 1000000007

#A
"""
t,x = LI()
print(t/x)
"""

#B
"""
n= II()
a = LI()
m = max(a)
if m >= sum(a)-m:
    print("No")
else:
    print("Yes")
"""

#C
n,m = LI()
x = LI()
x.sort()
l = [x[i+1]-x[i] for i in range(m-1)]
l.sort()
l = l[::-1]
ans = sum(l[max(n-1,0):])
print(ans)
#D
"""
n,k = LI()
a = LI()
l = 0
b = [0 for i in range(n)]
for i in range(n):
    b[i] = list(bin(a[i]))[2:]
    l = max(l,len(b[i]))
s = [0 for i in range(l)]
for i in range(n):
    for j in range(l-len(b[i])):
        b[i].insert(0,"0")
for i in range(n):
    for j in range(l):
        s[j] += 1-int(b[i][j])
ke = 1
for i in range(l)[::-1]:
    if s[i] <= n//2:
        s[i] = [(n-s[i])*ke,0,float("inf")]
    else:
        s[i] = [(n-s[i])*ke,s[i]*ke,ke]
    ke *= 2
s.sort(key = lambda x:x[0])
d = 0
ans = 0
key = len(list(bin(k)))-2
key -= l
ke = 2**l
print(s)
for i in range(key):
    d += ke
    ans += n*ke
    ke *= 2
for i in range(l):
    r,q,p = s[i]
    if d+p <= k:
        d += p
        ans += q
    else:
        ans += r
print(ans)
"""
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T
### BUGGY CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    n, m, k = map(int, args[0].split())
    AB = [tuple(map(int, ab)) for ab in map(str.split, args[1:1+m])]
    CD = [tuple(map(int, cd)) for cd in map(str.split, args[1+m:1+m+k])]

    friends = [set() for _ in range(n+1)]
    blocked = [set() for _ in range(n+1)]

    for a, b in AB:
        friends[a].add(b)
        friends[b].add(a)

    for c, d in CD:
        blocked[c].add(d)
        blocked[d].add(c)

    ret = [0]*(n+1)
    for a in range(1, n+1):
        checked = set((a,))
        stack = list(friends[a])
        while stack:
            b = stack.pop()
            if b in checked:
                continue

            checked.add(b)
            if b not in blocked[a] | friends[a]:
                ret[a] += 1

            stack.extend(friends[b]-checked)

    return ' '.join(map(str, ret[1:]))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

# coding: utf-8
from sys import setrecursionlimit


def dfs(node: int):
    if checked[node]:
        return

    checked[node] = True
    chain.add(node)
    for n in friends[node]:
        dfs(n)


def solve(*args: str) -> str:
    setrecursionlimit(2 * 10 ** 9)
    n, m, k = map(int, args[0].split())

    global friends
    friends = {i: set() for i in range(n+1)}
    blocked = {i: set() for i in range(n+1)}

    for a, b in map(str.split, args[1:1+m]):
        friends[int(a)].add(int(b))
        friends[int(b)].add(int(a))

    for c, d in map(str.split, args[1+m:1+m+k]):
        blocked[int(c)].add(int(d))
        blocked[int(d)].add(int(c))

    global checked
    checked = [False]*(n+1)

    ret = [0]*(n+1)
    for a in range(1, n+1):
        if checked[a]:
            continue

        global chain
        chain = set()
        dfs(a)
        count = len(chain) - 1
        for i in chain:
            ret[i] += count - len(chain & (friends[i] | blocked[i]))

    return ' '.join(map(str, ret[1:]))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
### BUGGY CODE ###

N = int(input())
S = []
for i in range(N):
    S.append(input())
    

#二部グラフ判定
L = [0 for i in range(N)]
L[0] = 1
q = [0]
res = 0

while len(q) > 0:
    idx = q.pop(-1)
    c = L[idx]*(-1)
    for i in range(N):
        if S[idx][i] == "1":
            if L[i] == 0:
                L[i] = c
                q.append(i)
            elif L[i] == c*(-1):
                res = 1
                q.clear()
                break
            

if res == 1:
    print(-1)
else:
    # Warshall-Floyd法で直径を求める
    d = [[10**4 for j in range(N)] for i in range(N)]
    # initialize
    for i in range(N):
        for j in range(N):
            if S[i][j] == "1":
                d[i][j] = 1
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if i != j:
                    d[i][j] = min(d[i][j], d[i][k]+d[k][j])

                
    ans = 0
    for i in range(N):
        for j in range(N):
            if d[i][j] < 10**4:
                ans = max(ans, d[i][j])
                
    print(ans+1)

### FIXED CODE ###

N = int(input())
S = []
for i in range(N):
    S.append(input())
    

#二部グラフ判定
L = [0 for i in range(N)]
L[0] = 1
q = [0]
res = 0

while len(q) > 0:
    idx = q.pop(-1)
    c = L[idx]*(-1)
    for i in range(N):
        if S[idx][i] == "1":
            if L[i] == 0:
                L[i] = c
                q.append(i)
            elif L[i] == c*(-1):
                res = 1
                q = []
                break
            

if res == 1:
    print(-1)
else:
    # Warshall-Floyd法で直径を求める
    d = [[10**4 for j in range(N)] for i in range(N)]
    # initialize
    for i in range(N):
        for j in range(N):
            if S[i][j] == "1":
                d[i][j] = 1
    
    # DP
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if i != j:
                    d[i][j] = min(d[i][j], d[i][k]+d[k][j])

                
    ans = 0
    for i in range(N):
        for j in range(N):
            if d[i][j] < 10**4:
                ans = max(ans, d[i][j])
                
    print(ans+1)
### BUGGY CODE ###

#!/usr/bin/env python3

# from typing import Optional
from typing import List
import array

# from typing import Dict
from typing import Tuple

# from typing import Sequence

Cod = Tuple[int, int]


def main():
    args = input().split()
    H = int(args[0])
    W = int(args[1])
    M = int(args[2])

    codList: array[Cod] = []
    for i in range(M):
        args = input().split()
        codList.append((int(args[0]), int(args[1])))

    columnSumList: array[int] = [0] * W
    rowSumList: array[int] = [0] * H

    maxColumnSum = 0
    maxColumIndexList: array[int] = []
    maxRowSum = 0
    maxRowIndexList: array[int] = []
    for item in codList:
        columnSum = columnSumList[item[1] - 1] + 1
        if columnSum > maxColumnSum:
            maxColumnSum = columnSum
            maxColumIndexList = [item[1]]
        elif columnSum == maxColumnSum:
            maxColumIndexList.append(item[1])

        rowSum = rowSumList[item[0] - 1] + 1
        if rowSum > maxRowSum:
            maxRowSum = rowSum
            maxRowIndexList = [item[0]]
        elif rowSum == maxRowSum:
            maxRowIndexList.append(item[0])

        columnSumList[item[1] - 1] = columnSum
        rowSumList[item[0] - 1] += 1

    result = maxColumnSum + maxRowSum
    for row in maxRowIndexList:
        for column in maxColumIndexList:
            if (row, column) in codList:
                continue
            else:
                print(result)
                return

    print(result - 1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

# from typing import Optional
from typing import List

# from typing import Dict
from typing import Tuple
from typing import Set

# from typing import Sequence

Cod = Tuple[int, int]


def main():
    args = input().split()
    H = int(args[0])
    W = int(args[1])
    M = int(args[2])

    codList = {}
    columnSumList: List[int] = [0] * W
    rowSumList: List[int] = [0] * H
    for i in range(M):
        h, w = map(lambda x: int(x), input().split())
        item = (h, w)
        codList.setdefault(h, {})
        codList[h][w] = item
        columnSumList[w - 1] += 1
        rowSumList[h - 1] += 1

    maxColumnSum = max(columnSumList)
    maxColumIndexList = [i for i, x in enumerate(columnSumList) if x == maxColumnSum]
    maxRowSum = max(rowSumList)
    maxRowIndexList = [i for i, x in enumerate(rowSumList) if x == maxRowSum]

    result = maxColumnSum + maxRowSum
    for row in maxRowIndexList:
        for column in maxColumIndexList:
            if row + 1 in codList and column + 1 in codList[row + 1]:
                continue
            else:
                print(result)
                return

    print(result - 1)


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

N,K=map(int,input().split())
A=list(map(int,input().split()))
cnt=0
for i in range(N):
  Alen=0
  Asum=0
  for j in range(i,N):
    if i==j:
      Alen=1
      Asum=A[j]
    else:
      Alen+=1
      Asum+=A[j]
    if Asum%K==Alen:
      cnt+=1
print(cnt)

### FIXED CODE ###

from collections import defaultdict
d=defaultdict(int)
N,K=map(int,input().split())
A=[0]+list(map(int,input().split()))
S=[None]*(N+1)
S[0]=0
cnt=0
d[0]=1
for i in range(1,N+1):
  S[i]=(S[i-1]+A[i]-1)%K
for i in range(1,N+1):
  if i-K>=0:
    d[S[i-K]]-=1
  cnt+=d[S[i]]
  d[S[i]]+=1
print(cnt)
### BUGGY CODE ###

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

A    = [int(i)-1 for i in input().split()]

visited_town = []
current_town = 0
loop_flg     = False
visited_town.append(current_town)
for i in range(K):
    current_town = A[current_town]
    if current_town in visited_town:
        visited_town.append(current_town)
        loop_flg = True
        break
    visited_town.append(current_town)


if loop_flg:
    loop_start = visited_town.index(current_town)
    loop_end   = len(visited_town) - 1
    loop_length = loop_end - loop_start
    last_index = (K-loop_start)%loop_length
    current_town = visited_town[loop_start+last_index]

print(current_town+1)

### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    A    = [int(i)-1 for i in input().split()]

    visited_town = []
    current_town = 0
    loop_flg     = False
    visited_town.append(current_town)
    set_visted_town = set(visited_town)
    for i in range(K):
        current_town = A[current_town]
        if current_town in set_visted_town:
            visited_town.append(current_town)
            loop_flg = True
            break
        visited_town.append(current_town)
        set_visted_town.add(current_town)


    if loop_flg:
        loop_start = visited_town.index(current_town)
        loop_end   = len(visited_town) - 1
        loop_length = loop_end - loop_start
        last_index = (K-loop_start)%loop_length
        current_town = visited_town[loop_start+last_index]

    print(current_town+1)


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

N, P = map(int, input().split())
S = input()

l = len(S)
if P == 2:
    ans = 0
    for i in range(l):
        if int(S[i])%2 == 0:
            ans += i+1
elif P == 5:
    ans = 0
    for i in range(l):
        if int(S[i])%5 == 0:
            ans += i+1
else:
    data = [0]*P
    temp = 0
    ans = 0
    for i in range(l-1, -1, -1):
        temp += (int(S[i])*(10**(l-i-1)))%P
        temp %= P
        ans += data[temp]
        data[temp] += 1
    ans += data[0]

print(ans)

### FIXED CODE ###

N, P = map(int, input().split())
S = list(map(int, list(input())))

l = len(S)
if P == 2:
    ans = 0
    for i in range(l):
        if S[i]%2 == 0:
            ans += i+1
elif P == 5:
    ans = 0
    for i in range(l):
        if S[i]%5 == 0:
            ans += i+1
else:
    data = [0]*P
    temp = 0
    ans = 0
    for i in range(l-1, -1, -1):
        temp += S[i]*pow(10, l-i-1, P)
        temp %= P
        ans += data[temp]
        data[temp] += 1
    ans += data[0]

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

primes = [0, 0] + [1] * 9999999
for i in range(2, 3163):
    if primes[i]:
        for j in range(i*i, 10000001, i):
            primes[j] = 0

while True:
    n = int(input())
    if n == 0:
        break
    while not (primes[n-8] & primes[n-6] & primes[n-2] & primes[n]):
        n -= 1
    print(n)

### FIXED CODE ###

import bisect


primes = [0, 0] + [1] * 9999999
for i in range(2, 3163):
    if primes[i]:
        for j in range(i*i, 10000001, i):
            primes[j] = 0

values = [i for i, v in enumerate(primes) if v]
while True:
    n = int(input())
    if n == 0:
        break
    index = bisect.bisect(values, n)
    for i in range(2, index)[::-1]:
        if all(primes[values[i]-j] for j in [0, 2, 6, 8]):
            print(values[i])
            break
### BUGGY CODE ###

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

def convi(li):
    m=max(li)
    a=[1,1]
    if m>2:
        for i in range(2,m+1):
            a.append(a[i-2]+a[i-1])
            
    ans=1    
    for j in li:
        ans*=a[j-1]
    return ans

def count(li,n):
    t=1
    ans=1
    li2=[]
    for i in range(1,n+1):
        if i in li:
            if i+1 in li:
                return(0)
            else:
                li2.append(t)
                t=0
        else:
            t+=1
    if t>0:        
        li2.append(t)   
    if 0 in li2:
    	li2.remove(0)
        

        
    return convi(li2)

                

print(count(li,n)%1000000007)   

### FIXED CODE ###

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

def convi(li):
    m=max(li)
    a=[1,1]
    if m>2:
        for i in range(2,m+1):
            a.append(a[i-2]+a[i-1])
            
    ans=1    
    for j in li:
        ans=ans*a[j-1]%1000000007
    return ans

def count(li,n):
    t=1
    ans=1
    li2=[]
    li.append(n+1)
    if len(li)>0:
        for i in range(len(li)):
            
            if i>0:
                li2.append(li[i]-li[i-1]-1)
                if li[i]-li[i-1]==1 and i<len(li):
                    return 0
            else:
                li2.append(li[i])
                
    #print(li2)      
    return convi(li2)
                

print(count(li,n)%1000000007)
### BUGGY CODE ###

n=int(input())
s=input()
cnt=0
if n<=2:
    print(0)
    quit()
import itertools           
for i,j,k in itertools.combinations_with_replacement(range(0,n), 3):
    si,sj,sk=s[i],s[j],s[k]
    if 2*j!=i+k and si!=sj and si!=sk and sj!=sk:
        cnt+=1
print(cnt)


### FIXED CODE ###

n = int(input())
s =     input()
if n < 3:
  print(0)
  exit

result = s.count('R') * s.count('G') * s.count('B')
for i in range(n):
  for j in range(i+1, n):
    k = 2*j - i
    if k < n and s[k] != s[i] and s[k] != s[j] and s[j] != s[i]:
      result -= 1

print(result)
### BUGGY CODE ###

import numpy as np

N, M = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(N)]
a.sort()
a.append([np.inf, np.inf])
job = []
ans = 0
ind = 0
for i in range(1, M+1):
    while a[ind][0] <= i:
        job.append(a[ind][1])
        ind += 1
        if ind == N:
            break
    if job:
        m = max(job)
        ans += m
        job.remove(m)
print(ans)

### FIXED CODE ###

import heapq as hq
import numpy as np

N, M = map(int, input().split())
job = [list(map(int, input().split())) for _ in range(N)]
ans = 0
job.sort()
job.append([np.inf, np.inf])
jobhq = []
index = 0
for day in range(1, M + 1):
    while day >= job[index][0]:
        hq.heappush(jobhq, - job[index][1])
        index += 1
    if jobhq:
        ans += - hq.heappop(jobhq)
print(ans)