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

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


x,y = map(int,input().split())

mod = 10**9+7

division = (x+y)//3

if (x+y)%3!=0:
    print(0)
    exit()


mod = 10**9+7

#combを求める前処理 O(log division)
g1 = [1, 1] #元テーブル
g2 = [1, 1] #逆元テーブル

for i in range( 2, division + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    g2.append( pow(g1[-1],mod-2,mod) )

r = min(x,y)-division
ans = cmb(division,r,mod)

print(ans)

### FIXED CODE ###

x,y = map(int,input().split())

mod = 10**9+7

division = (x+y)//3

if [x%3,y%3] in [[1,1],[2,2]]:
    print(0)
    exit()

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )



r = min(x,y)-division
ans = cmb(division,r,mod)

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

import functools
import operator

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

ans = functools.reduce(operator.mul, a)

if (ans > 10**18):
  print('-1')
else:
  print(ans)


### FIXED CODE ###

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

ans = 1
for i in range(N):
  ans = ans * a[i]
  if (ans > 10 ** 18):
    break
  
if (ans > 10**18):
  if a.count(0) > 0:
    print(0)
  else:
    print(-1)
else:
  print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
pl = list(map(int, input().split()))
# dp = [0] * n

dp = [(i + 1)/2 for i in pl]
pmax = [0] * (n-k+1)

for i in range(n-k+1):
    pmax[i] = sum(dp[i:i+k])

print(max(pmax))

### FIXED CODE ###

n, k = map(int, input().split())
pl = list(map(int, input().split()))

dp = [0] * (n + 1)

for i in range(n):
    dp[i+1] = dp[i] + (pl[i] + 1)/2

ans = 0
for i in range(k, n+1):
    ans = max(ans, dp[i] - dp[i-k])

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

import bisect

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

ok = N-1
ng = -1
mid = (ok+ng)//2
while ok - ng > 1:
    if mid >= N - P:
        ok = mid
        continue
    K = A[mid] + M
    if K < A[N - P]:
        ng = mid
        mid = (ok+ng)//2
        continue
    p = M * (V-P)
    flg = 0
    for i in range(mid):
        p -= M
        if p <= 0:
            flg = 1
            break
    if flg:
        ok = mid
        mid = (ok+ng)//2
        continue
    for i in range(mid+1, N - (P-1)):
        p -= K - A[i]
        if p <= 0:
            flg = 1
            break
    if flg:
        ok = mid
        mid = (ok+ng)//2
    else:
        ng = mid
        mid = (ok+ng)//2

print(N - ok)


### FIXED CODE ###

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

ok = N-1
ng = -1
mid = (ok+ng)//2
while ok - ng > 1:
    if mid >= N - P:
        ok = mid
        mid = (ok+ng)//2
        continue
    K = A[mid] + M
    if K < A[N - P]:
        ng = mid
        mid = (ok+ng)//2
        continue
    p = M * (V-P)
    flg = 0
    for i in range(mid):
        p -= M
        if p <= 0:
            flg = 1
            break
    if flg:
        ok = mid
        mid = (ok+ng)//2
        continue
    for i in range(mid+1, N - (P-1)):
        p -= K - A[i]
        if p <= 0:
            flg = 1
            break
    if flg:
        ok = mid
        mid = (ok+ng)//2
    else:
        ng = mid
        mid = (ok+ng)//2

print(N - ok)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
ans = []

for i in range(1,n+1):
    ans.append(a.index(i)+1)
print(*ans)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
ans = [0]*(n+1)

for i,j in enumerate(a):
    ans[j]=i+1
print(*ans[1:])
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
grid = []
graph = [[2000 for i in range(w)] for j in range(h)]
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False

#graph => そこまでの距離を保存した二次元配列　grid=>与えられた迷路
def bfs(que):
    finished = set()
    while que:
        x , y, cost = que.popleft()
        if (grid[y][x] == '#' and cost != 0):
            continue
        if (x,y) not in finished and graph[y][x] > cost:
            finished.add((x,y))
            graph[y][x] = cost
            if check(y,x+1):
                que.append([x+1,y,cost+1])
            if check(y+1,x):
                que.append([x, y+1, cost+1])
            if check(y,x-1):
                que.append([x-1,y,cost+1])
            if check(y-1,x):
                que.append([x,y-1,cost+1])
for i in range(h):
    grid.append(list(input()))
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            que = deque([(j,i,0)])
            bfs(que)
