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

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def check(vec, init_pos, target_pos):
    base = 8000
    dp = [[False] * 16001 for _ in range(len(vec) + 1)]
    dp[0][init_pos + base] = True

    for i in range(len(vec)):
        for j in range(16001):
            if j - vec[i] >= 0 and dp[i][j - vec[i]] or j + vec[i] <= 16000 and dp[i][j + vec[i]]:
                dp[i + 1][j] = True

    return dp[len(vec)][target_pos + base]


def main():
    S = readline().strip()
    x, y = map(int, readline().split())

    idx = len(S)
    for i, c in enumerate(S):
        if c == 'T':
            idx = i
            break

    init_x = idx
    step = [[0] for _ in range(2)]
    i = 0
    for c in S[idx:]:
        if c == 'T':
            i = 1 - i
            step[i].append(0)
        else:
            step[i][-1] += 1

    ok = check(step[0], init_x, x) and check(step[1], 0, y)

    if ok:
        print('Yes')
    else:
        print('No')

    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def check(vec, init_pos, target_pos):
    base = 8000
    dp = [False] * 16001
    dp[init_pos + base] = True

    for i in range(len(vec)):
        dp, dp_prev = [False] * 16001, dp
        for j in range(16001):
            if (
                j - vec[i] >= 0
                and dp_prev[j - vec[i]]
                or j + vec[i] <= 16000
                and dp_prev[j + vec[i]]
            ):
                dp[j] = True

    return dp[target_pos + base]


def main():
    S = readline().strip()
    x, y = map(int, readline().split())

    idx = len(S)
    for i, c in enumerate(S):
        if c == 'T':
            idx = i
            break

    init_x = idx
    step = [[0] for _ in range(2)]
    i = 0
    for c in S[idx:]:
        if c == 'T':
            i = 1 - i
            step[i].append(0)
        else:
            step[i][-1] += 1

    ok = check(step[0], init_x, x) and check(step[1], 0, y)

    if ok:
        print('Yes')
    else:
        print('No')

    return


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

import sys
input=sys.stdin.readline
h,w=map(int,input().split())
a=[list(map(int,input().split())) for i in range(h)]
b=[list(map(int,input().split())) for i in range(h)]
c=[[0]*w for i in range(h)]
for i in range(h):
  for j in range(w):
    c[i][j]=abs(a[i][j]-b[i][j])
dp=[[[] for i in range(w)] for j in range(h)]
dp[0][0].append(c[0][0])
for i in range(h):
  for j in range(w):
    f=0
    if i<h-1:
      l=[]
      for k in range(len(dp[i][j])):
        if -160*80<=dp[i][j][k]+c[i+1][j]<=160*80:
          l.append(dp[i][j][k]+c[i+1][j])
        if -160*80<=l[k]-c[i+1][j]<=160*80:
          l.append(dp[i][j][k]-c[i+1][j])
      l=list(set(l))
      dp[i+1][j]=l+dp[i+1][j]
      dp[i+1][j]=list(set(dp[i+1][j]))
    f=0
    if j<w-1:
      l=[]
      for k in range(len(dp[i][j])):
        if -160*80<=dp[i][j][k]+c[i][j+1]<=160*80:
          l.append(dp[i][j][k]+c[i][j+1])
        if -160*80<=dp[i][j][k]-c[i][j+1]<=160*80:
          l.append(dp[i][j][k]-c[i][j+1])
      l=list(set(l))
      dp[i][j+1]=l+dp[i][j+1]
      dp[i][j+1]=list(set(dp[i][j+1]))
for i in range(len(dp[h-1][w-1])):
  dp[h-1][w-1][i]=abs(dp[h-1][w-1][i])
print(min(dp[h-1][w-1]))

### FIXED CODE ###

import sys
input=sys.stdin.readline

def main():
  h,w=map(int,input().split())
  a=[list(map(int,input().split())) for i in range(h)]
  b=[list(map(int,input().split())) for i in range(h)]
  dp=[[[0]*(80*(h+w+1)+1) for i in range(w)] for j in range(h)]
  dp[0][0][abs(a[0][0]-b[0][0])]=1
  for i in range(h):
    for j in range(w):
      c=abs(a[i][j]-b[i][j])
      if i!=0 or j!=0:
        for k in range(80*(i+j+1)+1):
          dp[i][j][k]=dp[i-1][j][abs(k-c)]|dp[i-1][j][k+c]|dp[i][j-1][abs(k-c)]|dp[i][j-1][k+c]
  for i in range(80*(h+w+1)+1):
    if dp[h-1][w-1][i]==1:
      print(i)
      break

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

