Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
readline = open(0).readline
write = open(1, 'w').write

N = int(readline())
P = [list(map(int, readline().split())) for i in range(N)]
P.sort(key=lambda x: x[0]+x[1])

L = 10**5
dp = [0]*L
for w, s, v in P:
    for i in range(s+w, w-1, -1):
        dp[i] = max(dp[i], dp[i-w] + v)
write("%d\n" % max(dp))

Fixed submission:
N = int(input())
P = [list(map(int, input().split())) for i in range(N)]
P.sort(key=lambda x: x[0]+x[1])

L = 10**5
dp = [0]*L
for w, s, v in P:
    for i in range(s, -1, -1):
        dp[i+w] = max(dp[i+w], dp[i] + v)
print(max(dp))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = [list(map(int, input().split())) for i in range(N)]

i = 0
while 1:
    if P[0][2] > 0:
        break
    i += 1
x0, y0, h0 = P[i]
for cy in range(101):
    for cx in range(101):
        h = h0 + abs(cx - x0) + abs(cy - y0)
        for x, y, h1 in P:
            if h1 != max(h - abs(cx - x) - abs(cy - y), 0):
                break
        else:
            print(cx, cy, h)
            exit(0)
exit(1)


Fixed submission:
N = int(input())
P = [list(map(int, input().split())) for i in range(N)]

i = 0
while 1:
    if P[i][2] > 0:
        break
    i += 1
x0, y0, h0 = P[i]
for cy in range(101):
    for cx in range(101):
        h = h0 + abs(cx - x0) + abs(cy - y0)
        for x, y, h1 in P:
            if h1 != max(h - abs(cx - x) - abs(cy - y), 0):
                break
        else:
            print(cx, cy, h)
            exit(0)
exit(1)

Buggy python submission (verdict: Runtime Error):
N = int(input())
P = [list(map(int, input().split())) for i in range(N)]

x0, y0, h0 = P[0]
for cy in range(101):
    for cx in range(101):
        h = h0 + abs(cx - x0) + abs(cy - y0)
        for x, y, h1 in P[1:]:
            if h != h1 + abs(cx - x) + abs(cy - y):
                break
        else:
            print(cx, cy, h)
            exit(0)
exit(1)


Fixed submission:
N = int(input())
P = [list(map(int, input().split())) for i in range(N)]

i = 0
while 1:
    if P[i][2] > 0:
        break
    i += 1
x0, y0, h0 = P[i]
for cy in range(101):
    for cx in range(101):
        h = h0 + abs(cx - x0) + abs(cy - y0)
        for x, y, h1 in P:
            if h1 != max(h - abs(cx - x) - abs(cy - y), 0):
                break
        else:
            print(cx, cy, h)
            exit(0)
exit(1)
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop, heappushpop
N = int(input())
*A, = map(int, input().split())

def update(v, que):
    p, q = que
    if v == p or v == q:
        return
    heappushpop(que, v)

memo = [None]*(2**N)
memo[0] = [(0, -1), (A[0], 0)]
ma = 0; ans = []
for i in range(1, 2**N):
    res = [(0, -1), (A[i], i)]
    for j in range(N):
        if (i >> j) & 1 == 0:
            continue
        p, q = memo[i ^ (1 << j)]
        update(p, res)
        update(q, res)
    p, q = memo[i] = res
    ma = max(ma, p[0] + q[0])
    ans.append(ma)
print(*ans, sep='\n')


Fixed submission:
from heapq import heappush, heappop, heappushpop
N = int(input())
*A, = map(int, input().split())

def update(v, que):
    p, q = que
    if v == p or v == q:
        return
    heappushpop(que, v)

memo = [None]*(2**N)
memo[0] = [(0, -1), (A[0], 0)]
ma = 0; ans = []
for i in range(1, 2**N):
    res = [(0, -1), (A[i], i)]
    for j in range(N):
        if (i >> j) & 1 == 0:
            continue
        p, q = memo[i ^ (1 << j)]
        update(p, res)
        update(q, res)
    p, q = memo[i] = res
    ma = max(ma, p[0] + q[0])
    ans.append(ma)
