Harryxun/stf_run huggingface dataset:
import numpy
import math
import collections
from decimal import *

def main():
    n = int(input())
    a = input_list()
    ca = collections.Counter(a)
    max_n = 10 ** 18
    if 0 in a:
        print(0)
        exit()
    ans = 1
    for num, count in ca.items():
        if num == 1:
            continue
        ans *= num**count
        if ans > max_n:
            print(-1)
            exit()
    print(ans)


def yogen(a, b, angle):
    coss = math.cos((angle/180)*math.pi)
    return math.sqrt(a**2 + b**2 - 2*a*b*coss)


def get_angle(hour, minute):
    h = (hour * 360) / 12 + (minute * 360) / (12 * 60)
    m = (minute * 360) / 60
    angle = abs(h-m)
    return min(angle, 360-angle)

def has(v, l):
    for vl in l:
        if v == vl:
            return True
    return False

def input_list():
    return list(map(int, input().split()))


if __name__ == '__main__':
    main()


### FIXED CODE ###

#import numpy
import math
import sys

def main():
    n = int(input())
    a = sorted(input_list())
    max_n = 10 ** 18
    ans = 1
    for v in a:
        ans *= v
        if ans > max_n:
            ans = -1
            break
        if ans == 0:
            break
    print(ans)


def yogen(a, b, angle):
    coss = math.cos((angle/180)*math.pi)
    return math.sqrt(a**2 + b**2 - 2*a*b*coss)


def get_angle(hour, minute):
    h = (hour * 360) / 12 + (minute * 360) / (12 * 60)
    m = (minute * 360) / 60
    angle = abs(h-m)
    return min(angle, 360-angle)

def has(v, l):
    for vl in l:
        if v == vl:
            return True
    return False

def input_list():
    return list(map(int, sys.stdin.readline().split()))


if __name__ == '__main__':
    main()
input()
A = list(map(int, input().split))
count = 0
while all(a % 2 == 0 for a in A):
  A = [a/2 for a in A]
  count += 1
print(count)

### FIXED CODE ###

input()
A = list(map(int, input().split()))
count = 0
while all(a % 2 == 0 for a in A):
  A = [a/2 for a in A]
  count += 1
print(count)
while 1:
    try:
        ipt = raw_input().split() 
        s = []
        for i in range(len(ipt)):
            if ipt[i].isdigit():
                s.append(float(ipt[i]))
            else:
                b = s.pop(); a = s.pop();
                if ipt[i]=='+':
                    s.append(a+b)
                elif ipt[i]=='-':
                    s.append(a-b)
                elif ipt[i]=='*':
                    s.append(a*b)
                else:
                    s.append(a/b)
        if len(s)==1: print "%.6f"%s[0]
    except EOFError:
        break;

### FIXED CODE ###

import sys
for s in sys.stdin.readlines():
    st = []
    for c in s.strip().split():
        if c=='+':
            st.append(st.pop()+st.pop())
        elif c=='-':
            st.append(-st.pop()+st.pop())
        elif c=='*':
            st.append(st.pop()*st.pop())
        elif c=='/':
            st.append(1/st.pop()*st.pop())
        else:
            st.append(float(c))
    print st.pop()
while True:
    r, c = input()
    if not r: break
    print "yes" if not r*c%2 else "no"

### FIXED CODE ###

while 1:
    r,c=map(int,raw_input().split())
    if r==0:break
    print "yes" if r*c%2==0 else "no"
i = 1
while True:
  x = int(input())
  if x == 0 :
    break
  print("Case","", i,":","",x)
  i += 


### FIXED CODE ###

i = 1
while True:
  x = int(input())
  if x == 0 :
    break
  print("Case {}: {}".format(i,x))
  i += 1
import math
 
a, b, h, m = map(int, input().split())
 
deg = 0
 
deg += 5.5 * m
deg -= 30 * h
 
print(math.sqrt(a ** 2 + b ** 2 - 2 * a * b * math.cos(math.radians(abs(deg)))))

### FIXED CODE ###

one = int(input()) % 10


hon_list = [2, 4, 5, 7, 9]

if one in hon_list:
    print('hon')
elif 3 == one:
    print('bon')
else:
    print('pon')
import math
import itertools
import numpy as np

n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]

def l2(z1, z2):
  return np.sqrt((z1[0]^2 - z2[0]^2) + (z1[1]^2 - z2[1]^2))


