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

N,M = map(int,input().split(' '))
ans = 1
P = M//N
for i in range(P):
    ans = P - i

    if (M - ans * N)%ans == 0:
        break
print(ans)

### FIXED CODE ###

import math


def divisor(num):
    if num < 0:
        return [0,]
    elif num == 1:
        return [1,]
    else:
        divisor_list =[1,]
        for i in range(2, int(math.sqrt(num) + 1)):
            if num % i== 0:
                divisor_list.append(i)
        return divisor_list


N,M = map(int,input().split(' '))
P = M // N
divisor_list = divisor(M)

for i in reversed(range(len(divisor_list))):
    num = M // divisor_list[i]
    divisor_list.append(num)

for i in reversed(range(len(divisor_list))):
    if divisor_list[i] <= P:
        print(divisor_list[i])
        break
### BUGGY CODE ###

def addbit(i):
    i += 1
    while i <= N:
        BIT[i] += 1
        i += i & (-i)
def getsum(i):
    ret = 0
    i += 1
    while i != 0:
        ret += BIT[i]
        i -= i&(-i)
    return ret
def bit(L):
    global BIT
    BIT=[0] * (N+1)
    re = 0
    for i, l in enumerate(L):
        re += i - getsum(l)
        addbit(l)
    return re
def calc(Z):
    Z.sort()
    l, r, lc, rc = -1<<28, 1<<28, N*(N-1)//4+1, N*(N-1)//4+1
    f = 1
    while r - l > 0.000000001:
        m = (l+r) / 2 if f else (l * rc + r * lc) / (lc + rc)
        A = [a&((1<<16)-1) for a in sorted([(int((s*m+t)*2**40)<<16)+i for i, (s, t) in enumerate(Z)])]
        c = bit(A)
        if c > N*(N-1)//4:
            l = m
            lc = (c - N*(N-1)//4) * 2
        else:
            r = m
            rc = (N*(N-1)//4 - c) * 2 + 1
        f ^= 1
    return l

N = int(input())
X, Y = [], []
for _ in range(N):
    a, b, c = map(int, input().split())
    X.append((-a/b, c/b))
    Y.append((-b/a, c/a))
print(calc(X), calc(Y))

### FIXED CODE ###

def addbit(i):
    i += 1
    while i <= N:
        BIT[i] += 1
        i += i & (-i)
def getsum(i):
    ret = 0
    i += 1
    while i != 0:
        ret += BIT[i]
        i -= i&(-i)
    return ret
def bit(L):
    global BIT
    BIT=[0] * (N+1)
    re = 0
    for l in L:
        re += getsum(l)
        addbit(l)
    return N*(N-1)//2 - re
def calc(Z):
    Z.sort()
    l, r, lc, rc = -1<<28, 1<<28, N*(N-1)//4+1, N*(N-1)//4+1
    f = 1
    while (r - l) / max(abs(l), 1) > 0.000000001:
        m = (l+r) / 2 if f else (l * rc + r * lc) / (lc + rc)
        A = [a&((1<<16)-1) for a in sorted([(int((s*m+t)*2**40)<<16)+i for i, (s, t) in enumerate(Z)])]
        c = bit(A)
        if c > N*(N-1)//4:
            l = m
            lc = (c - N*(N-1)//4) * 2
        else:
            r = m
            rc = (N*(N-1)//4 - c) * 2 + 1
        f ^= 1
    return l

N = int(input())
X, Y = [], []
for _ in range(N):
    a, b, c = map(int, input().split())
    X.append((-a/b, c/b))
    Y.append((-b/a, c/a))
print(calc(X), calc(Y))
### BUGGY CODE ###

from collections import Counter
from math import factorial
N = int(input())
A = list(map(int, input().split()))

allCount = 0
c = Counter(A)

for i, v in c.items():
    if (v == 1):
        continue
    else:
        allCount += factorial(v) // factorial(2) // factorial(v - 2)


if (allCount == 0):
    for i in range(N):
        print(0)
    exit()

for i in range(N):
    a = allCount
    num = c[A[i]] - 1
    if (num == 1 or num == 0):
        print(allCount - num)
        continue
    old = factorial(c[A[i]]) // factorial(2) // factorial(c[A[i]] - 2)
    count = factorial(num) // factorial(2) // factorial(num - 2)
    print(a - old + count)


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))

allCount = 0
c = Counter(A)

for i, v in c.items():
    if (v == 1):
        continue
    else:
        allCount += v * (v - 1) // 2


if (allCount == 0):
    for i in range(N):
        print(0)
    exit()

for i in range(N):
    a = allCount
    num = c[A[i]] - 1
    if (num == 1 or num == 0):
        print(allCount - num)
        continue
    old = c[A[i]] * (c[A[i]] - 1) // 2
    count = num * (num - 1) // 2
    print(a - old + count)
### BUGGY CODE ###

n,m = map(int,input().split())
ans = 1
for i in range(2,m//n + 1):
  if m % i == 0 and m // i >= n:
    ans = i
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
ans = 0
for i in range(1,int(m**0.5)+1):
  if m % i == 0 and m // i >= n:
    ans = max(ans,i)
  if m % i == 0 and i >= n:
    ans = max(ans,m//i)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
MAX_VAL = 10000
OFFSET = MAX_VAL // 2

h, w = [int(item) for item in input().split()]
a = []
b = []
for i in range(h):
    line = [int(item) for item in input().split()] + [0]
    a.append(line)
a.append([0] * (w + 1))
for i in range(h):
    line = [int(item) for item in input().split()] + [0]
    b.append(line)
b.append([0] * (w + 1))

# dp[height][width][bias]
dp = [[set() for _ in range(w+1)] for _ in range(h+1)] 
dp[0][0].add(a[0][0] - b[0][0])
dp[0][0].add(b[0][0] - a[0][0])
for i in range(h):
    for j in range(w):
        diffr = a[i][j+1] - b[i][j+1]
        diffd = a[i+1][j] - b[i+1][j]
        for item in dp[i][j]:
            # Move right
            dp[i][j+1].add(item+diffr)
            dp[i][j+1].add(item-diffr)
            # Move down
            dp[i+1][j].add(item+diffd)
            dp[i+1][j].add(item-diffd)
ans = 10**9
for item in dp[h-1][w-1]:
    ans = min(ans, abs(item))
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MAX_VAL = 12800
 
h, w = [int(item) for item in input().split()]
a = []
b = []
for i in range(h):
    line = [int(item) for item in input().split()] + [0]
    a.append(line)
a.append([0] * (w + 1))
for i in range(h):
    line = [int(item) for item in input().split()] + [0]
    b.append(line)
b.append([0] * (w + 1))
 
# dp[height][width] bitset
dp = [[0] * (w+1) for _ in range(h+1)] 
delta = abs(a[0][0] - b[0][0])
dp[0][0] |= 1 << (MAX_VAL + delta)
dp[0][0] |= 1 << (MAX_VAL - delta)
for i in range(h):
    for j in range(w):
        diffr = abs(a[i][j+1] - b[i][j+1])
        diffd = abs(a[i+1][j] - b[i+1][j])
        # Move right
        add_delta = dp[i][j] << diffr
        sub_delta = dp[i][j] >> diffr
        dp[i][j+1] |= add_delta | sub_delta
        # Move down
        add_delta = dp[i][j] << diffd
        sub_delta = dp[i][j] >> diffd
        dp[i+1][j] |= add_delta | sub_delta
ans = MAX_VAL
for i in range(MAX_VAL * 2):
    if dp[h-1][w-1] & (1 << i):
        ans = min(ans, abs(i - MAX_VAL))
print(ans)
### BUGGY CODE ###

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

  
for i in range(n):
  print(a.count(i+1))




### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
c=[0]*n
for i in range(n-1):
  t=a[i]
  c[t-1]+=1
  
for i in range(n):
  print(c[i])
### BUGGY CODE ###

import math


def num_divisors_trial_division(n):
    num = 0
    for i in range(1, int(math.sqrt(n) + 1e-9) + 1):
        if n % i == 0:
            num += 1
            if n != i ** 2:
                num += 1

    return num

N = int(input())
summ = 0
for i in range(1, N):
    temp = num_divisors_trial_division(i)
#    print(temp)
    summ += temp

print(summ)

### FIXED CODE ###

import math


def num_divisors_table(n):
    table = [0] * (n + 1)

    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            table[j] += 1

    return table

N = int(input())


summ = 0

summ = sum(num_divisors_table(N-1))
print(summ)
### BUGGY CODE ###

import sys

a = []
for l in sys.stdin:
    if l == '\n':
        break
    else :
        a.append(l)

target = a[int(a[0])]
num = 0
for i in range(1, len(a) - 1):
    for j in range(i + 1, len(a)):
        flag = False
        iStrSorted = ''.join(sorted(a[i]))
        jStrSorted = ''.join(sorted(a[j]))
        if iStrSorted==jStrSorted:
            flag = True
        else:
            flag = False
        if flag:
            num = num + 1
print(num)

### FIXED CODE ###

import sys
import collections

n=int(input())
a=[''.join(sorted(input())) for _ in range(n)]

ans = 0
for v in collections.Counter(a).values():
    if v != 1:
        ans += v * (v - 1) // 2
print(ans)
### BUGGY CODE ###

def main():
    S = input()
    if len(set(S)) == 1:
        print(0)
    else:
        ans = 0
        while len(set(S)) != 1:
            if S[-1] == 'B':
                x = 'W'
            else:
                x = 'B'

            S = S + x
            S = S[::-1]
            new_s = x
            flag = False
            for si in S[1:]:
                if not flag and si != x:
                    new_s += x
                elif not flag and si == x:
                    new_s += x
                    flag = True
                else:
                    new_s += si
            S = new_s
            ans += 1
            # print(S)
        print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    S = input()
    if len(set(S)) == 1:
        print(0)
    else:
        s2 = ''
        prev = ''
        for si in S:
            if si == prev:
                pass
            else:
                s2 += si
            prev = si
        
        print(len(s2) - 1)


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

a=int(input())
ans=0
while a//10!=0:
    ans+=a%10
    a=a//10
ans+=a
if ans%9==0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

a=int(input())
if a%9==0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

from collections import Counter

n = int(input())
A = [int(i) for i in input().split()]
C = Counter(A)
a, b, c = [C[i] for i in range(3, 0, -1)]

DP = [[[-1] * (a + b + c + 1) for i in range(a + b + 1)] for j in range(a + 1)]
DP[0][0][0] = 0

def dfs(i, j, k):
    if DP[i][j][k] != -1:
        return DP[i][j][k]
    
    DP[i][j][k] = 1
    DP[i][j][k] += i / n * dfs(i - 1, j + 1, k) if i != 0 else 0
    DP[i][j][k] += j / n * dfs(i, j - 1, k + 1) if j != 0 else 0
    DP[i][j][k] += k / n * dfs(i, j, k - 1) if k != 0 else 0
    DP[i][j][k] *= n / (i + j + k)

    return DP[i][j][k]

print(dfs(a, b, c))

### FIXED CODE ###

from collections import Counter

n = int(input())
A = [int(i) for i in input().split()]
C = Counter(A)
a, b, c = [C[i] for i in range(3, 0, -1)]

DP = [[[-1] * (a + b + c + 1) for i in range(a + b + 1)] for j in range(a + 1)]
DP[0][0][0] = 0

for i in range(a + 1):
    for j in range(a + b - i + 1):
        for k in range(a + b + c - i - j + 1):
            if i == j == k == 0:
                continue
            DP[i][j][k] = 1
            if i > 0: DP[i][j][k] += i / n * DP[i - 1][j + 1][k]
            if j > 0: DP[i][j][k] += j / n * DP[i][j - 1][k + 1]
            if k > 0: DP[i][j][k] += k / n * DP[i][j][k - 1]
            DP[i][j][k] *= n / (i + j + k)

print(DP[a][b][c])
### BUGGY CODE ###

f = lambda : map(int,input().split())
n, q = f()
s = input()
for _ in range(q):
  l, r = f()
  print(s[l-1:r].count('AC'))

### FIXED CODE ###

f = lambda : map(int,input().split())
n, q = f()
s = input()

cnt = 0
ln = [0]*n
for i in range(1,n):
  if s[i-1:i+1] == 'AC':
    cnt += 1
  ln[i] = cnt
for _ in range(q):
  l, r = f()
  print(ln[r-1]-ln[l-1])
### BUGGY CODE ###

n = int(input())
s = input()
r, g, b = s.count("R"), s.count("G"), s.count("B")
cnt = 0
for i in range(n):
    for j in range(i + 1, n):
        try:
            k = j + (j - i)
            if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
                cnt += 1
        except:
            pass
print(r * g * b - cnt)

### FIXED CODE ###

n = int(input())
s = input()
r, g, b = s.count("R"), s.count("G"), s.count("B")
ans = r * g * b
for i in range(n):
    for j in range(i + 1, n):
        k = j + (j - i)
        if k >= n:
            break
        if s[i] != s[j] != s[k] != s[i]:
            ans -= 1
print(ans)
### BUGGY CODE ###

n = int(input())

d = list(map(int, input().split()))

d.sort()

m = 0



for a in range(n-2):
	for b in range(a+1,n-1):
		for c in range(b+1,n):
			if d[c]==d[a]:
				m -= 1
			if d[c]<d[b]+d[a]:
				m += 1
			else:
				break
			

print(m)

### FIXED CODE ###

import bisect

n = int(input())
d = list(map(int, input().split()))
d.sort()

m = 0

for a in range(n-2):
	for b in range(a+1,n-1):
		m+=bisect.bisect_left(d,d[a]+d[b])-1-b

print(m)
### BUGGY CODE ###

N = int(input())
nums = [int(e) for e in input().split()]
nums.sort()
t=1
ans = 1
for i in range(0,9):
    t = t*10
t+=7
if(N%2)==1:
    if(nums.count(0) == 1):
        for i in range(2,N,2):
            if(nums.count(i))==2:
                ans = (ans * 2)%t
            else:
                print('0')
                break
        else:
            print(ans)
    else:
        print('0')
else:
    for i in range(1,N,2):
        if(nums.count(i))==2:
            ans = (ans *2)%t
        else:
            print('0')
            break
    else:
        print(ans)

### FIXED CODE ###

N = int(input())
nums = [int(e) for e in input().split()]
nums.sort()
t=1
ans = 1
t = 10**9
t+=7
i=1
k=0
if(N%2)==1:
    if(nums.count(0) == 1):
        while(i<N):
            if nums[i] == nums[i+1]:
                i+=2
                ans = (ans *2)%t
                continue
            else:
                print('0')
                break
        else:
            print(ans)
    else:
        print('0')
else:
    while(k<N):
        if nums[k] == nums[k+1]:
            k += 2
            ans = (ans * 2)%t
            continue
        else:
            print('0')
            break
    else:
        print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
*A,=map(int,input().split())
for i in range(0,N-K):
    x = 1
    y = 1
    for j in range(K):
        x*=A[i+j]
        y*=A[i+j+1]
    if (y<=x):
        print('No')
    else:
        print('Yes')

### FIXED CODE ###

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

for i in range(0,N-K):
    print('Yes' if 1<A[i+K]/A[i] else 'No')
### BUGGY CODE ###

n = int(input())
L = sum([list(map(int, input().split())) for i in range(n)], [])
next = 1
count = 0
while True:
  if next == 2:
    print(count)
    exit()
  elif count > n:
    print(-1)
    exit()
  else:
    next = L[next-1]
    count += 1

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
cur = 1
cnt = 0
while True:
    if cur == 2:
        print(cnt)
        exit()
    elif cnt > n:
        print(-1)
        exit()
    else:
        cur = a[cur - 1]
        cnt += 1
### BUGGY CODE ###

import sys

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

A.sort()

if len(A) == 1:
    A[0] //= (2 ** M)
    print(sum(A))
    sys.exit()

for m in range(M):
    *A, a = A

    a //= 2

    for i, x in reversed(list(enumerate(A))):
        if x < a:
            A.insert(i+1, a)
            break
    else:
        A = [a] + A

print(sum(A))


### FIXED CODE ###

import sys
import heapq

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

if len(A) == 1:
    A[0] //= (2 ** M)
    print(sum(A))
    sys.exit()

h = [(1/a, a) for a in A]
heapq.heapify(h)

for m in range(M):
    x = heapq.heappop(h)
    _, a = x

    a //= 2

    heapq.heappush(h, (1/a if a > 0 else float('inf'), a))

print(sum([a for _, a in h]))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
A_cnt = [0] * 100001
A_sum = 0

for a in A:
    A_cnt[a]+=1

for _ in range(Q):
    B, C = map(int, input().split())
    A_cnt[C] = A_cnt[C] + A_cnt[B]
    A_cnt[B] = 0

    for i, x in enumerate(A_cnt):
        if A_cnt[i] > 0:
            A_sum = A_sum + (i * A_cnt[i])
    print(A_sum)
    A_sum = 0

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
A_cnt = [0] * 100001
A_sum = 0

# 各数値の数を数えておく
for a in A:
    A_cnt[a]+=1
    # ついでに現時点の総和も出しておく
    A_sum+=a

for _ in range(Q):
    B, C = map(int, input().split())
    A_cnt[C] = A_cnt[C] + A_cnt[B]
    A_sum = A_sum + ((C-B) * A_cnt[B])
    A_cnt[B] = 0
    print(A_sum)
### BUGGY CODE ###

K,S = map(int,raw_input().split())
con = 0
for X in range(0,K+1):
        for Y in range(0,K+1):
                for Z in range(0,K+1):
                        if X+Y+Z == S:
                               con+=1 
print con

### FIXED CODE ###

K,S = map(int,raw_input().split())
con = 0
for X in range(0,K+1):
        for Y in range(0,K+1):
                if (S-(X+Y)) <= K and S-(X+Y) >= 0:
                        con +=1
print con
### BUGGY CODE ###

from math import gcd
K = int(input())
i = 0

def gcd3(a,b,c):
    d = gcd(a,b)
    e = gcd(d,c)
    return(e)

for a in range(1,K + 1):
    for b in range(1,K + 1):
        for c in range(1,K + 1):
            j = gcd3(a,b,c)
            i = i + j

print(i)

### FIXED CODE ###

from math import gcd
K = int(input())
i = 0
p = 0

def gcd3(a,b,c):
    d = gcd(a,b)
    e = gcd(d,c)
    return(e)

for a in range(1,K + 1):
    for b in range(a + 1,K + 1):
        for c in range(b + 1,K + 1):
            j = gcd3(a,b,c)
            i = i + j

for a in range(1,K + 1):
    for b in range(a + 1,K + 1):
        o = gcd(a,b)
        p = p + o

d = int((1 + K)* K /2)

print(6*i + d + 6*p)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
cd = 0
count = 0
while(True) :
    cd = a[cd] - 1
    count += 1
    if cd == 1 :
        print(count)
        break
    if cd == 0 :
        print(-1)
        break

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
cd = 0
count = 0
while(True) :
    cd = a[cd] - 1
    count += 1
    if cd == 1 :
        print(count)
        break
    if count >= n :
        print(-1)
        break
### BUGGY CODE ###

from collections import deque

n,c,k = map(int, input().split())
t = [int(input()) for _ in range(n)]

tk = [(ti, ti+k) for ti in t]
tk.sort(key=lambda x:x[1])
tk = deque(tk)
#print(tk)


ans = 0
# tkが尽きるまで
while tk:
    _, bus = tk[0]
    
    # バスの時刻より早く来ている客をカウント
    cnt = 0
    while (tk[cnt][0] <= bus):
        cnt += 1
        
        if cnt == len(tk):
            break
        
        
    # バスの定員もしくはいる人数を乗せていく
    for _ in range(min(cnt,c)):
        tk.popleft()
    
    ans += 1
        
print(ans)
    

### FIXED CODE ###

from collections import deque

n,c,k = map(int, input().split())
t = [int(input()) for _ in range(n)]

tk = [(ti, ti+k) for ti in t]
tk.sort(key=lambda x:x[1])
tk = deque(tk)
#print(tk)


ans = 0
# tkが尽きるまで
while tk:
    _, bus = tk[0]
    
    # バスの時刻より早く来ている客をカウント
    cnt = 0
    while (tk[cnt][0] <= bus):
        cnt += 1
        
        if cnt == len(tk):
            break
        
        
    # バスの定員もしくはいる人数を乗せていく
    for _ in range(min(cnt,c)):
        tk.popleft()
    
    ans += 1
        
print(ans)
### BUGGY CODE ###

def g(field,x,y,h,w,ans):
     cnt = 1
     flag = h+w+1
     while cnt < flag:
          for i in range(0,cnt+1):
               j = cnt - i
               if i == 0:
                    search = [[x,y+j],[x,y-j]]
               elif j == 0:
                    search = [[x+i,y],[x-i,y]]
               else:
                    search = [[x+i,y+j],[x-i,y+j],[x+i,y-j],[x-i,y-j]]
               for p in search:
                    if (0<=p[0]) and (p[0]<=w-1) and (0<=p[1]) and (p[1]<=h-1):
                         if field[p[1]][p[0]] == "#":
                              return cnt
                         if ans[p[1]][p[0]] != "#":
                              flag == min(flag,cnt + ans[p[1]][p[0]])
          cnt += 1
     return flag


def f():
     answer = 0
     h,w = map(int,input().split())
     field = []
     for i in range(h):
          field.append(list(input()))
     ans = [["#"]*w for i in range(h)]
     for i in range(0,h):
          for j in range(0,w):
               if field[i][j] == "#":
                    ans[i][j] = 0
               elif field[i][j] == ".":
                    ans[i][j] = g(field,j,i,h,w,ans)
                    answer = max(answer,ans[i][j])
     print(answer)
     return
f()

### FIXED CODE ###

def f():
     h,w = map(int,input().split())
     field = []
     for i in range(h):
          field.append(list(input()))
          
     que = []
     for i in range(h):
          for j in range(w):
               if field[i][j] == "#":
                    que.append([i,j])
     if que == []:
          print(0)
          return
     cnt = 0
     while que != []:
          que1 = []
          for p in que:
               for v in [[1,0],[0,1],[-1,0],[0,-1]]:
                    newx,newy = p[1]+v[1],p[0]+v[0]
                    if (0<=newx) and (newx<w) and (0<=newy) and (newy<h):
                         if field[newy][newx] == ".":
                              field[newy][newx] = "#"
                              que1.append([newy,newx])
          que = que1
          cnt += 1
     print(cnt-1)
     return
f()
### BUGGY CODE ###

N,K = map(int,input().rstrip().split(" "))
p = list(map(int,input().rstrip().split(" ")))
ans = 0
for i in range(N - K + 1):
  karians = 0
  for i2 in range(K):
    karians += p[i + i2] + 1
  if ans <= karians:
    ans = karians
print(ans / 2)

### FIXED CODE ###

N,K = map(int,input().rstrip().split(" "))
p = list(map(int,input().rstrip().split(" ")))
karians = K
for i in range(K):
  karians += p[i]
ans = karians
for i in range(N - K):
  karians -= p[i]
  karians += p[i + K]
  if ans < karians:
    ans = karians
print(ans / 2)
### BUGGY CODE ###

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

"""
とりあえず何通りあるかを数える：各頂点を通る時点での場合の数
最後に衝突する方法を除外する：頂点での衝突、辺での衝突
辺での衝突：距離を見れば分かる
"""

MOD = 10 ** 9 + 7

N,M = map(int,input().split())
S,T = map(int,input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u,v,d = map(int,input().split())
    graph[u].append((v,d))
    graph[v].append((u,d))

def dijkstra(S):
    # 距離、パスの個数を返す
    INF = 10 ** 15
    dist = [INF] * (N+1)
    cnt_path = [0] * (N+1)
    cnt_path[0] = 1
    q = [(0,S,0)] # 距離、場所、直前
    while q:
        d,x,pred = heappop(q)
        if dist[x] < d:
            continue
        if dist[x] == d:
            cnt_path[x] += cnt_path[pred]
            cnt_path[x] %= MOD
            continue
        dist[x] = d
        cnt_path[x] = cnt_path[pred]
        for y,dy in graph[x]:
            if d + dy > dist[y]:
                continue
            heappush(q,(d+dy,y,x))
    return dist, cnt_path

dist_S, cnt_path_S = dijkstra(S)
dist_T, cnt_path_T = dijkstra(T)

D = dist_S[T]
# 最短路の組
answer = cnt_path_S[T] * cnt_path_T[S]
# 頂点での衝突
for x in range(1,N+1):
    if dist_S[x] == dist_T[x]:
        t = cnt_path_S[x] * cnt_path_T[x] % MOD
        answer -= t * t % MOD
# 辺での衝突。S側がx、T側がy
for x in range(1,N+1):
    for y,d in graph[x]:
        dx = dist_S[x]
        dy = dist_T[y]
        if dx + dy + d == D and dx + d > dy and dy + d > dx:
            t = cnt_path_S[x] * cnt_path_T[y] % MOD
            answer -= t * t % MOD

answer %= MOD
print(answer)



### FIXED CODE ###

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

"""
とりあえず何通りあるかを数える：各頂点を通る時点での場合の数
最後に衝突する方法を除外する：頂点での衝突、辺での衝突
辺での衝突：距離を見れば分かる
"""

MOD = 10 ** 9 + 7

N,M = map(int,input().split())
S,T = map(int,input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u,v,d = map(int,input().split())
    graph[u].append((v,d))
    graph[v].append((u,d))

def dijkstra(S):
    # 距離、パスの個数を返す
    INF = 10 ** 15
    dist = [INF] * (N+1)
    cnt_path = [0] * (N+1)
    cnt_path[S] = 1
    q = [(0,S)] # 距離、場所
    while q:
        d,x = heappop(q)
        if dist[x] < d:
            continue
        dist[x] = d
        for y,dy in graph[x]:
            if d + dy > dist[y]:
                continue
            if d + dy == dist[y]:
                cnt_path[y] += cnt_path[x]
                continue
            cnt_path[y] = cnt_path[x]
            dist[y] = d + dy
            heappush(q,(d+dy,y))
    return dist, cnt_path

dist_S, cnt_path_S = dijkstra(S)
dist_T, cnt_path_T = dijkstra(T)

D = dist_S[T]
# 最短路の組
answer = cnt_path_S[T] * cnt_path_T[S]
# 頂点での衝突
for x in range(1,N+1):
    if dist_S[x] == dist_T[x]:
        t = cnt_path_S[x] * cnt_path_T[x] % MOD
        answer -= t * t % MOD
# 辺での衝突。S側がx、T側がy
for x in range(1,N+1):
    for y,d in graph[x]:
        dx = dist_S[x]
        dy = dist_T[y]
        if dx + dy + d == D and dx + d > dy and dy + d > dx:
            t = cnt_path_S[x] * cnt_path_T[y] % MOD
            answer -= t * t % MOD

answer %= MOD
print(answer)