N,K = map(int,input().split())
stones = list(map(int,input().split()))
dp =[0] *N

dp[0]=0
dp[1]=abs(stones[1]-stones[0])

for i in range(2,N):
    dp[i] = min(abs(stones[i] - stones[j]) + dp[j] for j in range(max(0, i - K), i))

print(dp[-1])


### FIXED CODE ###

N,K = map(int,input().split())
stones = list(map(int,input().split()))
dp =[0] *N

for i in range(1,N):
    dp[i] = min(abs(stones[i] - stones[j]) + dp[j] for j in range(max(0, i - K), i))

print(dp[-1])
### BUGGY CODE ###

import math

a, b = map(int, input().split())
n = min(a, b)
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]
l = primes(n//2)
count = 1
for p in l:
    if a % p == 0 and b % p == 0:
        count += 1
print(count)

### FIXED CODE ###

a, b = map(int, input().split())

def gcd(a, b):
    while b > 0:
        a, b = b, a%b
    return a
n = gcd(a, b)

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

ans = set(prime_factorize(n))
print(len(ans)+1)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
Ss = set(a)
s = list(Ss)
#import collections
#c = collections.Counter
j = 0
for i in range(len(s)):
  j += int(a.count(s[i])*(a.count(s[i])-1)/2)
#print(j)
for i in range(n):
  if a.count(a[i]) >= 2:
    print(int(j-(a.count(a[i])-1)))
  else:
    print(j)

### FIXED CODE ###

def main():
  import sys
  input = sys.stdin.readline
  n = int(input())
  a = [int(i) for i in input().split()]
  Ss = set(a)
  s = list(Ss)
  import collections
  c = collections.Counter(a)
  j = 0
  #print(c[a[0]])
  for i in range(len(s)):
    j += int(c[s[i]]*(c[s[i]]-1)/2)
  #print(j)
  for i in range(n):
    if c[a[i]] >= 2:
      print(int(j-(c[a[i]]-1)))
    else:
      print(j)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import math
S = int(input())

for i in range(int(math.sqrt(S))+1,0,-1):
    if S%i == 0:
        print(0,0,i,0,0,S//i)
        break

### FIXED CODE ###

import math
S = int(input())

if int(math.sqrt(S))**2 == S:
    a = d = int(math.sqrt(S))
else:
    a = d = int(math.sqrt(S)) + 1

bc = a*d - S

if bc == 0:
    b = c = 0
else:
    for i in range(int(math.sqrt(bc)),0,-1):
        if bc % i == 0:
            b = i
            c = bc//i
            break

print(0,0,a,b,c,d)
### BUGGY CODE ###

n=int(input())
s=0
for i in range(1,n):
    s+=i
print(s)

### FIXED CODE ###

n=int(input())
print((n-1)*n//2)
### BUGGY CODE ###

import bisect
N=int(input())
S=list(input())
ans=0
R=[]
G=[]
B=[]
for i in range(N):
    if S[i]=="R":
        R.append(i+1)
    elif S[i]=="G":
        G.append(i+1)
    else:
        B.append(i+1)
B.append(10000)
lenb=len(B)-1
for r in R:
    for g in G:
        flag=0
        left=max(min(r,g)-abs(r-g),0)
        right=max(r,g)+abs(r-g)
        if (r+g)%2==0:
            middle=(r+g)//2
        else:
            middle=0
        for i in (left,right,middle):
            if i!=0:
                a=bisect.bisect_left(B,i)
                if B[a]==i:
                    flag=flag+1
        ans=ans+lenb-flag
print(ans)

### FIXED CODE ###

N=int(input())
S=list(input())
ans=0
R=0
G=0
B=0
for i in range(N):
    if S[i]=="R":
        R=R+1
    elif S[i]=="G":
        G=G+1
    else:
        B=B+1
ans=R*G*B
for i in range(N-2):
    for j in range(i+1,N-1):
        if S[i]!=S[j]:
            k=2*j-i
            if N<=k:
                continue
            if S[i]!=S[k] and S[k]!=S[j]:
                ans=ans-1
print(ans)
### BUGGY CODE ###

n = int(input())

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

ans = 1
for tmp in a:
    ans *= tmp

if (ans > 1e18) :
    print(-1)
else:
    print(ans)


### FIXED CODE ###

def main():
    n = int(input())

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

    if 0 in a:
        print(0)
        return

    ans = 1
    for tmp in a:
        ans *= tmp
        if (ans > 1e18) :
            print(-1)
            return

    print(ans)

main()
### BUGGY CODE ###

from collections import Counter 

def main():
    n = int(input())

    checker = [False] * (10**6+1)

    a = list([int(t)for t in input().split()])
    c = Counter(a)

    for a_i in a:
        for i in range(a_i*2,10**6+1,a_i):
            checker[i] = True

    ans = 0
    for a_i in a:
        if not checker[a_i] and c[a_i]==1:
            ans += 1

    print(ans)
            
if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import Counter 

def main():
    n = int(input())
    a = list([int(t)for t in input().split()])
    c = Counter(a)
    checker = [False]*(10**6+1)
    times = [False]*(10**6+1)

    for a_i in a:
        checker[a_i] = True
    ans = 0
    for i in range(1,10**6+1):
        if times[i]:
            continue
        if not checker[i]:
            continue
        if checker[i] and c[i]==1:
            ans+=1
        for j in range(i,10**6+1,i):
            times[j] = True
        
    print(ans)
            
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n, m = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
if n == 1: print(a[0] // (2**m))
else:
    a.sort()
    for _ in range(m):
        a[-1] //= 2
        if a[-1] >= a[-2]: continue
        else:
            a.sort()
    print(sum(a))

### FIXED CODE ###

import heapq as hp
n, m = (int(x) for x in input().split())
a = [int(x)*(-1) for x in input().split()]
hp.heapify(a)
for _ in range(m):
    min = hp.heappop(a)
    hp.heappush(a, (-1)*(-min//2))
print(-sum(a))
### BUGGY CODE ###

import copy
N, Q = map(int, input().split())
s = str(input())
TD = [list(map(str, input().split())) for i in range(Q)]

# どんどん合体していくことだけはわかった
hash = {}
for i in range(N):
    if s[i] in hash.keys():
        hash[s[i]].append(i)
    else:
        hash[s[i]] = [i]

for t, d in TD:
    if t not in hash.keys():
        continue
    if d == 'R':
        r_list = [i+1 for i in hash[t]]
        hash[t] = []
        for r in r_list:
            if 0 <= r <= N-1:
                hash[s[r]].append(r)
    else:
        l_list = [i-1 for i in hash[t]]
        hash[t] = []
        for l in l_list:
            if 0 <= l <= N - 1:
                hash[s[l]].append(l)

ans = 0
for d in hash.values():
    ans += len(d)
print(ans)

### FIXED CODE ###

N, Q = map(int, input().split())
S = str(input())
TD = [list(map(str, input().split())) for i in range(Q)]


def disappear(index, place):
    if index == -1:
        return (False, False)
    else:
        left = False
        right = False
        for t, d in TD:
            cur_chara = place[index]
            if t == cur_chara:
                if d == 'R':
                    index += 1
                else:
                    index -= 1
                if index < 0:
                    left = True
                    break
                elif index > N-1:
                    right = True
                    break
        return (left, right)


def binarySearch(place, direction):
    """
    :param direction; left, right
    :return: 消失する位置
    """
    start, end = -1, N
    if direction == 'left':
        while end - start > 1:
            t = start + (end - start) // 2
            if disappear(t, place)[0]:
                start = t
            else:
                end = t
        return start
    elif direction == 'right':
        while end - start > 1:
            t = start + (end - start) // 2
            if disappear(t, place)[1]:
                end = t
            else:
                start = t
        return start


left = binarySearch(S, direction='left')
right = binarySearch(S, direction='right')
print(right - left)
### BUGGY CODE ###

n = int(input())
power = 1
for i in range(1, n+1):
    power *= i
print(power % 1000000007)


### FIXED CODE ###

n = int(input())
power = 1
for i in range(1, n+1):
    power = (i * power) % 1000000007
print(power)
### BUGGY CODE ###

N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(int, input().split())) for _ in range(N)]
sum_val = [[0] * C for _ in range(3)]

for color in range(1, C + 1):
    for i in range(N):
        for j in range(N):
            sum_val[(i + j) % 3][color - 1] += D[c[i][j] - 1][color - 1]

ans = float('inf')
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i == j or j == k or i == k:
                continue
            ans = min(ans, sum_val[0][i] + sum_val[1][j] + sum_val[2][k])
print(ans)

### FIXED CODE ###

N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(int, input().split())) for _ in range(N)]
sum_val = [[0] * C for _ in range(3)]

for color in range(1, C + 1):
    for i in range(N):
        for j in range(N):
            sum_val[(i + j) % 3][color - 1] += D[c[i][j] - 1][color - 1]

ans = float('inf')
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i == j or j == k or i == k:
                continue
            ans = min(ans, sum_val[0][i] + sum_val[1][j] + sum_val[2][k])
print(ans)
### BUGGY CODE ###

import sys
import math

N, M = list(map(int, input().split()))
H = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]

cnt = 0
for i in range(1,N+1):
    tmp = []
    for j in AB:
        if i in j:
            tmp.extend(j)
    tmp = list(set(tmp))
#    print(i,tmp)

    top_flag = True
    for k in tmp:
        if i == k:
            continue
        if H[i-1] <= H[k-1]:
            top_flag = False
    if top_flag == True:
        cnt += 1

print(cnt) 


### FIXED CODE ###

import sys
import math
from collections import deque

N, M = list(map(int, input().split()))
H = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]