print(*ans, sep='\n')
Buggy python submission (verdict: Time Limit Exceeded):
N, C = map(int, input().split())
D = [list(map(int, input().split())) for i in range(C)]
c = [list(map(int, input().split())) for i in range(N)]
col = [[0]*3 for i in range(C)]
for i in range(N):
    for j in range(N):
        p = c[i][j]-1
        for k in range(C):
            col[k][(i+j)%3] += D[p][k]
ans = 10**18
for i in range(C):
    for j in range(C):
        if i == j:
            continue
        for k in range(C):
            if i == k or j == k:
                continue
            ans = min(ans, col[i][0] + col[j][1] + col[k][2])
print(ans)

Fixed submission:
N, C = map(int, input().split())
D = [list(map(int, input().split())) for i in range(C)]
c = [list(map(int, input().split())) for i in range(N)]
col = [[0]*3 for i in range(C)]
for i in range(N):
    for j in range(N):
        p = c[i][j]-1
        for k in range(C):
            col[k][(i+j)%3] += D[p][k]
ans = 10**18
for i in range(C):
    for j in range(C):
        if i == j:
            continue
        for k in range(C):
            if i == k or j == k:
                continue
            ans = min(ans, col[i][0] + col[j][1] + col[k][2])
print(ans)
Buggy python submission (verdict: Runtime Error):
N, A, B, K = map(int, input().split())
MOD = 998244353

fact = [1]*(N+1)
rev = [1]*(N+1)
for i in range(1, N+1):
    fact[i] = fact[i-1]*i % MOD
    rev[i] = pow(fact[i], MOD-2, MOD)

ans = 0
for a in range(N+1):
    if (K - a*A) >= 0 and (K - a*A) % B == 0:
        b = (K - a*A) // B
        ans += rev[a]*rev[N-a] * rev[b]*rev[N-b]
        ans %= MOD
ans *= fact[N]*fact[N]
ans %= MOD
print(ans)



Fixed submission:
N, A, B, K = map(int, input().split())
MOD = 998244353

fact = [1]*(N+1)
rev = [1]*(N+1)
for i in range(1, N+1):
    fact[i] = fact[i-1]*i % MOD
    rev[i] = pow(fact[i], MOD-2, MOD)

ans = 0
for a in range(N+1):
    if (K - a*A) >= 0 and (K - a*A) % B == 0:
        b = (K - a*A) // B
        if not 0 <= b <= N:
            continue
        ans += rev[a]*rev[N-a] * rev[b]*rev[N-b]
        ans %= MOD
ans *= fact[N]*fact[N]
ans %= MOD
print(ans)
Buggy python submission (verdict: Runtime Error):
X = int(input())
def f():
    for y in range(2, X.bit_length()):
        x = 0
        while (x+1)**y <= X:
            x += 1
        if x**y <= X:
            yield x**y
print(max(f()))


Fixed submission:
X = int(input())
def f():
    yield 1
    for y in range(2, X.bit_length()):
        x = 0
        while (x+1)**y <= X:
            x += 1
        if x**y <= X:
            yield x**y
print(max(f()))
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
K = int(input())

from heapq import heappush, heappop

Q = set()
u = set()
N = len(s)
for i in range(N):
    for j in range(i+1, N+1):
        ss = s[i:j]
        if ss in u:
            continue
        u.add(ss)
        Q.add(ss)
        if len(Q) > K:
            Q.remove(max(Q))
l = sorted(Q)
print(l[K-1])


Fixed submission:
s = input()
K = int(input())

from heapq import heappush, heappop