dist = 0
z_fr = []
z_to = []
for seq in itertools.permutations(l, n):
  for z in seq:
    z_fr = z_to
    z_to = z
    if len(z_fr):
      continue
    dist += l2(z_fr, z_to)

print(dist/math.factorial(n))

### FIXED CODE ###

import math
import itertools

def l2(z1, z2):
  return math.sqrt(pow(z1[0] - z2[0], 2) + pow(z1[1] - z2[1], 2))

n = int(input())
l = [list(map(int, input().split(' '))) for _ in range(n)]
seq_list = itertools.permutations(l, n)

dist = 0
for seq in seq_list:
  z_fr = []
  z_to = []
  
  for z in seq:
    z_fr = z_to
    z_to = z
    if len(z_fr)==0:
      continue
    dist += l2(z_fr, z_to)

print(dist/math.factorial(n))
from sys import setrecursionlimit
setrecursionlimit(10**9)

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    l = []
    for _ in range(40):
        cnt = 0
        for i in range(n):
            if a[i] & 1:
                cnt += 1
            a[i] >>= 1
        l.append(cnt)

    pows = [1]
    for _ in range(39):
        pows.append(pows[-1] * 2)

    right = 40

    def solve(k, right):
        if right == 0:
            return 0

        left = k.bit_length()
        x = 0
        y = 0
        for i in range(left):
            if l[i] < n - l[i]:
                x += pows[i]
                y += (n - l[i]) * pows[i]
            else:
                y += l[i] * pows[i]
        for i in range(left, right):
            y += l[i] * pows[i]

        if x <= k:
            return y
        else:
            return max(y - (n-2*l[right-1]) * pows[right-1], (n - l[i]) * pows[right-1] + solve(k - pows[right-1], left))

    print(solve(k, right))

main()

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    l = []
    for _ in range(40):
        cnt = 0
        for i in range(n):
            if a[i] & 1:
                cnt += 1
            a[i] >>= 1
        l.append(cnt)

    pows = [1]
    for _ in range(39):
        pows.append(pows[-1] * 2)

    if k == 0:
        print(sum([l[i] * pows[i] for i in range(40)]))
        exit()

    # when it does not use the biggest bit of k
    ans1 = 0
    for i in range(k.bit_length() - 1):
        if l[i] < n - l[i]:
            ans1 += (n - l[i]) * pows[i]
        else:
            ans1 += l[i] * pows[i]
    for i in range(k.bit_length() - 1, 40):
        ans1 += l[i] * pows[i]

    # when it use the biggest bit of k
    ans2 = 0
    ans3 = 0
    for i in range(40):
        if l[i] < n - l[i]:
            if k & 1:
                ans2 += (n - l[i]) * pows[i]
            else:
                ans2 += l[i] * pows[i]
            ans3 += (n - l[i]) * pows[i]
        else:
            if k & 1:
                ans2 = ans3 + l[i] * pows[i]
            else:
                ans2 += l[i] * pows[i]
            ans3 += l[i] * pows[i]
        k >>= 1

    print(max(ans1, ans2))

main()
N,X = map(int,input().split())
if N == 0:
    print(1)
    exit()
# a:バンの数  b:パティの数
a,b = [1],[1]
for i in range(N):
    a.append(2*a[i] + 3)
    b.append(2*b[i] + 1)
def f(N,X):
    if X == 1:
        return 0
    elif 1 < X <= a[N-1] + 1:
        return f(N-1,X-1)
    elif X == a[N-1] + 2:
        return b[N-1] + 1
    elif a[N-1] + 2 < X <= 2*a[N-1] + 2:
        return b[N-1] + 1 + f(N-1,X-(a[N-1]+2))
    elif X = 2*a[N-1] + 3:
        return 2*b[N-1] + 1
ans = def(N,X)
print(ans)

### FIXED CODE ###

N,X = map(int,input().split())
# a:バンの数  b:パティの数
a,b = [1],[1]
for i in range(N):
    a.append(2*a[i] + 3)
    b.append(2*b[i] + 1)
def f(N,X):
    if N == 0:
        return 1
    if X == 1:
        return 0
    elif 1 < X <= a[N-1] + 1:
        return f(N-1,X-1)
    elif X == a[N-1] + 2:
        return b[N-1] + 1
    elif a[N-1] + 2 < X <= 2*a[N-1] + 2:
        return b[N-1] + 1 + f(N-1,X-(a[N-1]+2))
    elif X == 2*a[N-1] + 3:
        return 2*b[N-1] + 1
