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

from sys import stdin
from itertools import accumulate
def main():
    #入力
    readline=stdin.readline
    n,m,q=map(int,readline().split())
    table=[[0]*n for _ in range(n)]
    for i in range(m):
        l,r=map(lambda x:int(x)-1,readline().split())
        table[l][r]+=1

    #累積和
    for i in range(n):
        table[i]=list(accumulate(table[i]))

    ans=[0]*q
    for i in range(q):
        l,r=map(lambda x:int(x)-1,readline().split())
        t=0
        for j in range(l,r+1):
            t+=table[j][r]
        ans[i]=t

    for i in range(q):
        print(ans[i])

if __name__=="__main__":
    main()

### FIXED CODE ###

from sys import stdin
from itertools import accumulate
def main():
    #入力
    readline=stdin.readline
    n,m,q=map(int,readline().split())
    table=[[0]*n for _ in range(n)]
    for i in range(m):
        l,r=map(lambda x:int(x)-1,readline().split())
        table[l][r]+=1

    #累積和
    for i in range(n):
        table[i]=list(accumulate(table[i]))

    ans=[0]*q
    for i in range(q):
        l,r=map(lambda x:int(x)-1,readline().split())
        t=0
        for j in range(l,r+1):
            t+=table[j][r]
        ans[i]=t

    for i in range(q):
        print(ans[i])

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

N = int(input())
for i in range(1,N):
    N = N*i
print(N%(10**9+7))

### FIXED CODE ###

from math import factorial
N = int(input())
print(factorial(N)%(10**9+7))
### BUGGY CODE ###

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


### FIXED CODE ###

import math
K = int(input())
ans = 0
for i in range(1,K+1):
    ans -= i*2
    for j in range(i,K+1):
        l = math.gcd(i,j)
        ans -= l*3
        for k in range(j,K+1):
            ans += math.gcd(l,k)*6

for i in range(1,K+1):
    for j in range(i+1,K+1):
        ans -= math.gcd(i,j)*3

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

#0<=i<r,0<=j<cで総和求めて引く
#chooseの+2でよい
#10**6なのでpythonにしてみる
mod = 10**9+7
def chs(a,b):
    a+=1;b+=1
    a+=b
    res = 1
    for i in range(a,a-b,-1):
        res *= i 
        res%=mod
    for i in range(1,b+1):
        rev = pow(i,mod-2,mod)
        res *= rev 
        res %=mod 
    return res


r1,c1,r2,c2 = map(int, input().split( ))
r1 -=1;c1-=1
#print(chs(r2,c2),chs(r1,c2),chs(r2,c1),chs(r1,c1))
ans = chs(r2,c2)-chs(r1,c2)-chs(r2,c1)+chs(r1,c1)
ans%=mod

print(ans)

### FIXED CODE ###

#0<=i<r,0<=j<cで総和求めて引く
#chooseの+2でよい
mod = 10**9+7

def chs(a,b):
    a+=1;b+=1
    a+=b
    res = 1
    for i in range(a,a-b,-1):
        res *= i 
        res%=mod
    for i in range(1,b+1):
        res *= rev[i]
        #print(rev[i],pow(i,mod-2,mod))
        res %=mod 
    return res


r1,c1,r2,c2 = map(int, input().split( ))
r1 -=1;c1-=1
if c2>r2:
    r2,c2 = c2,r2
    r1,c1= c1,r1
rev = [pow(i,mod-2,mod) for i in range(c2+5)]###
ans = chs(r2,c2)-chs(r1,c2)-chs(r2,c1)+chs(r1,c1)
ans%=mod
#print(chs(r2,c2),chs(r1,c2),chs(r2,c1),chs(r1,c1))

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

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

passwords =[]

for a in range(n-2):
    for b in range(a+1,n-1):
        for c in range(b+1,n):
            
            pw = s[a] + s[b] + s[c] 
            passwords.append(pw)
            
            # print(pw)
passwords = list(set(passwords))
print(len(passwords))

### FIXED CODE ###

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

score = 0

for p in range(1000):
    
    pw = str(p).zfill(3)
    
    start = 0
    n_match = 0
    
    for j in range(3):
        for i in range(start, len(s)):
            
            if s[i] == pw[j]:
                start = i+1
                n_match = n_match+1
                
                if j == 3-1:
                    # print(pw)
                    score = score+1
                
                break
        if n_match <= j:
            break
            
print(score)
### BUGGY CODE ###

