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

n,m,l = map(int,input().split())
road = [[] for _ in range(n)]
for _ in range(m):
  a,b,c = map(int,input().split())
  a -= 1
  b -= 1
  road[a].append([b,c])
  road[b].append([a,c])
cango = []
for i in range(n):
  tmp = [l+1 for _ in range(n)]
  tmp[i] = 0
  now = [[i,0]]
  while now:
    last = now
    now = []
    for x in last:
      for yz in road[x[0]]:
        y,z = yz
        if x[1] + z < tmp[y]:
          tmp[y] = x[1] + z
          now.append([y,tmp[y]])
  add = []
  for i in range(n):
    if 0 < tmp[i] <= l:
      add.append(i)
  cango.append(add)
q = int(input())
for _ in range(q):
  s,t = map(int,input().split())
  s -= 1
  t -= 1
  tmp = [-1 for _ in range(n)]
  tmp[s] = 0
  time = 0
  now = [s]
  while now:
    time += 1
    last = now
    now = []
    for x in last:
      for y in cango[x]:
        if tmp[y] == -1:
          tmp[y] = time - 1
          now.append(y)
    if tmp[t] != -1:
      print(tmp[t])
      break
  else:
    print(tmp[t])

### FIXED CODE ###

n,m,l = map(int,input().split())
road = [[10**18 for _ in range(n)] for _ in range(n)]
for _ in range(m):
  a,b,c = map(int,input().split())
  a -= 1
  b -= 1
  road[a][b] = c
  road[b][a] = c
#print(road)
for k in range(n):
  for i in range(n):
    for j in range(n):
      road[i][j] = min(road[i][j],road[i][k]+road[k][j])
#print(road)
cango = [[1000 for _ in range(n)] for _ in range(n)]
for i in range(n):
  for j in range(n):
    if road[i][j] == 0:
      cango[i][j] = 0
    elif road[i][j] <= l:
      cango[i][j] = 1
#print(cango)
for k in range(n):
  for i in range(n):
    for j in range(n):
      cango[i][j] = min(cango[i][j],cango[i][k]+cango[k][j])
#print(cango)
q = int(input())
for _ in range(q):
  s,t = map(int,input().split())
  ans = cango[s-1][t-1]-1
  if ans > 500:
    print(-1)
  else:
    print(ans)
### BUGGY CODE ###

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

for i in range(1,A*B+1):
    if i%A==0 and i%B==0:
        print(i)
        break


### FIXED CODE ###

A,B=map(int,input().split())
def gcd(A,B):
    while B!=0:
        A,B=B,A%B
    return A
print(int(A*B/gcd(A,B)))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

n, m = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
    x, y = map(int, input().split())
    edge[x-1].append(y-1)
dp = [-1]*n
    
def calc(x):
    if dp[x] != -1:
        return dp[x]
    if not len(edge[x]):
        dp[x] = 0
        return 0
    dp[x] = max(calc(i) for i in edge[x])+1
    return dp[x]
    
ans = 0
for i in range(n):
    ans = max(ans, calc(i))
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    edge[x-1].append(y-1)
dp = [-1]*N

def calc(x):
    if dp[x]!=-1:
        return dp[x]
    if not len(edge[x]):
        dp[x] = 0
        return 0
    dp[x] = max([calc(i) for i in edge[x]])+1
    return dp[x]

ans = 0
for i in range(N):
    if dp[i] != -1: continue
    ans = max(ans, calc(i))
print(ans)
### BUGGY CODE ###

import itertools

n, m = map(int, input().split())
a=list(map(int,input().split()))
b =[0]+ list(itertools.accumulate(a))
count=0

for i in range(n):
    for j in range(i+1,n+1):
        if (b[j]-b[i])%m==0:
            count+=1
print(count)


### FIXED CODE ###

import itertools
import collections

n, m = map(int, input().split())
a=list(map(int,input().split()))
b =[0]+ list(itertools.accumulate(a))
count=0
for i in range(n+1):
    b[i]=b[i]%m

b=collections.Counter(b)
b=b.most_common()

for i in range(len(b)):
    if b[i][1]>=2:
        count+=b[i][1]*(b[i][1]-1)//2
    else:
        break
print(count)
### BUGGY CODE ###