ans = f(N,X)
print(ans)
# input
N = int(input())
A = list(map(int, input().split()))

l, r, sum, ans = 0, 0, 0, 0
 
while r < N:
    if sum + A[r] == num ^ A[r]:
        sum += A[r]
        ans += r - l + 1
        r += 1
    else:
        sum -= A[l]
        l += 1
 
print(ans)

### FIXED CODE ###

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

l, r, sum, ans = 0, 0, 0, 0
 
while r < N:
    if sum + A[r] == sum ^ A[r]:
        sum += A[r]
        ans += r - l + 1
        r += 1
    else:
        sum -= A[l]
        l += 1
 
print(ans)
#include <bits/stdc++.h>
using namespace std; 
typedef long long int  ll;
#pragma GCC optimize("O3")
#define pb push_back

int32_t main()  {
    ios::sync_with_stdio(false);
    cin.tie(0);
	int n ;
	cin >> n ;
	ll ans = 1;
	ll k = 1000000000000000000;
	int fl =0;
	while ( n--)
	{
		ll in ;
		cin >> in;
		ans=ans*in;
		if(ans>k) {
			fl=1;}
		if(in==0){
			ans=0;
		}
		if(ans!=0)	
		if((k/ans)>in) {
			fl=1;
		}	
	}
	if(	fl==1 and ans!=0)
	cout<<-1<<endl;
	else
	cout << ans;
}


### FIXED CODE ###

n=int(input())
p=list(map(int, input().split()))
i=0
ans=1
flag=0
k=1e18
while(n>i):
	if(p[i]==0):
		flag=1
	i+=1
if(flag==1):
	print(0)
else:
	flag=0
	i=0			
	while(n>i):
		ans*=p[i]
		if(ans>k):
			flag=1
			break
		i+=1		
	if( flag==1):
		print(-1)
	else:
		print(ans)
import numpy as np

n = int(input())
l = np.arange(1,n+1)
print(np.pord(l)%(10**9+7))

### FIXED CODE ###

n = int(input())
ans = 1

for i in range(1, n+1):
  ans *= i
  ans %= 10**9+7

print(ans)
import itertools

def warshall_floyd(d):
  len_d = len(d)
  for k in range(len_d):
    for i in range(len_d):
      for j in range(len_d):
        if d[i][j] < d[i][k] + d[k][j]:
          d[i][j] = d[i][k] + d[k][j]
  return d

def main():
  n, m, r = map(int, input().split())
  list_r = list(map(int, input().split()))
  list_cand = list(itertools.permutations(list_r))

  dist = [[float("inf") if i != j else 0 for j in range(n)] for i in range(n)]
  for i in range(m):
    a, b, c = map(int, input().split())
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c
  min_dist = warshall_floyd(dist)

  result = 10**100
  for one_cand in list_cand:
    temp = 0
    for i in range(r-1)
      temp += min_dist[one_cand[i]-1][one_cand[i+1]-1]
    if temp < result:
      result = temp
  print(result)

if __name__ == "__main__":
  main()

### FIXED CODE ###

from itertools import permutations
import sys

def main():
    
    N, M, R = map(int, sys.stdin.readline().split())
    r = [i - 1 for i in map(int, sys.stdin.readline().split())]
    
    d = [[float('inf')] * N for _ in range(N)]
    
    for i in range(N):
        d[i][i] = 0
        
    for i in range(M):
        a, b, c = map(int,sys.stdin.readline().split())
        d[a-1][b-1] = c
        d[b-1][a-1] = c
        
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    
    ans = 10**12
    
    for each in permutations(r):
        t_dis = 0
        for i in range(R-1):
            t_dis += d[each[i]][each[i+1]]  
        
        ans = min(ans, t_dis)
    
    print(ans)

if __name__ == '__main__':
    main()
n,k = map(int, input().split())
h = [int(input()) for i in range(n)]
h.sort()
minh = inf
for i in range(n-k+1):
    tmp = h[i+k-1] - h[i]
    minh = min(minh, tmp)
print(minh)

### FIXED CODE ###

inf = 10**9+7
mod = 10**9+7
n,k = map(int, input().split())
a = [int(input()) for i in range(n)]
a.sort()
minh = inf
for i in range(n-k+1):
    minh = min(minh, a[i+k-1]-a[i])