Q = set()
u = set()
N = len(s)
for i in range(N):
    for j in range(i+1, i+K+1):
        ss = s[i:j]
        if ss in u:
            continue
        u.add(ss)
        Q.add(ss)
        if len(Q) > K:
            Q.remove(max(Q))
l = sorted(Q)
print(l[K-1])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = [input() for i in range(N)]
T = [list(s[i] for s in S) for i in range(N)]

def check(A, B):
    for i in range(N):
        si = S[A+i-N]
        ti = T[B+i-N]
        for j in range(i+1, N):
            if si[B+j-N] != ti[A+j-N]:
                return 0
    return 1

ans = 0
for i in range(N):
    ans += N*check(0, i)
print(ans)

Fixed submission:
N = int(input())
S = [input() for i in range(N)]

def check(A, B):
    for i in range(N):
        for j in range(i+1, N):
            if S[(A+i)%N][(B+j)%N] != S[(A+j)%N][(B+i)%N]:
                return 0
    return 1

ans = 0
for i in range(N):
    ans += N*check(0, i)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = [input() for i in range(N)]

def check(A, B):
    for i in range(N):
        for j in range(i+1, N):
            if S[(A+i)%N][(B+j)%N] != S[(A+j)%N][(B+i)%N]:
                return 0
    return 1

ans = 0
for i in range(N):
    ans += N*check(0, i)
print(ans)

Fixed submission:
N = int(input())
S = [input() for i in range(N)]

def check(A, B):
    for i in range(N):
        for j in range(i+1, N):
            if S[(A+i)%N][(B+j)%N] != S[(A+j)%N][(B+i)%N]:
                return 0
    return 1

ans = 0
for i in range(N):
    ans += N*check(0, i)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# seishin.py
N = int(input())
MOD = 10**9 + 7

fact = [1]*(N+1)

for i in range(1, N+1):
    fact[i] = r = i*fact[i-1] % MOD