N = int(input())
t = x = y = [0]
for i in range(N):
  tn,xn,yn = map(int,input().split())
  t = t+[tn]
  x = x+[xn]
  y = y+[yn]
  dt = t[i+1]-t[i]
  d = abs(x[i+1]-x[i])+abs(y[i+1]-y[i])
  if d <= dt and dt%2 == d%2:
    isValid = True
  else:
    isValid = False
    break
print("Yes" if isValid else "No")

### FIXED CODE ###

N = int(input())
t = x = y = 0
for i in range(N):
  tn,xn,yn = map(int,input().split())
  dt = tn-t
  d = abs(xn-x)+abs(yn-y)
  if d <= dt and dt%2 == d%2:
    t,x,y = tn,xn,yn
    isValid = True
  else:
    isValid = False
    break
print("Yes" if isValid else "No")
### BUGGY CODE ###

X, Y, A, B, C = map(int,input().split())
p = list(map(int,input().split()))
q = list(map(int,input().split()))
r = list(map(int,input().split()))

p.sort()
p.reverse()
q.sort()
q.reverse()

d = 0
x = 0
y = 0

while x < X and y < Y:
    a = max(p)
    b = max(q)
    c = max(r)
    if a >= c:
        d += a
        x += 1
        p.remove(a)
    elif b >= c:
        d += b
        y += 1
        q.remove(b)
    elif c > a >= b:
        d += c
        y += 1
        r.remove(c)
    elif c > b > a:
        d += c
        x += 1
        r.remove(c)

while x < X:
    p.extend(r)
    d += max(p)
    x += 1
    p.remove(max(p))
while y < Y:
    q.extend(r)
    d += max(q)
    y += 1
    q.remove(max(q))
print(d)


### FIXED CODE ###

X, Y, A, B, C = map(int,input().split())
p = list(map(int,input().split()))
q = list(map(int,input().split()))
r = list(map(int,input().split()))

p.sort()
p.reverse()
q.sort()
q.reverse()
del p[X:]
del q[Y:]
p.extend(q)
p.extend(r)
p.sort()
p.reverse()
del p[X+Y:]
d = sum(p)
print(d)
### BUGGY CODE ###

from itertools import permutations

INF = 10**18

def solve(h, w, c, a):
    v = list(range(10))
    dp = [INF] * 10
    for p in permutations(v):
        cost = 0
        for i in range(10):
            if p[i] == 1:
                break
            cost += c[p[i]][p[i+1]]
        dp[p[0]] = min(dp[p[0]], cost)
    ans = 0
    for r in range(h):
        for c in range(w):
            x = a[r][c]
            if x == -1:
                continue
            ans += dp[x]
    return ans

h, w = map(int, input().split())
c = [list(map(int, input().split())) for i in range(10)]
a = [list(map(int, input().split())) for i in range(h)]
print(solve(h, w, c, a))




### FIXED CODE ###

def solve(h, w, c, a):
    n = 10
    dp = c.copy()
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    ans = 0
    for i in range(h):
        for j in range(w):
            x = a[i][j]
            if x == -1:
                continue
            ans += dp[x][1]
    return ans

h, w = map(int, input().split())
c = [list(map(int, input().split())) for i in range(10)]
a = [list(map(int, input().split())) for i in range(h)]
print(solve(h, w, c, a))
### BUGGY CODE ###

import fractions

n = int(input())
As = list(map(int, input().split(" ")))
maxa = max(As)
largest = 1

for i in range(n):
  gcd = 0
  for idx, j in enumerate(As):
    if idx == i:
      continue
    gcd = j if gcd==0 else fractions.gcd(gcd, j)
    if gcd <= largest:
      break
  if gcd > largest:
    largest = gcd
    if largest == max:
      break

print(largest)



### FIXED CODE ###

def gcd(a, b):
  l = max(a, b)
  s = min(a, b)
  if s == 0:
    return l
  else:
    return gcd(s, l%s)

n = int(input())
A = [0] + list(map(int, input().split())) + [0]
largest = 0
L = [0 for _ in range(n+2)]
R = [0 for _ in range(n+2)]
for i in range(1, n+2):
  L[i] = gcd(A[i], L[i-1])
  R[n-i+1] = gcd(R[n-i+2], A[n-i+1])