mydict = {}
for i in AB:
    if i[0] not in mydict:
        mydict[i[0]] =[i[1]]
    else:
        mydict[i[0]].append(i[1])

    if i[1] not in mydict:
        mydict[i[1]] =[i[0]]
    else:
        mydict[i[1]].append(i[0])


cnt = 0
for i in range(1,N+1):
    if i not in mydict.keys():
        cnt += 1
        continue

    top_flag = True
    for k in list(set(mydict[i])):
        if i == k:
            continue
        if H[i-1] <= H[k-1]:
            top_flag = False
            break
    if top_flag == True:
        cnt += 1

print(cnt)
### BUGGY CODE ###

N=int(input())
S=input()
ans=0
partlist=[[] for i in range(0,N+1)]
for j in range(0,N-1):
    if S[j]==S[j+1]:
        ans=1
for i in range(2,N):
    x=S[0]
    for j in range(1,i):
        x+=S[j]
    partlist[i].append([x,0])
    for j in range(0,N-i):
        x=x[1:i]+S[j+i]
        partlist[i].append([x,j+1])
    partlist[i].sort()
    for j in range(0,len(partlist[i])-1):
        if partlist[i][j][0]==partlist[i][j+1][0] and partlist[i][j][1]+i-1<partlist[i][j+1][1]:
            if i>ans:
                ans=i