ans = cnt = 0
for K in range((N+1)//2, N):
    res = fact[K]*fact[K-1]*pow(fact[2*K-N], MOD-2, MOD) % MOD
    ans += (res - cnt) * K % MOD
    cnt = res
    ans %= MOD
print(ans)


Fixed submission:
# seishin.py
N = int(input())
MOD = 10**9 + 7

fact = [1]*(N+1)
rfact = [1]*(N+1)

for i in range(1, N+1):
    fact[i] = r = i*fact[i-1] % MOD
    rfact[i] = pow(r, MOD-2, MOD)

ans = cnt = 0
for K in range((N+1)//2, N):
    res = fact[K]*fact[K-1]*rfact[2*K-N] % MOD
    ans += (res - cnt) * K % MOD
    cnt = res
    ans %= MOD
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
# seishin.py
N = int(input())
MOD = 10**9 + 7

fact = [1]*(N+1)
rfact = [1]*(N+1)

for i in range(1, N+1):
    fact[i] = r = i*fact[i-1] % MOD
    rfact[i] = pow(r, MOD-2, MOD)

ans = 0
cnt = 0
for K in range(1, N):
    if not K >= N-K >= 1:
        continue
    res = fact[K]*fact[K-1]*rfact[2*K-N] % MOD
    ans += (res - cnt) * K % MOD
    cnt = res
    ans %= MOD
print(ans)

Fixed submission:
# seishin.py
N = int(input())
MOD = 10**9 + 7

fact = [1]*(N+1)
rfact = [1]*(N+1)

for i in range(1, N+1):
    fact[i] = r = i*fact[i-1] % MOD
    rfact[i] = pow(r, MOD-2, MOD)

ans = cnt = 0
for K in range((N+1)//2, N):
    res = fact[K]*fact[K-1]*rfact[2*K-N] % MOD
    ans += (res - cnt) * K % MOD
    cnt = res
    ans %= MOD
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
# seishin.py
N = int(input())
MOD = 10**9 + 7

fact = [1]*(N+1)
rfact = [1]*(N+1)

for i in range(1, N+1):
    fact[i] = r = i*fact[i-1] % MOD
    rfact[i] = pow(r, MOD-2, MOD)

ans = 0
cnt = 0
for K in range(1, N):
    if not K >= N-K >= 1:
        continue
    res = fact[K]*fact[K-1]*rfact[2*K-N] % MOD
    ans += (res - cnt) * K % MOD
    cnt = res
print(ans % MOD)

Fixed submission:
# seishin.py
N = int(input())
MOD = 10**9 + 7

fact = [1]*(N+1)
rfact = [1]*(N+1)

for i in range(1, N+1):
    fact[i] = r = i*fact[i-1] % MOD
    rfact[i] = pow(r, MOD-2, MOD)

ans = cnt = 0
for K in range((N+1)//2, N):
    res = fact[K]*fact[K-1]*rfact[2*K-N] % MOD
    ans += (res - cnt) * K % MOD
    cnt = res
    ans %= MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, X, D = map(int, input().split())
M = [0]*N
M[0] = int(input())
P = [0]*N
for i in range(N-1):
    M[i+1], P[i+1] = map(int, input().split())

C = [1]*N
for i in range(N-1, 0, -1):
    p = P[i]-1
    C[p] += C[i]
    M[p] += M[i]
L = [D]*N
L[0] = X

from collections import deque

def solve(N, W, ws, vs, ms):
    V0 = max(vs)
    V = sum(v * min(V0, m) for v, m in zip(vs, ms))

    dp = [W+1]*(V + 1)
    dp[0] = 0
    for i in range(N):
        v = vs[i]; w = ws[i]; m = ms[i]
        c = min(V0, m)
        ms[i] -= c
        for k in range(v):
            que = deque()
            push = que.append
            popf = que.popleft; popb = que.pop

            for j in range((V-k)//v+1):
                a = dp[k + j*v] - j * w
                while que and a <= que[-1][1]:
                    popb()
                push((j, a))

                p, b = que[0]

                dp[k + j*v] = b + j * w
                if que and p <= j-c:
                    popf()

    *I, = range(N)
    I.sort(key=lambda x: ws[x]/vs[x])
    *S, = [(vs[i], ws[i], ms[i]) for i in I]

    def greedy():
        yield 0
        for i in range(V + 1):
            if dp[i] > W:
                continue
            rest = W - dp[i]
            r = i
            for v, w, m in S:
                m = min(m, rest // w)
                r += m * v
                rest -= m * w
            yield r
    return max(greedy())

print(solve(N, X, M, C, L))

Fixed submission:
N, X, D = map(int, input().split())
M = [0]*N
M[0] = int(input())
P = [0]*N
for i in range(N-1):
    M[i+1], P[i+1] = map(int, input().split())

C = [1]*N
for i in range(N-1, 0, -1):
    p = P[i]-1
    C[p] += C[i]
    M[p] += M[i]
L = [D]*N
L[0] = X

from collections import deque

def solve(N, W, ws, vs, ms):
    V0 = max(vs)
    V = sum(v * min(V0, m) for v, m in zip(vs, ms))

    dp = [W+1]*(V + 1)
    dp[0] = 0
    for i in range(N):
        v = vs[i]; w = ws[i]; m = ms[i]
        c = min(V0, m)
        ms[i] -= c
        for k in range(v):
            que = deque()
            push = que.append
            popf = que.popleft; popb = que.pop

            for j in range((V-k)//v+1):
                a = dp[k + j*v] - j * w
                while que and a <= que[-1][1]:
                    popb()
                push((j, a))

                p, b = que[0]

                dp[k + j*v] = b + j * w
                if que and p <= j-c:
                    popf()

    *I, = range(N)
    I.sort(key=lambda x: ws[x]/vs[x])
    *S, = [(vs[i], ws[i], ms[i]) for i in I]

    def greedy():
        yield 0
        for i in range(V + 1):
            if dp[i] > W:
                continue
            rest = W - dp[i]
            r = i
            for v, w, m in S:
                m = min(m, rest // w)
                r += m * v
                rest -= m * w
            yield r
    return max(greedy())

print(solve(N, X, M, C, L))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**5)
a, b, c = map(int, input().split())

M = 100
memo = {}
def dfs(a, b, c):
    if (a, b, c) in memo:
        return memo[a,b,c]
    if a == b == c:
        return 0
    res = 10**9+7
    if a < M:
        res = min(res, dfs(a+2, b, c) + 1)
    if b < M:
        res = min(res, dfs(a, b+2, c) + 1)
    if c < M:
        res = min(res, dfs(a, b, c+2) + 1)
    if a < M and b < M:
        res = min(res, dfs(a+1, b+1, c) + 1)
    if b < M and c < M:
        res = min(res, dfs(a, b+1, c+1) + 1)
    if a < M and c < M:
        res = min(res, dfs(a+1, b, c+1) + 1)
    memo[a, b, c] = res
    return res
print(dfs(a, b, c))

Fixed submission:
a, b, c= map(int, input().split())
ans = 0
def calc(a, b):
    if a < b:
        r = b-a
        if r % 2:
            return r//2 + 2
        return r//2
    else:
        return a-b
def solve(a, b, c):
    return calc(a, c) + calc(b, c)
print(min(solve(a, b, c), solve(b, c, a), solve(c, a, b)))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
import sys
sys.setrecursionlimit(10**6)

MOD = 998244353

ABC = "abc".index
*S, = map(ABC, input())
N = len(S)

def bruteforce(S):
    used = set()
    def dfs(s):
        key = tuple(s)
        if key in used:
            return
        used.add(key)
        for i in range(len(s)-1):
            if s[i] != s[i+1]:
                a = s[i]; b = s[i+1]
                s[i] = s[i+1] = 3 - a - b
                dfs(s)
                s[i] = a; s[i+1] = b
    dfs(S)
    return len(used)

if len(S) <= 3:
    print(bruteforce(S))
else:
    c = Counter(S)
    if c[0] == N or c[1] == N or c[2] == N:
        print(1)
    else:
        r3 = range(3); r2 = range(2)
        P = [[[0,0] for i in r3] for j in r3]
        Q = [[[0,0] for i in r3] for j in r3]
        P[0][0][0] = P[1][1][0] = P[2][2][0] = 1
        for i in range(N-1):
            for p in r3:
                for q in r3:
                    for r in r2:
                        Q[p][q][r] = 0
            for p in r3:
                for q in r3:
                    for r in r2:
                        for k in r3:
                            Q[k][(q+k)%3][r | (p == k)] += P[p][q][r] % MOD
            P, Q = Q, P
        ans = 0
        r = sum(S) % 3
        for i in r3:
            ans += P[i][r][1]
        if all(S[i] != S[i+1] for i in range(N-1)):
            ans += 1
        print(ans % MOD)

Fixed submission:
from collections import Counter
import sys
sys.setrecursionlimit(10**6)

MOD = 998244353

ABC = "abc".index
*S, = map(ABC, input())
N = len(S)

def bruteforce(S):
    used = set()
    def dfs(s):
        key = tuple(s)
        if key in used:
            return
        used.add(key)
        for i in range(len(s)-1):
            if s[i] != s[i+1]:
                a = s[i]; b = s[i+1]
                s[i] = s[i+1] = 3 - a - b
                dfs(s)
                s[i] = a; s[i+1] = b
    dfs(S)
    return len(used)

if len(S) <= 3:
    print(bruteforce(S))
else:
    c = Counter(S)
    if c[0] == N or c[1] == N or c[2] == N:
        print(1)
    else:
        P = [[[0,0] for i in range(3)] for j in range(3)]
        Q = [[[0,0] for i in range(3)] for j in range(3)]
        P[0][0][0] = P[1][1][0] = P[2][2][0] = 1
        for i in range(N-1):
            for p in range(3):
                for q in range(3):
                    for r in range(2):
                        Q[p][q][r] = 0
            for p in range(3):
                for q in range(3):
                    for r in range(2):
                        for k in range(3):
                            Q[k][(q+k)%3][r | (p == k)] += P[p][q][r] % MOD
            P, Q = Q, P
        ans = 0
        r = sum(S) % 3
        for i in range(3):
            ans += P[i][r][1]
        if all(S[i] != S[i+1] for i in range(N-1)):
            ans += 1
        print(ans % MOD)
Buggy python submission (verdict: Runtime Error):
s = s0 = input()
d = {chr(c) for c in range(97, 123)}
for c in s:
    d.remove(c)
if d:
    s += min(d)
else:
    for c in reversed(s):
        s = s[:-1]
        if d and c < min(d):
            s += min(d)
            break
        d.add(c)
print(s if s else -1)
assert s0 < s


Fixed submission:
s = s0 = input()
d = {chr(c) for c in range(97, 123)}
for c in s:
    d.remove(c)
if d:
    s += min(d)
else:
    for c in reversed(s):
        s = s[:-1]
        if d and any(c < e for e in d):
            s += min(e for e in d if c < e)
            break
        d.add(c)
print(s if s else -1)
if s:
    assert s0 < s
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
grundy = 0
for i in range(N):
    a, k = map(int, input().split())
    while a % k:
        a = (a - (a//k) - 1)
    grundy ^= a // k
print('Takahashi' if grundy else 'Aoki')


Fixed submission:
def extgcd(a, b):
    if b:
        d, y, x = extgcd(b, a%b)
        y -= (a/b)*x
        return d, x, y
    else:
        return a, 1, 0
N = int(input())
grundy = 0
for i in range(N):
    a, k = map(int, input().split())
    while a % k:
        p, q = divmod(a, k)
        a -= (p + 1)*((q+p)//(p+1))

    grundy ^= a // k
print('Takahashi' if grundy else 'Aoki')
Buggy python submission (verdict: Runtime Error):
N = int(input())
B = [0]*N
for i in range(N-1):
    x, y, a = map(int, input().split())
    B[x] ^= a
    B[y] ^= a
D = {}
for b in B:
    D[b] = D.get(b, 0) + 1
D[0] = 0
ans = 0
first = 0
for b in D:
    ans += D[b]//2
    if D[b]%2:
        first |= 1 << b

A = [0]*(1 << 15)
for i in range(1, 1<<15):
    bit = i & -i
    l = len(bin(bit))-3
    A[i] = A[i ^ bit] ^ l

memo = {0: 0}
def dfs(state):
    if state in memo:
        return memo[state]
    cur = state
    res = 10**9+7
    while cur:
        if A[cur] == 0:
            res = min(res, dfs(state ^ cur) + bin(cur).count('1')-1)
        cur -= 1
        cur &= state
    memo[state] = res
    return res
ans += dfs(first)
print(ans)


Fixed submission:
N = int(input())
B = [0]*N
for i in range(N-1):
    x, y, a = map(int, input().split())
    B[x] ^= a
    B[y] ^= a
D = {}
for b in B:
    D[b] = D.get(b, 0) + 1
D[0] = 0
ans = 0
first = 0
for b in D:
    ans += D[b]//2
    if D[b]%2:
        first |= 1 << b

A = [0]*(1 << 16)
for i in range(1, 1<<16):
    bit = i & -i
    l = len(bin(bit))-3
    A[i] = A[i ^ bit] ^ l

memo = {0: 0}
def dfs(state):
    if state in memo:
        return memo[state]
    cur = state
    res = 10**9+7
    while cur:
        if A[cur] == 0:
            res = min(res, dfs(state ^ cur) + bin(cur).count('1')-1)
        cur -= 1
        cur &= state
    memo[state] = res
    return res
ans += dfs(first)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop
from collections import deque
N, M = map(int, input().split())
S, T = map(int, input().split())
S -= 1; T -= 1
G = [[] for i in range(N)]
for i in range(M):
    u, v, d = map(int, input().split())
    G[u-1].append((v-1, d))
    G[v-1].append((u-1, d))

INF = 10**18
MOD = 10**9 + 7

dist = [INF]*N
dist[S] = 0
que = [(0, S)]
while que:
    cost, v = heappop(que)
    if dist[v] < cost:
        continue
    for w, c in G[v]:
        if cost + c < dist[w]:
            dist[w] = cost + c
            heappush(que, (cost + c, w))

que = deque()
mi = [0]*N
que.append(T)
mi[T] = 1
H = [[] for i in range(N)]
RH = [[] for i in range(N)]

D = dist[T]

V = []
E = []
while que:
    v = que.popleft()
    d = dist[v]
    if d*2 == D:
        V.append(v)
    for w, c in G[v]:
        if d == dist[w] + c:
            if dist[w]*2 < D < d*2:
                E.append((w, v))
            H[v].append(w)
            RH[w].append(v)
            if mi[w] == 0:
                mi[w] = 1
                que.append(w)

def bfs(G, RG, s):
    *deg, = map(len, RG)
    que = deque([s])
    res = [0]*N
    res[s] = 1
    while que:
        v = que.popleft()
        for w in G[v]:
            deg[w] -= 1
            res[w] += res[v]
            if deg[w] == 0:
                que.append(w)
                res[w] %= MOD
    return res
CT = bfs(H, RH, T)
CS = bfs(RH, H, S)

ans = CS[T] * CT[S] % MOD
for v in V:
    ans -= (CS[v] * CT[v]) ** 2
    ans %= MOD
for v, w in E:
    ans -= (CS[v] * CT[w]) ** 2
    ans %= MOD
print(ans)

Fixed submission:
from heapq import heappush, heappop
from collections import deque
N, M = map(int, input().split())
S, T = map(int, input().split())
S -= 1; T -= 1
G = [[] for i in range(N)]
for i in range(M):
    u, v, d = map(int, input().split())
    G[u-1].append((v-1, d))
    G[v-1].append((u-1, d))

INF = 10**18
MOD = 10**9 + 7

dist = [INF]*N
dist[S] = 0
que = [(0, S)]
while que:
    cost, v = heappop(que)
    if dist[v] < cost:
        continue
    for w, c in G[v]:
        if cost + c < dist[w]:
            dist[w] = cost + c
            heappush(que, (cost + c, w))

que = deque()
mi = [0]*N
que.append(T)
mi[T] = 1
H = [[] for i in range(N)]
RH = [[] for i in range(N)]

D = dist[T]

V = []
E = []
while que:
    v = que.popleft()
    d = dist[v]
    if d*2 == D:
        V.append(v)
    for w, c in G[v]:
        if d == dist[w] + c:
            if dist[w]*2 < D < d*2:
                E.append((w, v))
            H[v].append(w)
            RH[w].append(v)
            if mi[w] == 0:
                mi[w] = 1
                que.append(w)

def bfs(G, RG, s):
    *deg, = map(len, RG)
    que = deque([s])
    res = [0]*N
    res[s] = 1
    while que:
        v = que.popleft()
        for w in G[v]:
            deg[w] -= 1
            res[w] += res[v]
            if deg[w] == 0:
                que.append(w)
                res[w] %= MOD
    return res
CT = bfs(H, RH, T)
CS = bfs(RH, H, S)

ans = CS[T] * CT[S] % MOD
for v in V:
    ans -= (CS[v] * CT[v]) ** 2
    ans %= MOD
for v, w in E:
    ans -= (CS[v] * CT[w]) ** 2
    ans %= MOD
print(ans)