print(max(gcd(L[i-1],R[i+1]) for i in range(1, n+1)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
h,w=map(int,input().split())
a=[]
for i in range(h):
    a.append(list(map(int,input().split())))
b=[]
for i in range(h):
    b.append(list(map(int,input().split())))
dp=[[set([]) for i in range(w)] for j in range(h)]
dp[0][0].add(a[0][0]-b[0][0])
dp[0][0].add(b[0][0]-a[0][0])
for i in range(h):
    for j in range(w):
        if i==j==0:
            continue
        if i==0:
            for k in dp[i][j-1]:
                if k<=3550:
                    dp[i][j].add(abs(k+a[i][j]-b[i][j]))
                    dp[i][j].add(abs(k+b[i][j]-a[i][j]))
        elif j==0:
            for k in dp[i-1][j]:
                if k<=3550:
                    dp[i][j].add(abs(k+a[i][j]-b[i][j]))
                    dp[i][j].add(abs(k+b[i][j]-a[i][j]))
        else:
            for k in (dp[i][j-1]|dp[i-1][j]):
                if k<=6500:
                    dp[i][j].add(abs(k+a[i][j]-b[i][j]))
                    dp[i][j].add(abs(k+b[i][j]-a[i][j]))             
#dp[h-1][w-1]
ans=10**10
for i in dp[h-1][w-1]:
    ans=min(ans,abs(i))
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
H,W=map(int,input().split())
a = [[] for _ in range(H)]
for i in range(H):
    a[i] = list(map(int, input().split()))
b = [[] for _ in range(H)]
for i in range(H):
    b[i] = list(map(int, input().split()))

for i in range(H):
    for j in range(W):
        a[i][j] =abs(a[i][j]-b[i][j])

dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0].add(a[0][0])
for i in range(1,H):
    t = a[i][0]
    tmp = set()
    for k in dp[i-1][0]:
        tmp.add(k+t)
        tmp.add(abs(k-t))
    dp[i][0] = tmp
for j in range(1,W):
    t = a[0][j]
    tmp = set()
    for k in dp[0][j-1]:
        tmp.add(k+t)
        tmp.add(abs(k-t))
    dp[0][j] = tmp
for i in range(1,H):
    for j in range(1,W):
        t = a[i][j]
        tmp = set()
        for k in (dp[i-1][j] | dp[i][j-1]):
            tmp.add(k+t)
            tmp.add(abs(k-t))
        dp[i][j] = tmp
        dp[i-1][j-1] = set()

ls = list(dp[H-1][W-1])
print(min(ls))
### BUGGY CODE ###



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

K, S = map(int, input().split())

count = 0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x+y+z == S:
                count += 1

print(count)

### FIXED CODE ###



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

K, S = map(int, input().split())

count = 0
for x in range(K+1):
    for y in range(K+1):
        z = S-x-y
        if 0 <= z <= K:
            count += 1

print(count)
### BUGGY CODE ###

import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
h, w, d = map(int, readline().split())
num = h * w
mass = np.array([[0, 0] for _ in range(num + 1)])
mp = np.zeros(num+1, dtype=int)
for i in range(h):
    for j, a in enumerate(map(int, readline().split())):
        mass[a] = [i, j]
for i in range(d+1, num+1):
    mp[i] = mp[i-d] + np.sum(abs(mass[i]-mass[i-d]))
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(mp[r]-mp[l])


### FIXED CODE ###

import sys
input = sys.stdin.readline
h, w, d = map(int, input().split())
num = h * w
x = [0] * (num + 1)
y = [0] * (num + 1)
mp = [0] * (num + 1)
for i in range(h):
    for j, a in enumerate(map(int, input().split())):
        x[a], y[a] = [i+1, j+1]
for i in range(d+1, num+1):
    mp[i] = mp[i-d] + abs(x[i] - x[i-d]) + abs(y[i] - y[i-d])
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(mp[r]-mp[l])
### BUGGY CODE ###

import numpy as np
def inpl(): return list(map(int,input().split()))

N, M , Q = inpl()
trains = np.zeros((N,N),dtype=np.int)
ans = np.zeros((N,N),dtype=np.int)

for i in range(M):
    L, R = inpl()
    trains[L-1,R-1] += 1

for l in range(N):
    for r in range(l,N):
        ans[l,r] = trains[l:r+1,l:r+1].sum()

for i in range(Q):
    p, q = inpl()
    print(ans[p-1,q-1])

### FIXED CODE ###

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

N, M, Q = inpl()
cumsum = [0]*((N+1)**2)
ans = [0]*((N+1)**2)

for i in range(M):
    L, R = inpl()
    cumsum[L*(N+1)+R] += 1

for l in range(1,N+1):
    for r in range(1,N+1):
        cumsum[l*(N+1)+r] += cumsum[(l-1)*(N+1)+r] + cumsum[l*(N+1)+r-1] - cumsum[(l-1)*(N+1)+r-1]

for l in range(1,N+1):
    for r in range(l,N+1):
        ans[l*(N+1)+r] = cumsum[r*(N+1)+r] - cumsum[(l-1)*(N+1)+r] - cumsum[r*(N+1)+l-1] + cumsum[(l-1)*(N+1)+l-1]

for i in range(Q):
    p, q = inpl()
    print(ans[p*(N+1)+q])
### BUGGY CODE ###

from sys import stdin

def execute(a, b, c):
    return b+c, a+c, a+b

a, b, c, k = [int(x) for x in stdin.readline().rstrip().split()]

for i in range(k):
    a, b, c = execute(a, b, c)

if a - b > 10e18:
    print('Unfair')
else:
    print(a-b)


### FIXED CODE ###

from sys import stdin

def execute(a, b, c):
    return b+c, a+c, a+b


a, b, c, k = [int(x) for x in stdin.readline().rstrip().split()]

"""
for i in range(k):
    a, b, c = execute(a, b, c)

if a - b > 10e18:
    print('Unfair')
else:
    print(a-b)
"""

if k % 2 == 0:
    print(a-b)
else:
    print(b-a)
### BUGGY CODE ###

from itertools import permutations

# 入力
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)]