ans = 0
for i in range(h):
    ans = max(ans, max(graph[i]))
print(ans)

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
grid = []
graph = [[2000 for i in range(w)] for j in range(h)]
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False

#graph => そこまでの距離を保存した二次元配列　grid=>与えられた迷路
def bfs(que):
    finished = set()
    while que:
        x ,y = que.popleft()
        if y*w+x not in finished:
            finished.add(y*w+x)
            for n_x,n_y in [(x+1,y),(x,y+1),(x-1,y),(x,y-1)]:
                if check(n_y,n_x) and graph[n_y][n_x] > graph[y][x] + 1:
                    graph[n_y][n_x] = graph[y][x] + 1
                    que.append((n_x,n_y))
for i in range(h):
    grid.append(list(input()))
que = deque()
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            graph[i][j] = 0
            que.append((j,i))
bfs(que)
ans = 0
for i in range(h):
    ans = max(ans, max(graph[i]))
print(ans)
### BUGGY CODE ###

from collections import deque
n,m=map(int,input().split())
ab=[[] for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  ab[a].append(b)
  ab[b].append(a)
l,ll=deque([1]),deque([])
ans=[-1]*n
while l:
  x=l.popleft()
  ll.append(x)
  for i in ab[x]:
    if i in ll:
      continue
    if i in l:
      continue
    l.append(i)
    ans[i-1]=x
print('Yes')
for i in ans[1:]:
  print(i) 

### FIXED CODE ###

def main():
  from collections import deque
  n,m=map(int,input().split())
  ab=[[] for _ in range(n+1)]
  for _ in range(m):
    a,b=map(int,input().split())
    ab[a].append(b)
    ab[b].append(a)
  
  l=deque([1])
  ans=[-1]*n
  while l:
    x=l.popleft()
    for i in ab[x]:
      if ans[i-1]==-1:
        ans[i-1]=x
        l.append(i)
  print('Yes')
  for i in ans[1:]:
    print(i) 
    
if __name__=='__main__':
  main()
### BUGGY CODE ###

# coding:utf-8
# Doubly Linked List

class DLL:

    def __init__(self):
        self.array = []

    def insert(self, x):
        self.array = [x] + self.array
    
    def delete(self, x):
        try:
            del self.array[self.array.index(x)]
        except:
            pass

    def deleteFirst(self):
        del self.array[0]

    def deleteLast(self):
        del self.array[len(self.array)-1]


def main():

    dll = DLL()
    n = int(input())
    ans = ""
    
    for _ in range(n):
        operation = input().split()
        command = operation[0]
        if len(command) == 6:
            key = str(operation[1])
            if command == "insert":
                dll.insert(key)
            else:
                dll.delete(key)

        else:
            if command[6] == 'F':
                dll.deleteFirst()
            else:
                dll.deleteLast()

    for value in dll.array:
        ans += str(value) + " "

    print(ans.rstrip())

if __name__ == "__main__":
    main()

### FIXED CODE ###

# coding:utf-8
# Doubly Linked List

from collections import deque

def main():

    n = int(input())
    dll = deque()

    for _ in range(n):
        operation = input().split(' ')
        if operation[0] in ["insert", "delete"]:
            key = operation[1]
            if operation[0] == "insert":
                dll.appendleft(key)
            else:
                try:
                    dll.remove(key)
                except:
                    pass

        else:
            if operation[0][6] == 'F':
                dll.popleft()

            else:
                dll.pop()

    print(' '.join(dll))

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

S = input()
x=1
ans=0
for i in range(len(S)-3):
    j=4
    while i+j <= len(S):
        if int(S[i:i+j])%2019==0:
            ans+=1
            j+=4
        else:
            j+=1
print(ans)

### FIXED CODE ###

S = input()
T = [0]*2019
T[0]=1
t = 0
ans = 0
dig = 1
for i in range(len(S)):
    t = (t + (int(S[-i-1]))*dig)%2019
    dig = (dig*10)%2019
    T[t] += 1
for j in T:
    ans +=int(j*(j-1)/2)
print(ans)
### BUGGY CODE ###

x,k,d=map(int,input().split())
def counta(x,k,d):
    #xcnt=0
    x=abs(x)
    if d<2*x:
        while x>=d:
            x-=d
            k-=1
            if k==0:
                print(abs(x))
                return
        if k%2==0:
            print(x)
            return
        else:
            print(abs(x-d))
            return
    else:
        if k%2==0:
            print(x)
            return
        else:
            print(abs(x-d))
            return
counta(x,k,d)

### FIXED CODE ###

x,k,d=map(int,input().split())

def counta(x,k,d):
    #xcnt=0
    x=abs(x)
    if d<2*x:
        ans=x//d
        #amari=x%d
        if ans>k:
            print(abs(x-k*d))
            return
        k=k-ans
        x=x-ans*d
        if k%2==0:
            print(x)
            return
        else:
            print(abs(x-d))
            return
    else:
        if k%2==0:
            print(x)
            return
        else:
            print(abs(x-d))
            return
counta(x,k,d)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    g[u].append(v)
mi=set(range(n))
flg=False
def dfs(v,seen):
    for nv in g[v]:
        if seen[nv]!=-1:# 巡回閉路
            seen[nv]=v
            return nv
        else:
            seen[nv]=v
            t=dfs(nv,seen)
            if t!=-1:return t
            seen[nv]=-1
    return -1
while mi:
    v=mi.pop()
    seen=[-1]*n
    f=dfs(v,seen)
    if f!=-1:break
if f==-1:
    print(-1)
    exit()
ff=f
path={f}
while seen[f] not in path:
    f=seen[f]
    path.add(f)

#print(seen,path,ff)
from collections import deque
todo=deque([ff])
seen=[[-1,-1] for _ in '_'*n]
d=0
seen[ff][1]=d
flg=False
start=[-1,-1]
while todo:
    v=todo.popleft()
    d+=1
    for nv in g[v]:
        if nv in path:
            if seen[nv][1]!=-1:
                seen[nv][0]=v
                if start[0]==-1:
                    start=[nv,seen[nv][1]]
                else:
                    if start[1]<seen[nv][1]:
                        start=[nv,seen[nv][1]]
                flg=True
            else:
                todo.append(nv)
                seen[nv]=[v,d]
    if flg:break
s=nv
ans=[s+1]
#print(seen,nv)
while seen[nv][0]!=s:
    nv=seen[nv][0]
    ans.append(nv+1)

print(len(ans))
print(*ans,sep='\n')


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  g[u].append(v)
mi=set(range(n))
flg=False
def func(path):
  chk=set(path)
  if len(path)!=2:
    for i,v in enumerate(path):
      nvs=[nv for nv in g[v] if nv in chk]
      if len(nvs)==1:continue
      for nv in nvs:
        if nv==path[(i+1)%len(path)]:continue
        ary=[nv]
        for j,vj in enumerate(path):
          if vj==nv:break
        if i>j:
          ary=path[j:i+1]
        else:
          ary=path[:i+1]+path[j:]
        #print(path,ary,i,j)
        func(ary)
  print(len(path))
  for v in path:
    print(v+1)
  exit()

def dfs(v,seen):
  mi.discard(v)
  for nv in g[v]:
    if seen[nv]!=-1:# 巡回閉路
      seen[nv]=v
      path=[v]
      chk={v}
      while seen[v] not in chk:
        v=seen[v]
        path.append(v)
        chk.add(v)
      path.reverse()
      func(path)
    else:
      seen[nv]=v
      dfs(nv,seen)
      seen[nv]=-1
while mi:
  v=mi.pop()
  seen=[-1]*n
  dfs(v,seen)
print(-1)
exit()
### BUGGY CODE ###

x=input().split()
h=int(x[0])
w=int(x[1])
d=int(x[2])
grid=[[]*w for i in range(h)]
for i in range(h):
    y=input().split()
    x=0
    while x<w:
        y[x]=int(y[x])
        x=x+1
    grid[i]=y
coor=[[]*2 for i in range(h*w)]
for i in range(h):
    for j in range(w):
        coor[grid[i][j]-1]=[i,j]
q=int(input())
for ii in range(q):
    x=input().split()
    l=int(x[0])
    r=int(x[1])
    cost=0
    while l!=r:
        cost+=abs(coor[l+d-1][0]-coor[l-1][0])+abs(coor[l+d-1][1]-coor[l-1][1])
        l+=d
    print(cost)

### FIXED CODE ###

x=input().split()
h=int(x[0])
w=int(x[1])
d=int(x[2])
grid=[[]*w for i in range(h)]
for i in range(h):
    y=input().split()
    x=0
    while x<w:
        y[x]=int(y[x])
        x=x+1
    grid[i]=y
coor=[[]*2 for i in range(h*w)]
for i in range(h):
    for j in range(w):
        coor[grid[i][j]-1]=[i,j]
cost=[0*i for i in range(h*w-d)]
for i in range(h*w-d):
    cost[i]=abs(coor[i+d][0]-coor[i][0])+abs(coor[i+d][1]-coor[i][1])
ans=[0*i for i in range(h*w)]
for i in range(d,h*w):
    ans[i]=ans[i-d]+cost[i-d]
q=int(input())
for ii in range(q):
    x=input().split()
    l=int(x[0])
    r=int(x[1])
    print(ans[r-1]-ans[l-1])
### BUGGY CODE ###

BUFSIZE = 100
D = int(input())
C = list(map(int, input().split()))

c0 = sum(C)
Q = [(0, [], 0, [0]*26)]

for d in range(D):
    S = list(map(int, input().split()))
    Q2 = []
    
    for q in Q:
        sc, ts, c1, lasts = q
        c2 = c1 + c0

        for t in range(26):
            c3 = c2 - (d + 1 - lasts[t])*C[t]
            lasts2 = lasts[:]
            lasts2[t] = d+1
            Q2.append((sc + S[t] - c3, [ts, t], c3, lasts2))

    sizeOfQ2 = len(Q2)
    Q = sorted(Q2, reverse=True)[:min(sizeOfQ2, BUFSIZE)]

# print(Q[0][0])
T = []
ts = Q[0][1]

for d in range(D):
    T.append(ts[1] + 1)
    ts = ts[0]

for t in reversed(T):
    print(t)




### FIXED CODE ###

BUFSIZE = 30
D = int(input())
C = list(map(int, input().split()))

c0 = sum(C)
Q = [(0, [], 0, [0]*26)]

for d in range(D):
    S = list(map(int, input().split()))
    Q2 = []
    
    for q in Q:
        sc, ts, c1, lasts = q
        c2 = c1 + c0

        for t in range(26):
            c3 = c2 - (d + 1 - lasts[t])*C[t]
            lasts2 = lasts[:]
            lasts2[t] = d+1
            Q2.append((sc + S[t] - c3, [ts, t], c3, lasts2))

    sizeOfQ2 = len(Q2)
    Q = sorted(Q2, reverse=True)[:min(sizeOfQ2, BUFSIZE)]

# print(Q[0][0])
T = []
ts = Q[0][1]

for d in range(D):
    T.append(ts[1] + 1)
    ts = ts[0]

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

m = 10**6

def MyHash(k,i):
    return (k%m+i*(1+(k%m)))%m

def main():
    n = input()
    T = ['']*10**6
    O = []
    for i in range(n):
        c, k = raw_input().split()
        i = 0
        if c == 'insert':
            k_hashed = hash(k)
            while True:
                j = MyHash(k_hashed,i)
                if T[j] == '':
                    T[j] = k
                    break
                else:
                    i += 1
        else:
            O.append(search(T,k))

    for item in O:
        print item

    return 0


def search(T,k):
    k_hashed = hash(k)
    i = 0
    while True:
        j = MyHash(k_hashed,i)
        if T[j] == k:
            o = 'yes'
            break
        elif T[j] == '':
            o = 'no'
            break
        else:
            i += 1

    return o


if __name__ == "__main__":
    main()

### FIXED CODE ###

m = 2000003

def MyHash(k,i):
    return (k%m+i*(1+(k%m)))%m

def main():
    n = input()
    T = ['']*2000003
    O = []
    for i in range(n):
        c, k = raw_input().split()
        i = 0
        if c == 'insert':
            k_hashed = hash(k)
            while True:
                j = MyHash(k_hashed,i)
                if T[j] == '':
                    T[j] = k
                    break
                else:
                    i += 1
        else:
            O.append(search(T,k))

    for item in O:
        print item

    return 0


def search(T,k):
    k_hashed = hash(k)
    i = 0
    while True:
        j = MyHash(k_hashed,i)
        if T[j] == k:
            o = 'yes'
            break
        elif T[j] == '':
            o = 'no'
            break
        else:
            i += 1

    return o


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

N=int(input())
A=list(map(int,input().split()))
A.sort()
C=[]
i=0
while len(A)>0:
    c=len(A)
    a=A[0]
    del A[0]
    if a not in A:
        C.append(a)
    A=[A[j] for j in range(c-1) if A[j]%a!=0]
print(len(C))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort()
TF={a:True for a in A}
for i in range(N):
    if TF[A[i]]==True:
        if i > 0 and A[i - 1] == A[i]:
            TF[A[i]] = False
        m=A[N-1]//A[i]
        for j in range(2,m+1):
            s=A[i]*j
            if s in TF:
                TF[s]=False
print(len([1 for a in A if TF[a]==True]))
### BUGGY CODE ###


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

INF = 1 << 29

"""
・dp[bit][s]
ビットに1が立っているカードはソートされて左から並んでいる。
そのとき最後の値をsにするのに必要な最小操作回数


"""
# 1 <= A,B <= 50, bitの立ち方が 0...0 ~ 1...1 の2**N
dp = [[INF for _ in range(50 + 1)] for _ in range((1 << N))]
# 0枚選んでいて右端が0は何もしてないのでコスト0
dp[0][0] = 0

for bit in range(1 << N):
    # 現在見ているbit列にいくつ1が立っているか＝カードを何枚既に選んで並べているか
    num_used = bin(bit).count("1")
    
    # bitで１が立っていない＝まだ使われていないカードがどこにあるか
    idx = num_used
    remaining = []
    for i in range(N):
        if not (bit & (1 << i)):
            # 一つ目が初期位置、二つ目は、bitで１が立っているやつらを左に寄せた時にどの位置にいるか
            remaining.append((i, idx))
            idx += 1

    for s in range(51):
        # bitの集合かつ、その右端にsの状態が作れないならスキップ
        if dp[bit][s] >= INF:
            continue

        for ini, curr in remaining:
            """
            ini  : initial position
            curr : current position
            現時点でnum_used-1のインデックスまでカードがソートされて並んでいる
            最初iniの位置にあったカードを最後尾に並べることを考える
            """
            num = A[ini] if abs(ini - num_used) % 2 == 0 else B[ini]

            """
            numが並んでるカードの最後尾より大きければ最後尾につける
            """
            if num >= s:
                # 元の集合と、iniの位置だけ１が立ってるものの論理和で、追加した状態を表す
                # その場合の最小コストは、既に求まっているもの or 新たにnum_usedの位置にiniのカードをあてたとき　の小さいほう
                dp[bit | (1 << ini)][num] = min(dp[bit | (1 << ini)][num], dp[bit][s] + abs(num_used - curr))



# 全てのbitに1が立っている（全て並べ切った）時の最小コストが答え
ans = min(dp[-1][s] for s in range(51))

print(ans if ans < INF else -1)


### FIXED CODE ###



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

INF = 1 << 29

"""
・dp[bit][s]
ビットに1が立っているカードはソートされて左から並んでいる。
そのとき最後の値をsにするのに必要な最小操作回数


"""
# 1 <= A,B <= 50, bitの立ち方が 0...0 ~ 1...1 の2**N
dp = [[INF for _ in range(50 + 1)] for _ in range((1 << N))]
# 0枚選んでいて右端が0は何もしてないのでコスト0
dp[0][0] = 0

for bit in range(1 << N):
    # 現在見ているbit列にいくつ1が立っているか＝カードを何枚既に選んで並べているか
    num_used = bin(bit).count("1")
    
    # bitで１が立っていない＝まだ使われていないカードがどこにあるか
    idx = num_used
    remaining = []
    for i in range(N):
        if not (bit & (1 << i)):
            # 一つ目が初期位置、二つ目は、bitで１が立っているやつらを左に寄せた時にどの位置にいるか
            remaining.append((i, idx))
            idx += 1

    for s in range(51):
        # bitの集合かつ、その右端にsの状態が作れないならスキップ
        if dp[bit][s] >= INF:
            continue

        for ini, curr in remaining:
            """
            ini  : initial position
            curr : current position
            現時点でnum_used-1のインデックスまでカードがソートされて並んでいる
            最初iniの位置にあったカードを最後尾に並べることを考える
            """
            num = A[ini] if abs(ini - num_used) % 2 == 0 else B[ini]

            """
            numが並んでるカードの最後尾より大きければ最後尾につける
            """
            if num >= s:
                # 元の集合と、iniの位置だけ１が立ってるものの論理和で、追加した状態を表す
                # その場合の最小コストは、既に求まっているもの or 新たにnum_usedの位置にiniのカードをあてたとき　の小さいほう
                dp[bit | (1 << ini)][num] = min(dp[bit | (1 << ini)][num], dp[bit][s] + abs(num_used - curr))



# 全てのbitに1が立っている（全て並べ切った）時の最小コストが答え
ans = min(dp[-1][s] for s in range(51))

print(ans if ans < INF else -1)
### BUGGY CODE ###

import sys
from collections import defaultdict
from heapq import heappush, heappop, heapify
input = sys.stdin.readline

INF = 10**12
n, m, s = map(int, input().split())
edges = defaultdict(lambda: defaultdict(lambda: [INF, INF]))
cd = []
max_a = 0

for i in range(m):
    u, v, a, b = map(int, input().split())
    max_a = max(max_a, a)
    edges[u-1][v-1] = [a, b]
    edges[v-1][u-1] = [a, b]

for i in range(n):
    c, d = map(int, input().split())
    cd.append([c, d])

# 解答ACする
# Dijakstraの状態を(頂点、所持している銀貨の枚数, cost)で持つ
def dijakstra(goal):
    # SIZE = max_a * n + 1
    SIZE = 2501
    global s
    if s > SIZE:
        s = SIZE
    nodes = [[INF for _ in range(SIZE)] for _ in range(n)]
    nodes[0][1] = 0
    que = [(0, 0, s)]
    heapify(que)
    while len(que) > 0:
        # print(que[:3])
        cost, num, silver = heappop(que)
        # print(cost, num, silver)
        if num == goal:
            return cost
        c, d = cd[num]
        for v in edges[num].keys():
            a, b = edges[num][v]

            times = -1
            to = silver - a
            while to < SIZE:
                times += 1
                plus = times * c
                to = silver + plus - a
                if to < 0:
                    continue
                if to >= SIZE:
                    break
                if nodes[v][to] > cost + b + d * times:
                    nodes[v][to] = cost + b + d * times
                    heappush(que, (cost + b + d * times, v, to))

for i in range(1, n):
    print(dijakstra(i))




### FIXED CODE ###

ic=lambda i,c:i+c*50
n,m,s=map(int,input().split())
edge=[[]for _ in range(125100)]
for _ in range(m):
  u,v,a,b=map(int,input().split())
  u-=1
  v-=1
  for i in range(a,2501):
    edge[ic(u,i)].append((ic(v,i-a),b))
    edge[ic(v,i)].append((ic(u,i-a),b))
for i in range(n):
  c,d=map(int,input().split())
  for j in range(c,2501):
    edge[ic(i,j-c)].append((ic(i,j),d))
from heapq import heappop,heappush
def dijkstra(s,n,edge):
  inf=10**20
  ans=[inf]*n
  ans[s]=0
  h=[[0,s]]
  while h:
    c,v=heappop(h)
    if ans[v]<c:continue
    for u,t in edge[v]:
      if c+t<ans[u]:
        ans[u]=c+t
        heappush(h,[c+t,u])
  return ans
d=dijkstra(ic(0,min(2500,s)),125100,edge)
ans=[0]+[10**20]*(n-1)
for i in range(1,n):
  for j in range(2501):ans[i]=min(ans[i],d[ic(i,j)])
print(*ans[1:])
### BUGGY CODE ###

R, G , B, N = map(int, input().split())
cnt = 0
for i in range(3001):
    for j in range(3001):
        if i*R+j*G <= N and (N-i*R-j*G) % B == 0:
            cnt += 1
print(cnt)

### FIXED CODE ###

R, G , B, N = map(int, input().split())
cnt = 0
for i in range(3001):
    for j in range(3001):
        if i*R+j*G <= N and (N-i*R-j*G) % B == 0:
            cnt += 1
print(cnt)
### BUGGY CODE ###

N = int(input())

ans = 1

for i in range(N):

    ans *= i+1

print (ans % (10**9+7))

### FIXED CODE ###

import math


N = int(input())

print (math.factorial(N) % (10**9+7))
### BUGGY CODE ###

N = int(input())
a = []
for i in range(N):
    inputs = int(input())
    if inputs in a:
        a.remove(inputs)
    else:
        a.append(inputs)

print(len(a))


### FIXED CODE ###

from collections import Counter
N = int(input())
a = []
for i in range(N):
    inputs = int(input())
    a.append(inputs)
    
ans = dict(Counter(a))
ans1 = [kv[0] for kv in ans.items() if kv[1]%2==1]

print(len(ans1))