print(ans)

### FIXED CODE ###

from itertools import groupby

N=int(input())
S=input()
def condition(num):
    if num==0:
        return True
    else:
        flag=0
        data=[]
        for i in range(0,N-num+1):
            data.append([S[i:i+num],i])
        data.sort()
        partdata=[data[i][0] for i in range(0,len(data))]
        partdata=groupby(partdata)
        subdata=[]
        for key,group in partdata:
            g=len(list(group))
            subdata.append(g)
        s=0
        t=subdata[0]-1
        if len(subdata)==1:
            if data[t][1]-data[s][1]>=num:
                flag=1
        for i in range(0,len(subdata)-1):
            if data[t][1]-data[s][1]>=num:
                flag=1
            s=t+1
            t=t+subdata[i+1]
        if data[t][1]-data[s][1]>=num:
            flag=1
        return flag==1

start=0
end=N
while end-start>1:
    test=(end+start)//2
    if condition(test):
        start=test
    else:
        end=test
if condition(end):
    print(end)
else:
    print(start)
### BUGGY CODE ###

n,x,y = map(int,input().split())
dist = []

for i in range(1,n):
    for j in range(i+1,n+1):
        dist.append(min(j - i,abs(i-x) + 1 + abs(y-j)))
for i in range(1,n):
    print(dist.count(i))

### FIXED CODE ###

n,x,y = map(int,input().split())
dist = [[0] for i in range(n)]

for i in range(1,n):
    for j in range(i+1,n+1):
        dist[min(j - i,abs(i-x) + 1 + abs(y-j),abs(y-i)+ 1 + abs(j-x))][0] += 1

for i in range(1,n):
    print(dist[i][0])
### BUGGY CODE ###