# (i + j) % 3 = k のマスを色cに塗り替える際の違和感の和
dp = {
    k: [
        sum(
            D[c[i][j] - 1][k - 1] if (i + j) % 3 == m else
            0
            for i in range(N)
            for j in range(N)
        )
        for m in range(3)
    ]
    for k in range(1, C + 1)
}

# dpを用いて全探索し解を得る
ans = min(
    dp[i][0] + dp[j][1] + dp[k][2]
    for i, j, k in permutations(range(1, C + 1), 3)
)

# 出力
print(ans)


### FIXED CODE ###

from itertools import permutations

# 入力
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)]

# (i + j) % 3 = k のマスを色cに塗り替える際の違和感の和
dp = {
    k: [
        sum(
            D[c[i][j] - 1][k - 1] if (i + j) % 3 == m else
            0
            for i in range(N)
            for j in range(N)
        )
        for m in range(3)
    ]
    for k in range(1, C + 1)
}

# dpを用いて全探索し解を得る
ans = min(
    dp[i][0] + dp[j][1] + dp[k][2]
    for i, j, k in permutations(range(1, C + 1), 3)
)

# 出力
print(ans)
### BUGGY CODE ###

"""
keyword: 二項係数

与えられた文字列sの最後の文字以降は何を置いても(26通り)良い一方で、最後の文字より前は同じ文字は置けない(25通り)
そこで最後の文字より後と前で分けて場合の数を考える


"""

import sys
sys.setrecursionlimit(10**6)

k = int(input())
s = input()

mod = 10**9+7

n = len(s)
fact = [1, 1] # あとでnの階乗を求める初期値　[0!, 1!]

# n!を求める
for i in range(2, 2*(10**6)+1):
    fact.append(fact[-1]*i % mod)

# 二項係数nCrを求める nCr = n!/r!(n-r)!
def nCr(n, r, mod=10**9+7):
    return pow(fact[n-r]*fact[r] % mod, mod-2, mod)*fact[n] % mod # modの世界では逆元はpow(x,mod-2)をかけることと同じ

ans = 0
#for i in range(k+1):
#    ans = (ans+nCr(n+k, i)*pow(25, i, mod)) % mod
#print(ans)

for i in range(k+1):
    now = 26**(k-i)*25**i*nCr(i+n-1, n-1) % mod
    ans = (ans+now) % mod
print(ans)

### FIXED CODE ###

"""
keyword: 二項係数

与えられた文字列sの最後の文字以降は何を置いても(26通り)良い一方で、最後の文字より前は同じ文字は置けない(25通り)
そこで最後の文字より後と前で分けて場合の数を考える


"""