print(minh)
def binaryinsertion(A,x):
    left=0;right=len(A)-1;centre = 1 + len(A)//2
    while(True):
        if(right - left < 2):
            if(x[0]<A[left][0]):A.insert(left,x)
            else :
                if(x[0]<A[right][0]):A.insert(right,x)
                else:A.insert(right+1,x)
            break
        else:
            if(x[0] < A[centre][0]) :
                right = centre - 1
            elif(A[centre][0] < x[0]) :
                left = centre + 1
            else : 
                A.insert(centre,x)
                break
            centre = left + (right-left)//2 + 1

[N,L] = [int(x) for x in input().split()]
A = [[int(x),int(i)] for i,x in enumerate(input().split())]
sweep = A[:L]
sweep = sorted(sweep)
ans = [str(sweep[0][0])]
for i in range(L,N) :
    sweep.remove(A[i-L])
    binaryinsertion(sweep,A[i])
    ans.append(str(sweep[0][0]))
print(" ".join(ans))

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
from functools import reduce
l = [int(input()) for _ in range(5)]
r = [i % 10 for i in l if i % 10 != 0]
l = [i if i % 10 == 0 else i // 10 * 10 + 10 for i in l]
print(reduce(lambda a, b: a + b, l) + (min(r) - 10 if r else 0)

### FIXED CODE ###

import math
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
l = [a, b, c, d, e]
ans = 9
n = 0
j = 0
for i in [i % 10 for i in l]:
    if i != 0 and i < ans:
        ans = i
        n = j
    j += 1
m = l.pop(n)
r = 0
for i in l:
    r += math.ceil(i / 10) * 10
print(r + m)
N,W=map(int,input().split())
w=0
v=0
w_list=[]
v_list=[]
dp=[0]*(W+1)
for i in range (N):
    w,v=map(int,input().split())
    w_list.append(w)
    v_list.append(v)
for i in range (N):
    for j in range(0,W+1,-1):
        if j>=w_list[i]:
            dp[j]=max(dp[j],dp[j-w_list[i]]+v_list[i])
print(dp[-1])

### FIXED CODE ###

IN=lambda:map(int,input().split())
N,W=IN()
INF=float("inf")
dp=[INF]*(1000*N)
dp.insert(0,0)
c=0
ans=0
for i in range(N):
    w,v=IN()
    for j in range((1000*N+1),-1,-1):
        if dp[j-v]!=INF:
            dp[j]=min(dp[j],dp[j-v]+w)
for i in range(1000*N+1):
    if dp[i]<=W:
        ans=i
print(ans)
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

ans = []
tmp = []

for i in A:
	for j in B:
		tmp.append(i + j)
		
tmp.sort(reverse=True)

for i in range(K):
	for j in C:
		ans.append(tmp[i] + j)
		
ans.sort(reverse=True)

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


### FIXED CODE ###

import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

ans = []
tmp = []

for i in A:
	for j in B:
		tmp.append(i + j)
		
tmp.sort(reverse=True)

for i in range(min(K, len(tmp))):
	for j in C:
		ans.append(tmp[i] + j)
		
ans.sort(reverse=True)

for i in range(K):
	print(ans[i])
S = input()
S[3] = "8"
print(S)

### FIXED CODE ###

S = input()
print(S[:3] + "8" + S[4:])
A, B = list(map(int,input().split()))
if A or B == 0;
	print(A-B)

elif B%A ==0 :
	print(A+B)

else:
	print(A-B)

### FIXED CODE ###

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

if B%A ==0:
	print(A+B)

else:
	print(B-A)
a, b, h = map(int, input().split())

S = (a + b) * h /int(2)

print(S)

### FIXED CODE ###

a,b,h=map(int,open(0));print((a+b)*h//2)
import numpy as np
i,j=map(int,input().split())
mn=[]
n=[]
for _ in range(i):
    mn.append(list(map(int,input().split())))
for _ in range(j):
    n.append(int(input()))

x=np.array(mn)
y=np.array(n)
ret=x*y

for num in range(i):
    print(sum(ret[num]))

### FIXED CODE ###

i,j=map(int,input().split())
matrix=[list(map(int,input().split())) for _ in range(i)]
vector=[int(input()) for _ in range(j)]
for x in range(i):
    print(sum([v * m for v,m in zip(vector,matrix[x])]))
a,b = [int(i) for i in input().split()]
     
    souwa = 0
    n = b - a
    for i in range(n):
        souwa += i
         
    x = souwa - b
         
    print(x)

### FIXED CODE ###

a,b = [int(i) for i in input().split()]
     
souwa = 0
n = b - a
for i in range(n+1):
    souwa += i
         
x = souwa - b
         
print(x)
S = input()
    Q = int(input())
     
    # print(S, Q)
     
    queries = []
    for i in range(Q):
        query = input()
        queries.append(query)
     
    from collections import deque
    slist = deque()
	slist.append(S)
    for query in queries:
        if query == "1":
            isReversed = not isReversed
        else:
            t, f, c = query.split()
            if f == '1':
                if isReversed:
                    slist.append(c)
                else:
                    slist.appendleft(c)
            else:
                if isReversed:
                    slist.appendleft(c)
                else:
                    slist.append(c)
     
    if isReversed:
        slist.reverse()
    print("".join(slist))

### FIXED CODE ###

S = input()
Q = int(input())

queries = []
for i in range(Q):
    query = input()
    queries.append(query)

from collections import deque
slist = deque(list(S))
even = True
for query in queries:
    if query == "1":
        even = not even
    else:
        t, f, c = query.split()
        if f == '1':
            if even:
                slist.appendleft(c)
            else:
                slist.append(c)
        else:
            if even:
                slist.append(c)
            else:
                slist.appendleft(c)
if not even:
    slist.reverse()

print(''.join(slist))
n = int(input())
 
x = []
y = []
distance = []
 
for i in range(n):
  x1, y1 = input().split()
  x1 = int(x1)
  y1 = int(y1)
  x.append(x1)
  y.append(y1)
 
for i in range(len(x)):
  for j in range(i+1,len(x)):
    temp = abs(x[i] - x[j]) + abs(y[i] - y[j])
    distance.append(temp)

 
for i in range(len(distance)-1):
  if distance[i] >= distance[i+1]:
    a = distance[i]
 
print(a)

### FIXED CODE ###

x = int(input())
if x == 0:
  x = 1
else:
  x = 0
print(x)
def ans():
    if t==0:
        return "N0"
    if d/s < = t:
        return "Yes"
    else:
        return "No"
        
d, t, s = map(int, input().split())
print(ans())

### FIXED CODE ###

def ans():
    if t==0:
        return "N0"
    if d/s <= t:
        return "Yes"
    else:
        return "No"
        
d, t, s = map(int, input().split())
print(ans())
s=input()
k=int(input())
for i in range(len(s)):
    if s[i]!='1':
        a=s[i]
        break
print(1 if s[0:k]=='1'*k else a)

### FIXED CODE ###

s=input()
k=int(input())
a=1
for i in range(len(s)):
    if s[i]!='1':
        a=s[i]
        break
print(1 if k<=len(s) and s[0:k]=='1'*k else a)
n = int(input())
al = list(map(int,input().split()))

ansl = [0] * 9

for a in al:
    ansl[a//400] += 1

min_ans = 0
for a in ansl[:8]:
    if a > 0:
        min_ans += 1

max_ans = min_ans
if ansl[-1] > 0:
    if min_ans == 0:
        min_ans += 1
        max_ans += ansl[-1]
    else:
        max_ans = min_ans + ansl[-1]

print(min_ans, max_ans)

### FIXED CODE ###

color = [0 for i in range(8)]

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

p = 0
for a in al:
    if a < 3200:
        color[a//400] = 1
    else:
        p += 1
print(max(sum(color), 1))
print(sum(color) + p)
N, K = map(int, input().split())
h = [int(input()) for _ in range(N)]

h.sort()
ans = 10**10

for i in range(N - K + 1):
    ans_ = h[i + 2] - h[i]
    ans = min(ans, ans_)

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(input()) for _ in range(N)]

h.sort()
ans = 10**10

for i in range(N - K + 1):
    ans_ = h[i + K - 1] - h[i]
    ans = min(ans, ans_)

print(ans)
size, jumps = map(int, input().split())
array =  list(map(int, input().split()))
dp = [0]* size
for i in range(1,size):
	for j in range(i,jumps):	
			dp[j] = min(dp[j],abs(array[i] - array[j]))
print(dp[-1])
		


### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


def main():
    size, jumps = map(int, input().split())
    array = list(map(int, input().split()))
    dp = [999999999] * size
    dp[0]= 0
    dp[1] = abs(array[0]- array[1])
    for i in range(2,size):
        dp[i] = min(abs(array[i] - array[j]) + dp[j] for j in range(max(0, i - jumps), i))
    print(dp[size-1])

if __name__ == "__main__":
    main()
a = int(input())
b = int(input())
if 1<=a<=9 and 1<=b<=9:
  print(a*b)
else:
  print(-1)

### FIXED CODE ###

arr = input().split()
a = int(arr[0])
b = int(arr[1])

#b = int(input())
if 1<=a<=9 and 1<=b<=9:
  print(a*b)
else:
  print(-1)
import collections
from scipy.sparse import lil_matrix
from scipy.sparse.csgraph import bellman_ford

N, M, P = [int(_) for _ in input().split()]
#for multiple edges
ABC = sorted([[int(_) for _ in input().split()] for _ in range(M)], key=lambda xs:xs[2])
cd = collections.defaultdict
Ga = cd(set)
Gb = cd(set)
ok = cd(int)
for a, b, c in ABC:
    Ga[a].add(b)
    Gb[b].add(a)
#dfs
for pair in [[1, Ga], [N, Gb]]:
    S = pair
    Gn = pair.pop()
    visited = [0] * (N + 1)
    while S:
        s = S.pop()
        if not visited[s]:
            visited[s] = 1
            ok[s] += 1
            for ns in Gn[s]:
                S += [ns]
G = lil_matrix((N + 1, N + 1))
for a, b, c in ABC:
    if ok[a] == ok[b] == 2:
        G[a, b] = P - c

dist_matrix = bellman_ford(G, directed=True, indices=[1])
print(max(-int(dist_matrix[0][-1]), 0))


### FIXED CODE ###

import collections
N, M, P = [int(_) for _ in input().split()]
ABC = [[int(_) for _ in input().split()] for _ in range(M)]
cd = collections.defaultdict
Ga = cd(set)
Gb = cd(set)
G = []
ok = cd(int)
for a, b, c in ABC:
    Ga[a].add(b)
    Gb[b].add(a)
#dfs
for pair in [[1, Ga], [N, Gb]]:
    S = pair
    Gn = pair.pop()
    visited = [0] * (N + 1)
    while S:
        s = S.pop()
        if not visited[s]:
            visited[s] = 1
            ok[s] += 1
            for ns in Gn[s]:
                S += [ns]
for a, b, c in ABC:
    if ok[a] == ok[b] == 2:
        G += [(a, b, P - c)]


def bellman_ford(V, G, i):
    INF = float('inf')
    D = [INF] * V
    D[i] = 0
    for _ in range(V):
        update = False
        for s, t, d in G:
            if D[s] != INF and D[t] > D[s] + d:
                D[t] = D[s] + d
                update = True
        if not update:
            return D
        if _ == V:
            return False


a = bellman_ford(N + 1, G, 1)
try:
    print(max(-a[-1], 0))
except:
    print(-1)
hash_no = 10 ** 9 + 7
x, y = map(int, input().split())

counter = 0


def move(x, y, X, Y):
    global counter
    if x >X:
        return
    if y > Y:
        return
    if (x == X) and (y == Y):
        counter += 1
        return

    move(x + 1, y + 2, X, Y)
    move(x + 2, y + 1, X, Y)


move(0, 0, x, y)
print(counter / hash_no)

### FIXED CODE ###

# AtCoder Beginner Contest 145 D - Knight
import sys
from math import factorial

mod = 10 ** 9 + 7

X, Y = map(int, sys.stdin.readline().strip().split())

# 合計の移動回数は Total = X + Y / 3 
# 移動方法は A: (i + 1, j + 2)  B: (i + 2, j + 1) の2通り
# 移動回数は A: 2 * Total - X  B: X - Total 

# 到達不可能であるか判断する
if (X + Y) % 3 != 0:
    print(0)
    sys.exit()

if Y > 2 * X or Y < X * 0.5:
    print(0)
    sys.exit()


Total = (X + Y) // 3
A = Total * 2 - X
B = X - Total

# combination の計算
ans = 1
for i in range(1, Total + 1):
    ans *= i
    ans %= mod

ans = ans * pow(factorial(A), mod - 2, mod)
ans = ans * pow(factorial(B), mod - 2, mod)

print(ans % mod)