def l_in(type_): return list(map(type_, input().split()))
def i_in(): return int(input())
def m_in(type_): return map(type_, input().split())
def r_in(n, type_): return [type_(input()) for _ in range(n)]
ans = 0
const = 1000000007

n = i_in()
a = l_in(int)
hn = n/2
ts = sum(a)

for i in range(n):
    s = sum(a[i+1:]) if i > hn else ts - sum(a[:i+1])
    ans += s * a[i]

print(ans%const)


### FIXED CODE ###

def l_in(type_): return list(map(type_, input().split()))
def i_in(): return int(input())
def m_in(type_): return map(type_, input().split())
def r_in(n, type_): return [type_(input()) for _ in range(n)]
const = 1000000007
ans = 0

n = i_in()
a = l_in(int)

ins = 0
for i in range(1, n):
    ins += a[i-1]
    ans += ins * a[i]

print(ans%const)
### BUGGY CODE ###

import numpy as np
import sys

count=0
N=int(sys.stdin.readline().rstrip())
P=[int(i) for i in sys.stdin.readline().split()]
for i in range(0,N):
  if np.min(P[0:i+1])==P[i]:
    count+=1
print(count)

### FIXED CODE ###

import numpy as np
import sys

count=0
N=int(sys.stdin.readline().rstrip())
P=[int(i) for i in sys.stdin.readline().split()]
minval=np.max(P)
for i in range(0,N):
  if minval>=P[i]:
    minval=P[i]
    count+=1
print(count)
### BUGGY CODE ###

from collections import deque
n,k=map(int,input().split())
p = list(map(int,input().split()))
def ex_even(a):
    return (a+1)/2
def ex_odd(b):
    return b//2 + 1
ans = [0] * k
q = deque(ans)
c_max = 0
for i in range(1,n+1):
    if p[i-1] % 2 == 0:
        ex = ex_even(p[i-1])
        if ex > q[0]:
            q.popleft()
            q.append(ex)
            c_max = max(c_max, sum(q))
        else:
            q.popleft()
            q.append(ex)
    else:
        ex = ex_odd(p[i-1])
        if ex > q[0]:
            q.popleft()
            q.append(ex)
            c_max = max(c_max, sum(q))
        else:
            q.popleft()
            q.append(ex)
print(c_max)

### FIXED CODE ###

n,k=map(int,input().split())
p = list(map(int,input().split()))
def ex_even(a):
    return (a+1)/2
def ex_odd(b):
    return b//2 + 1
s = sum(p[0:k])
s_max = sum(p[0:k])
for i in range(n-k):
    s = s-p[i] + p[i+k]
    s_max = max(s_max,s)
if s_max % 2 == 0:
    print(ex_even(s_max) + 0.5*(k-1))
else:
    print(ex_odd(s_max) + 0.5*(k-1))
### BUGGY CODE ###

H,W=map(int,input().split())
field=[]
for i in range(H):
  field.append(list(input()))

l=[[0]*W for _ in range(H)]
r=[[0]*W for _ in range(H)]
u=[[0]*W for _ in range(H)]
d=[[0]*W for _ in range(H)]

for j in range(H):
  for i in range(W):
    if field[j][i]==".":
      if i==0:
        l[j][i]=1
      else:
        l[j][i]=l[j][i-1]+1
      if j==0:
        u[j][i]=1
      else:
        u[j][i]=u[j-1][i]+1
        

for j in reversed(range(H)):
  for i in reversed(range(W)):
    if field[j][i]==".":
      if i==W-1:
        r[j][i]=1
      else:
        r[j][i]=r[j][i+1]+1
      if j==H-1:
        d[j][i]=1
      else:
        d[j][i]=d[j+1][i]+1

A=[]
for j in range(H):
  for i in range(W):
    A.append(l[j][i]+r[j][i]+d[j][i]+u[j][i]-3)

print(max(A))

### FIXED CODE ###

H,W=map(int,input().split())
field=[list(input()) for _ in range(H)]

l=[[0]*W for _ in range(H)]
r=[[0]*W for _ in range(H)]
u=[[0]*W for _ in range(H)]
d=[[0]*W for _ in range(H)]

for j in range(H):
  for i in range(W):
    if field[j][i]==".":
      if i==0:
        l[j][i]=1
      else:
        l[j][i]=l[j][i-1]+1
      if j==0:
        u[j][i]=1
      else:
        u[j][i]=u[j-1][i]+1
        