import sys
sys.setrecursionlimit(10**6)

k = int(input())
s = input()

mod = 10**9+7

n = len(s)
fact = [1, 1] # あとでnの階乗を求める初期値　[0!, 1!]

# n!を求める
for i in range(2, 2*(10**6)+1):
    fact.append(fact[-1]*i % mod)

# 二項係数nCrを求める nCr = n!/r!(n-r)!
def nCr(n, r, mod=10**9+7):
    return pow(fact[n-r]*fact[r] % mod, mod-2, mod)*fact[n] % mod # modの世界では逆元はpow(x,mod-2)をかけることと同じ

ans = 0
#for i in range(k+1):
#    ans = (ans+nCr(n+k, i)*pow(25, i, mod)) % mod
#print(ans)

for i in range(k+1):
    now = pow(26, k-i, mod) * pow(25, i, mod) * nCr(i+n-1, n-1)
    ans = (ans+now) % mod
print(ans)
### BUGGY CODE ###

from collections import Counter
def main():
    mod=2019
    S=input().strip()
    M=[0]
    p=1
    for s in S[::-1]:
        x=int(s)
        M.append((M[-1]+x*p)%mod)
        p*=10
    C=Counter(M)
    ans=0
    for _,m in C.items():
        ans+=m*(m-1)//2
    print(ans)
    
if __name__=='__main__':
    main()

### FIXED CODE ###

from collections import Counter
def main():
    mod=2019
    S=input().strip()
    l=len(S)
    M=[0]*(l+1)
    p=1
    for i in range(1,l+1):
        x=int(S[l-i])
        M[i]=(M[i-1]+x*p)%mod
        p*=10
        p%=mod
    C=Counter(M)
    ans=0
    for m in C.values():
        ans+=m*(m-1)//2
    print(ans)
    
if __name__=='__main__':
    main()
### BUGGY CODE ###

import bisect

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(); b.sort(); c.sort()
ans = 0
for i in range(n) :
    r_b = bisect.bisect_right(b, a[i])
    for j in range(r_b, n) :
        r_c = bisect.bisect_right(c, b[j]) 
        ans += n - r_c

print(ans)

### FIXED CODE ###

import bisect

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(); b.sort(); c.sort()
dp = [0]*(n+1)
for i in range(n-1, -1, -1) :
    ins_c = bisect.bisect_right(c, b[i])
    dp[i] = dp[i+1] + (n-ins_c)
ans = 0
for i in range(n) :
    ins_b = bisect.bisect_right(b, a[i])
    ans += dp[ins_b]

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

def solve():
    n = int(input())
    l = []

    for i in range(n):
        l.append(int(input()))

    a = 1
    hist = []
    while(True):
        if(a-1 in hist):
            return -1
        if(a-1 == 1):
            return len(hist)
        hist.append(a-1)
        a = l[a-1]

if(__name__ == "__main__"):
    print(solve())


### FIXED CODE ###

def solve():
    n = int(input())
    l = []

    for i in range(n):
        l.append(int(input()))

    a = 1
    hist = set([])
    while(True):
        if(a-1 in hist):
            return -1
        if(a-1 == 1):
            return len(hist)
        hist.add(a-1)
        a = l[a-1]

if(__name__ == "__main__"):
    print(solve())
### BUGGY CODE ###


n,m = map(int,input().split())
a = [int(input()) for i in range(m)]

dp = [0] * (n+1)
for i in range(n+1):
     if i in a:
          dp[i] = 0
     elif i == 0 or i == 1:
          dp[i] = 1
     else:
          dp[i] = (dp[i-1] + dp[i-2])%1000000007
print(dp[n])

### FIXED CODE ###

n, m = map(int, input().split())
mod = 10**9 + 7
dp = [1]*(n+1)
 
for _ in range(m):
    a = int(input())
    dp[a] = 0
 
for i in range(2, n+1):
    if dp[i]>0:
        dp[i] = (dp[i-1]+dp[i-2])%mod
 
print(dp[n])
### BUGGY CODE ###

def warshall_floyd(graph):
    num_v = len(graph)

    for k in range(num_v):
        for i in range(num_v):
            for j in range(num_v):
                if graph[i][j] > graph[i][k] + graph[k][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]
    return graph