def main():
	n = int(input())
	l = [str(input()) for i in range(n)]
	
	import collections

	c = collections.Counter(l)

	keys = [k for k, v in c.items() if v == max(c.values())]
	keys.sort()
	print('\n'.join(map(str, keys)))

	
	
 
if __name__ == '__main__':
	main()

### FIXED CODE ###

def main():
	# n,m = map(int,input().split())
	n = int(input())
	l = [str(input()) for i in range(n)]
	
	import collections

	c = collections.Counter(l)
	lc = sorted(list(c.items()), key = lambda x:x[1] , reverse = True)
	# print(lc[0][0])
	ans = []
	checker = 0
	i = 0
	while checker == 0 and i < len(lc):
		if lc[i][1] == lc[0][1]:
			ans.append(lc[i][0])
		else:
			checker += 1
		i += 1

	# keys = [k for k, v in c.items() if v == max(c.values())]
	# print(list(c.items())[0][0])
	# checker = 0
	# while checker == 0:
	# 	if c.items() == max(c.values()):
	ans.sort()
	print('\n'.join(map(str, ans)))

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

import heapq

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


L = a[:N]
R = a[(N*2):]
L_sum_list = [sum(L)]
R_sum_list = [sum(R)]

R = [-elem for elem in R]
for k in range(N):
    #L側
    L.append(a[N+k])
    heapq.heapify(L)
    rem = a[N+k] - heapq.heappop(L)
    L_sum_list.append(L_sum_list[-1]+rem)

    #R側
    R.append(-(a[N*2-k-1]))
    heapq.heapify(R)
    rem = -(a[N*2-k-1]) - heapq.heappop(R)
    R_sum_list.append(R_sum_list[-1]-rem)

res = []
for k in range(N+1):
    res.append(L_sum_list[k] - R_sum_list[-k-1])
print(max(res))
    



### FIXED CODE ###

import heapq

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


L = a[:N]
R = a[(N*2):]
L_sum_list = [sum(L)]
R_sum_list = [sum(R)]

R = [-elem for elem in R]

heapq.heapify(L)
heapq.heapify(R)

for k in range(N):
    #L側
    rem = a[N+k] - heapq.heappushpop(L, a[N+k])
    L_sum_list.append(L_sum_list[-1]+rem)

    #R側
    rem = -(a[N*2-k-1]) - heapq.heappushpop(R, -(a[N*2-k-1]))
    R_sum_list.append(R_sum_list[-1]-rem)

res = []
for k in range(N+1):
    res.append(L_sum_list[k] - R_sum_list[-k-1])

print(max(res))
### BUGGY CODE ###

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

ans = 1
j = 0
for a in A:
  ans = ans*a
  if(ans > 10**18):
    j = 1
    
if((j == 0)or(ans == 0)):
  print(ans)
else:
  print(-1)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
         
if(0 in A):
  ans = 0 
else:
  ans = 1       
  for a in A:
    ans *= a
    if(ans > 10**18):
      ans = -1
      break
    if(len(str(ans))>=2):
     if(str(ans)[1] == 'e'):
      ans = -1
      break
         
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    M = int(input())
    wa = 0
    ans = 0
    for _ in range(M):
        d, c = [int(x) for x in input().split()]
        for _ in range(c):
            wa += d
            ans += 1
            if wa >= 10:
                ans += 1
                wa = wa % 10 + 1
    
    print(ans - 1)

    