for j in reversed(range(H)):
  for i in reversed(range(W)):
    if field[j][i]==".":
      if i==W-1:
        r[j][i]=1
      else:
        r[j][i]=r[j][i+1]+1
      if j==H-1:
        d[j][i]=1
      else:
        d[j][i]=d[j+1][i]+1

A=[]
for j in range(H):
  for i in range(W):
    A.append(l[j][i]+r[j][i]+d[j][i]+u[j][i]-3)

print(max(A))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, m, p = map(int, input().split())
edges = []
forward_edges = [[] for _ in range(n)]
backward_edges = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edges.append((a, b, p-c))
    forward_edges[a].append(b)
    backward_edges[b].append(a)

can_goal = [0]*n


def dfs(v, parent):
    can_goal[v] = 1
    for v2 in backward_edges[v]:
        if parent == v2:
            continue
        dfs(v2, v)


dfs(n-1, -1)

can_reach = [0]*n

def dfs(v, parent):
    can_reach[v] = 1
    for v2 in forward_edges[v]:
        if parent == v2:
            continue
        dfs(v2, v)

dfs(0, -1)

INF = 10**10
dist = [INF]*n
dist[0] = 0
for i in range(n):
    for v, v2, c in edges:
        if dist[v2] <= dist[v]+c:
            continue
        dist[v2] = dist[v]+c

negative = [0]*n
for i in range(n):
    for v, v2, c in edges:
        if dist[v2] <= dist[v]+c:
            continue
        dist[v2] = dist[v]+c
        negative[v2] = 1

got_infinity_coins = 0
for i in range(n):
    if negative[i]:
        if can_reach[i] and can_goal[i]:
            got_infinity_coins = 1
            break
            
if got_infinity_coins:
    print(-1)
else:
    print(max(0, -dist[-1]))


### FIXED CODE ###

import sys
input = sys.stdin.readline
n, m, p = map(int, input().split())
edges = []
forward_edges = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edges.append((a, b, p-c))
    forward_edges[a].append(b)


can_reach = [0]*n
stack = [0]
while stack:
    v = stack.pop()
    if can_reach[v]:
        continue
    can_reach[v] = 1
    for v2 in forward_edges[v]:
        if can_reach[v2]:
            continue
        stack.append(v2)


INF = 10**10
dist = [INF]*n
dist[0] = 0
for i in range(n):
    for v, v2, c in edges:
        if dist[v2] <= dist[v]+c:
            continue
        dist[v2] = dist[v]+c

negative = [0]*n
for i in range(n):
    for v, v2, c in edges:
        if dist[v2] <= dist[v]+c:
            continue
        if not can_reach[v2]:
            continue
        dist[v2] = -INF
        negative[v2] = 1

if negative[-1]:
    print(-1)
else:
    print(max(0, -dist[-1]))
### BUGGY CODE ###

mod = 10**9 + 7

s = input()[::-1]
n = len(s)
DP = [[0]*3 for i in range(n+1)]

htn_cnt = 0
for i, c in enumerate(list(s)):
    for j in range(3):
        if c == "?":
            DP[i+1][j] = 3*DP[i][j] % mod
        else:
            DP[i+1][j] = DP[i][j] % mod
    if c == "C" or c == "?":
        DP[i+1][0] += 3**htn_cnt
    if c == "B" or c == "?":
        DP[i+1][1] += DP[i][0]
    if c == "A" or c == "?":
        DP[i+1][2] += DP[i][1]
    if c == "?":
        htn_cnt += 1
print(DP[n][2] % mod)

### FIXED CODE ###

import numpy as np
mod = 10**9 + 7

s = input()[::-1]
#s = "?"*(10**5)
n = len(s)
DP = [[0]*3 for i in range(n+1)]

power_three = 1

for i, c in enumerate(list(s)):
    for j in range(3):
        if c == "?":
            DP[i+1][j] = 3*DP[i][j] % mod
        else:
            DP[i+1][j] = DP[i][j] % mod
    if c == "C" or c == "?":
        DP[i+1][0] = (DP[i+1][0] + power_three) % mod
    if c == "B" or c == "?":
        DP[i+1][1] = (DP[i+1][1] + DP[i][0]) % mod
    if c == "A" or c == "?":
        DP[i+1][2] = (DP[i+1][2] + DP[i][1]) % mod
    if c == "?":
        power_three = 3*power_three % mod
print(DP[n][2] % mod)