N = int(input())
graph = [[float("inf") for _ in range(N)] for _ in range(N)]
for i in range(N):
    a_list = list(map(int, input().split()))
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = a_list[j]
# import copy
# a_list = copy.deepcopy(graph)
from scipy.sparse.csgraph import floyd_warshall
w_graph = floyd_warshall(graph, directed=False)
result = 0
for i in range(N):
     w_graph[i][i] = float("inf")
for i in range(N):
    for j in range(i):
        if i == j:
            continue
        if w_graph[i][j] != graph[i][j]:
            print(-1)
            exit()
        d = []
        for k in range(N):
            d.append(w_graph[i][k] + w_graph[j][k])
        if min(d) > w_graph[i][j]:
            result += w_graph[i][j]
print(int(result))


### FIXED CODE ###

def warshall_floyd(graph):
    num_v = len(graph)

    for k in range(num_v):
        for i in range(num_v):
            for j in range(num_v):
                if graph[i][j] > graph[i][k] + graph[k][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]
    return graph

N = int(input())
graph = [[float("inf") for _ in range(N)] for _ in range(N)]
for i in range(N):
    a_list = list(map(int, input().split()))
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = a_list[j]
import copy
a_list = copy.deepcopy(graph)
w_graph = warshall_floyd(graph)
result = 0
for i in range(N):
    for j in range(i+1, N):
        if i == j:
            continue
        if w_graph[i][j] != a_list[i][j]:
            print(-1)
            exit()
        d = []
        for k in range(N):
            d.append(w_graph[i][k] + w_graph[j][k])
        if min(d) > w_graph[i][j]:
            result += w_graph[i][j]
print(result)
### BUGGY CODE ###

from copy import deepcopy


def solve(road, num, ans, n):
    pattern = 0
    test = deepcopy(road)
    if len(ans) is int(n):
        for i in range(1, n + 1):
            if ans.count(str(i)) == 0:
                return 0
        return 1
    if len(road[num - 1]) == int(0):
        return 0
    else:
        for i in range(len(road[num - 1])):
            tmp = test[num - 1][0]
            if tmp is not 0:
                word = ans + str(tmp)
            test[num - 1].pop(0)
            pattern += solve(test, tmp, word, n)
    return pattern


N, M = [int(i) for i in input().split()]
town = []
for i in range(N):
    town.append(deepcopy([]))

for i in range(M):
    a, b = [int(i) for i in input().split()]
    town[a - 1].append(b)
    town[b - 1].append(a)
print(solve(town, 1, '1', N))


### FIXED CODE ###

from copy import deepcopy


def solve(road, num, ans, n):
    pattern = 0
    test = deepcopy(road)
    for s in test:
        if num in s:
            s.remove(num)
    if len(ans) is n:
        return 1
    if len(test[num - 1]) == int(0):
        return 0
    else:
        for i in range(len(test[num - 1])):
            tmp = test[num - 1][i]
            if tmp is not 0:
                word = ans + str(tmp)
            pattern += solve(test, tmp, word, n)
    return pattern


N, M = [int(i) for i in input().split()]
town = []
for i in range(N):
    town.append(deepcopy([]))

for i in range(M):
    a, b = [int(i) for i in input().split()]
    if a is not 1 or b is not 1:
        town[a - 1].append(b)
        town[b - 1].append(a)
print(solve(town, 1, '1', N))
### BUGGY CODE ###

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

### FIXED CODE ###

import math
n=int(input())
s=math.factorial(n)
ans=s%(10**9+7)
print(ans)
### BUGGY CODE ###

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

import itertools
comb_list = list(itertools.combinations(sorted(l_list),3))
count = 0
for i in range(len(comb_list)):
    if comb_list[i][0] + comb_list[i][1] + comb_list[i][2] > comb_list[i][2] * 2:
        count += 1
print(count)

### FIXED CODE ###

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

import bisect

L_list = sorted(L_list)
 
ans = 0
for a_index in range(0, N):
    for b_index in range(a_index+1, N):
        a = L_list[a_index]
        b = L_list[b_index]
        c_right_index = bisect.bisect_left(L_list, a+b)
        if c_right_index > b_index:
            ans += c_right_index - b_index - 1
        else:
            pass

print(ans)