if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    M = int(input())
    count = 0
    wa = 0
    for _ in range(M):
        d, c = [int(x) for x in input().split()]
        count += c
        wa += d * c
    
    print(count - 1 + ((wa - 1) // 9))
    



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

N = int(input())
C = []
S = []
F = []
T = [0 for i in range(N)]

for i in range(N-1):
    c,s,f = map(int,input().split())
    C.append(c)
    S.append(s)
    F.append(f)

for i in range(1,N):
    time = 0
    if i == 1:
        #print(S[-i])
        time = S[-i] + C[-i]
    else:
        time = S[-i] + C[-i]
        for j in range(1,i):
            if time < S[-(i-j)]:
                time = S[-(i-j)] + C[-(i-j)]
            else:
                n = 1
                while True:
                    dev = S[-(i-j)] + n * F[-(i-j)] - time
                    if(0 <= dev and dev <  F[-(i-j)]):
                          time = (time + dev + C[-(i-j)])
                          break
                    n+=1
    T[-(i+1)] = time

for t in T:
    print(t)

### FIXED CODE ###

N = int(input())
C = []
S = []
F = []
T = [0 for i in range(N)]

for i in range(N-1):
    c,s,f = map(int,input().split())
    C.append(c)
    S.append(s)
    F.append(f)

for i in range(1,N):
    time = 0
    if i == 1:
        #print(S[-i])
        time = S[-i] + C[-i]
    else:
        time = S[-i] + C[-i]
        for j in range(1,i):
            if time < S[-(i-j)]:
                time = S[-(i-j)] + C[-(i-j)]
            else:
                dev = (time - S[-(i-j)]) % F[-(i-j)]
                if(dev != 0):
                    time = (time + (F[-(i-j)] - dev) + C[-(i-j)])
                else:
                    time = time + C[-(i-j)]
    T[-(i+1)] = time

for t in T:
    print(t)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np

def main():
	N, M, Q = map(int, input().split(" "))
	N_list = [[0 for _ in range(N)] for _ in range(N)]
	
	for _ in range(M):
		l, r = map(int, input().split(" "))
		l -= 1
		r -= 1
		for a in range(l, N):
			for b in range(r, N):
				N_list[a][b] += 1
		
	for _ in range(Q):
		p, q = map(int, input().split(" "))
		p -= 1
		q -= 1
		
		a = 0
		b = 0
		c = 0
		if p != 0:
			a = N_list[q][p-1]
			b = N_list[p-1][q]
			c = N_list[p-1][p-1]
		ans = N_list[q][q] - a - b + c
		print(ans)
		
	
if __name__ == "__main__":
	main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np

def main():
	N, M, Q = map(int, input().split(" "))
	N_list = [[0 for _ in range(N)] for _ in range(N)]
	
	for _ in range(M):
		l, r = map(int, input().split(" "))
		l -= 1
		r -= 1
		N_list[l][r] += 1
		
	#print(N_list)
	
	for i in range(N):
		for j in range(N):
			if i == 0 and j == 0:
				continue
			if i == 0:
				N_list[i][j] = N_list[i][j] + N_list[i][j-1]
				continue
			if j == 0:
				N_list[i][j] = N_list[i][j] + N_list[i-1][j]
				continue
			N_list[i][j] = N_list[i][j] + N_list[i-1][j] + N_list[i][j-1] - N_list[i-1][j-1]
			
	#print(N_list)
		
	for _ in range(Q):
		p, q = map(int, input().split(" "))
		p -= 1
		q -= 1
		
		a = 0
		b = 0
		c = 0
		if p != 0:
			a = N_list[q][p-1]
			b = N_list[p-1][q]
			c = N_list[p-1][p-1]
		ans = N_list[q][q] - a - b + c
		print(ans)
		
	
if __name__ == "__main__":
	main()
### BUGGY CODE ###

#! /usr/bin/env python3
import sys
sys.setrecursionlimit(10**9)


INF=10**20
class Counter:
    def __init__(self):
        self.dict = {}

    def add(self,x):
        if x in self.dict: self.dict[x] += 1
        else: self.dict[x] = 1

    def decrement(self,x):
        self.dict[x] -= 1
        if self.dict[x] <= 0:
            del self.dict[x]

    def get_dict(self):
        return self.dict


def solve(S):
    N = len(S)

    v1 = [0] * (N+1)
    v1[0] = 0

    for i in range(N):
        v1[i+1] = v1[i] * 10 + int(S[i])

    counter = Counter()
    for i in range(N+1):
        u = v1[i] * pow(10,201900-i,2019) % 2019
        counter.add(u)

    
    ans = 0
    # print(counter.get_dict())
    for _,count in counter.get_dict().items():
        ans += count * (count-1) // 2
    
    print(ans)

    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = list((next(tokens)))  # type: int
    solve(S)



if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

def main():
    S = [int(s) for s in input()]
    N = len(S)
    K = 2019

    V = [0] * (N+1)
    for i in reversed(range(N)):
        rev_i = (N-1)-i
        V[rev_i+1] = V[rev_i] + S[i] * (pow(10,rev_i+1,K))
        # print(V)

    dic = {} # value:count
    U = set()
    for v in V:
        u = v % K
        if u in U:
            dic[u] += 1
        else:
            dic[u] = 1
            U.add(u)

    ans = 0
    for u in U:
        u_count = dic[u]
        ans += u_count * (u_count-1) // 2

    # print(S)
    # print(V)
    # print(dic)
    print(ans)

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

import math
import collections
def f(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 = n//f
        else:f += 2
    if n != 1:
        a.append(n)
    return a

ans = 0
n = int(input())
for i in map(int,input().split()):
    c = collections.Counter(f(i))
    ans += c[2]
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
for i in map(int,input().split()):
    a = i
    while a % 2 == 0:
        ans += 1
        a = a // 2
print(ans)
### BUGGY CODE ###

# 最大公約数
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

# 最小公倍数


def lcm(x, y):
    return (x * y) // gcd(x, y)

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

x = A[0]
for i in range(N):
    x = lcm(x, A[i])

sums = 0
for i in range(N):
    sums += x // A[i]
    sums %= 10 ** 9 + 7

print(sums)

### FIXED CODE ###

from fractions import gcd
# 最小公倍数
def lcm(x, y):
    return x // gcd(x, y) * y

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

x = A[0]
for i in range(N):
    x = lcm(x, A[i]) 


sums = 0
mod = 10 ** 9 + 7
for i in range(N):
    sums += x // A[i]

print(sums % mod)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
m = 1
for i in range(len(a)):
    m = m * a[i]
if m > 10 ** 18:
    print(-1)
    exit()
else:
    print(m)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
m = 1
if 0 in a:
    print(0)
    exit()
for i in range(len(a)):
    m = m * a[i]
    if m > 10 ** 18:
        print(-1)
        exit()
print(m)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7
ans = 0
for i in range(60):
    count = 0
    for j in a:
        if j >> i & 1:
            count += 1
    ans += count * (n-count) * pow(2,i,mod)
print(ans % mod)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7
ans = 0
for i in range(60):
    mask = 1 << i
    count = sum(1 for j in a if mask & j == 0)
    ans += count * (n-count) * pow(2,i,mod)
print(ans % mod)
### BUGGY CODE ###

import numpy as np

n = int(input())
dam = list(map(int, input().split()))
yama = [0] * n
yama_copy = [0] * n

min_dam = min(dam)
min_arg = np.argmin(dam)

yama_bf = min_arg
yama_i = min_arg
for i in range(0, min_dam * 2 + 1, 2):
    yama_copy[yama_i] = i
    yama_i = (yama_i + 1) % n
    for j in range(n-1):
        yama_copy[yama_i] = (dam[yama_bf] - yama_copy[yama_bf]/2) * 2
        yama_bf = yama_i
        yama_i = (yama_i + 1) % n
    if dam[yama_bf] == yama_copy[yama_bf]/2 + yama_copy[min_arg]/2:
        break
    yama_copy = [0] * n
    yama_bf = min_arg
    yama_i = min_arg
yama_copy = map(int, yama_copy)
print(' '.join(map(str, yama_copy)))

### FIXED CODE ###

import numpy as np

n = int(input())
dam = list(map(int, input().split()))
yama = [-1] * n

min_dam = min(dam)
min_dam_arg = np.argmin(dam)

s = sum(dam)
yama[0] = s - 2 * sum(dam[1::2])
for i in range(1, n):
    yama[i] = 2 * (dam[i-1] - yama[i-1]/2)

yama = map(int, yama)
print(' '.join(map(str, yama)))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(1000000)

MOD = 10 ** 9 + 7

n = int(input())

ab = [[] for _ in range(n)]

for _ in range(n-1):
    a, b = map(int, input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)

def treeDP(p):
    if len(ab[p]) == 0:
        return [2,1]
    else:
        f = 1
        g = 1
        for x in ab[p]:
            ab[x].remove(p)
            temp = treeDP(x)
            f *= temp[1]
            g *= temp[0]
        f += g
        return [f % MOD, g % MOD]

print(treeDP(0)[0])


### FIXED CODE ###

import sys

sys.setrecursionlimit(1000000)

MOD = 10 ** 9 + 7

n = int(input())

ab = [[] for _ in range(n)]

for _ in range(n-1):
    a, b = map(int, input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)

def treeDP(p):
    if len(ab[p]) == 0:
        return [2,1]
    else:
        f = 1
        g = 1
        for x in ab[p]:
            ab[x].remove(p)
            temp = treeDP(x)
            f *= temp[1]
            g *= temp[0]
        f += g
        return [f % MOD, g % MOD]

print(treeDP(0)[0])
### BUGGY CODE ###

S = input()
gx, gy = map(int, input().split())

from collections import deque
# 命令, x, y, 向き
q = deque([[-1, 0, 0, (1, 0)]])

ans = 'No'
while q:
    i, x, y, rot = q.popleft()
    if i == len(S)-1 and x==gx and y == gy:
        ans = 'Yes'
        break
    elif i == len(S)-1:
        continue
    ind = S[i+1]

    if ind == 'T':
        q.append((i+1, x, y, (-rot[1], rot[0])))
        q.append((i+1, x, y, (rot[1], -rot[0])))
    else:
        if abs(gx-x-rot[0]) + abs(gy-y-rot[1]) < len(S)-i:
            q.append((i+1, x+rot[0], y+rot[1], rot))
    
print(ans)


### FIXED CODE ###

S = input()
gx, gy = map(int, input().split())
SL = S.split('T')
D = [len(sli) for sli in SL]
DX = D[2::2]
DY = D[1::2]

def reachable(D, s, g):
    dp = [{} for _ in range(len(D)+1)]
    dp[0][s] = 1
    for i in range(len(D)):
        d = D[i]
        for j in dp[i]:
            dp[i+1][j+d] = 1
            dp[i+1][j-d] = 1
    return g in dp[-1]

if reachable(DX, D[0], gx) and reachable(DY, 0, gy):
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

num = int(input())

num_list = []

for i in range(0,num):
  num_list.append(input())

num_set = list(set(num_list))
count_list = []

num_list_len = len(num_list)

for i in range(0,len(num_set)):
  while num_set[i] in num_list:
    num_list.remove(num_set[i])
    
  count_list.append(num_list_len - len(num_list))
  num_list_len = len(num_list)

ans = []
max = 0

for i in range(0,len(num_set)):
  temp = count_list[i]
  
  if temp == max:
    ans.append(num_set[i])
  
  if temp > max:
    max = temp
    ans = []
    ans.append(num_set[i])
ans.sort()

for i in range(0,len(ans)):
  print(ans[i])

### FIXED CODE ###

import collections

num = int(input())

num_list = []
count_list = []
ans = []

for i in range(0,num):
  num_list.append(input())

num_list_2 =collections.Counter(num_list).most_common()

for i in range(0,len(num_list_2)):
  if num_list_2[0][1] > num_list_2[i][1]:
    break
  
  ans.append(num_list_2[i][0])

ans.sort()

for i in range(0,len(ans)):
  print(ans[i])
### BUGGY CODE ###

import numpy as np
def main():
  H, W, D = map(int, input().split())
  num = [[] for _  in range(H*W)]
  for i in range(H):
    temp = list(map(int, input().split()))
    for j in range(len(temp)):
      num[temp[j]-1] = [i, j]
  num = np.array(num)
  num_sum = [0]*(H*W)
  for i in range(D, H*W):
    num_sum[i] = num_sum[i-D] + np.sum(np.abs(num[i]-num[i-D]))
  Q = int(input())
  for i in range(Q):
    L, R = map(int, input().split())
    print(num_sum[R-1]-num_sum[L-1])
if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  H, W, D = map(int, input().split())
  num = [[] for _  in range(H*W)]
  for i in range(H):
    temp = list(map(int, input().split()))
    for j in range(len(temp)):
      num[temp[j]-1] = [i, j]
  #num = np.array(num)
  num_sum = [0]*(H*W)
  for i in range(D, H*W):
    num_sum[i] = num_sum[i-D] + (abs(num[i][0]-num[i-D][0])+ abs(num[i][1]-num[i-D][1]))
  Q = int(input())
  for i in range(Q):
    L, R = map(int, input().split())
    print(num_sum[R-1]-num_sum[L-1])
if __name__ == "__main__":
  main()
### BUGGY CODE ###

n=int(input())
ar=list(map(int,input().split()))
dp=[0]*n
for i in range(n):
    x=0
    for j in range(n):
        if(i!=j):
            x^=ar[j]
    dp[i]=x
print(' '.join(map(str,dp)))
    

### FIXED CODE ###

n=int(input())
ar=list(map(int,input().split()))
x=0
for i in range(n):
    x^=ar[i]
for i in range(n):
    print(ar[i]^x,end=" ")
### BUGGY CODE ###

from collections import defaultdict as dd
from collections import deque
from copy import deepcopy as dc
N, M = map(int, input().split())
e = dd(list)
inf = 10 ** 9
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
S, T = map(int, input().split())

stopped = [inf] * (N + 1)
Q = deque()
Q.append(S)
stopped[S] = 0
saw2 = {i: 0 for i in range(1, N + 1)}
#saw3 = {i: 0 for i in range(1, N + 1)}
while len(Q) != 0:
  s2 = dc(saw2)
  #s3 = dc(saw3)
  p = Q.popleft()
  if stopped[p] >= stopped[T]:
    break
  for q in e[p]:
    for r in e[q]:
      if s2[r] == 1:
        continue
      else:
        s2[r] = 1
      for s in e[r]:
        #if s3[s] == 1:
        #  continue
        #else:
        #  s3[s] = 1
        if stopped[s] > stopped[p] + 1:
          Q.append(s)
          stopped[s] = stopped[p] + 1
if stopped[T] == inf:
  print(-1)
else:
  print(stopped[T])

### FIXED CODE ###

from collections import defaultdict as dd
from collections import deque
N, M = map(int, input().split())
e = dd(list)
inf = 10 ** 9
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v + N)
  e[u + N].append(v + 2 * N)
  e[u + 2 * N].append(v)
S, T = map(int, input().split())
S += 2 * N
T += 2 * N
stopped = [inf] * (3 * (N + 1))
Q = deque()
Q.append(S)
stopped[S] = 0
while len(Q) != 0:
  p = Q.popleft()
  if stopped[p] >= stopped[T]:
    break
  for q in e[p]:
    if stopped[q] > stopped[p] + 1:
      Q.append(q)
      stopped[q] = stopped[p] + 1
if stopped[T] == inf:
  print(-1)
else:
  print(stopped[T] // 3)
### BUGGY CODE ###

X = input()

for _ in range(len(X)):
    X = X.replace('ST', '')

print(len(X))


### FIXED CODE ###

X = input()

S_count = 0
T_count = 0
for item in X:
    if item == 'S':
        S_count += 1
    elif item == 'T' and S_count > 0:
        S_count -= 1


print(2 * S_count)
### BUGGY CODE ###

n = int(input())
from math import gcd

samu = 0

for i in range(n):
    for j in range(n):
        for k in range(n):
            samu += gcd(gcd(i+1,j+1),k+1)


print(str(int(samu)))


### FIXED CODE ###

k = int(input())
from math import gcd

samu = 0

for i in range(1,k+1):
    for j in range(1,k+1):
        for k in range(1,k+1):
            samu += gcd(gcd(i,j),k)


print(samu)
### BUGGY CODE ###

L,R = list(map(int,input().split()))
Y = []
for i in range(L, R):
    for j in range(i+1, R+1):
        Y.append((i * j) % 2019)
print(min(Y))

### FIXED CODE ###

L,R = list(map(int,input().split()))
def main(L,R):
    mod_min = 2019
    if L // mod_min == R // mod_min:
        L %= mod_min
        R %= mod_min
        for i in range(L,R):
            for j in range(i+1, R+1):
                Y = i*j % 2019
                if Y < mod_min:
                    mod_min = Y
    else:
        mod_min = 0
    return mod_min
print(main(L,R))
### BUGGY CODE ###

n,q = list(map(int, input().split()))
queue = []
for i in range(n):
    pair = input().split()
    queue.append( (pair[0], int(pair[1])))

time = 0
while queue != []:
    p,t = queue[0]
    queue = queue[1:]
    if t<=q:
        time += t
        print(p,time)
    else:
        time += q
        queue.append((p,t-q))

### FIXED CODE ###

import collections
n,q = map(int, input().split())
queue = collections.deque(maxlen=100000)

for i in range(n):
    p,t = input().split()
    queue.append([p, int(t)])

time = 0
while queue:
    p,t = queue.popleft()
    if t<=q:
        time += t
        print(p,time)
    else:
        time += q
        queue.append([p,t-q])
### BUGGY CODE ###

N = int(input())
a = list( map(int, input().split() ) )
kai = 1
M = 10**9+7
result = 0
for i in range(1,N):
    kai *= i
    
for i in range(N-1):
    result += kai * (a[N-1] - a[i]) // ( i+1 )
    result = result%M

print( result )

### FIXED CODE ###

N = int(input())
d = list( map(int, input().split() ) )
kai = 1
mod = 10**9+7
result = 0

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

for i in range(1,N):
    kai = (kai%mod)*i

for i in range(N-1):    
    result += ( kai * (d[N-1] - d[i]) * modinv(i+1) ) % mod 

print( result%mod )