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

from collections import deque, defaultdict
import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        p, q, c = map(int, input().split())
        adj[p].append((q, c))
        adj[q].append((p, c))

    deq = deque()
    cost = [10 ** 7] * (N+1)
    seen = [defaultdict(int) for _ in range(N+1)]
    prev = defaultdict(list)
    deq.append(1)
    cost[1] = 0
    flag = [1] * (N+1)
    while deq:
        v = deq.pop()
        flag[v] = 1
        for uc in adj[v]:
            u, c = uc
            # print(v, u, c)
            # print(deq, prev, cost)
            # print(seen[4])
            if c in prev[v] and seen[u][c] == 0:
                if cost[u] == cost[v]:
                    prev[u].append(c)
                    if flag[u]:
                        deq.append(u)
                        flag[u] = 0
                elif cost[u] > cost[v]:
                    cost[u] = cost[v]
                    deq.append(u)
                    prev[u] = [c]
                seen[v][c] = 1
            else:
                if cost[u] > cost[v] + 1:
                    cost[u] = cost[v] + 1
                    deq.appendleft(u)
                    prev[u] = [c]
                elif cost[u] == cost[v] + 1:
                    prev[u].append(c)

    print(cost[N]) if cost[N] < 10 ** 7 else print(-1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    N, M = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    c2v = {}
    v = N+1
    for _ in range(M):
        p, q, c = map(int, input().split())
        P = p*(10**7) + c
        Q = q*(10**7) + c
        if P not in c2v:
            c2v[P] = v
            adj[p].append((v, 1))
            adj.append([(p, 1)])
            v += 1
        if Q not in c2v:
            c2v[Q] = v
            adj[q].append((v, 1))
            adj.append([(q, 1)])
            v += 1
        adj[c2v[P]].append((c2v[Q], 0))
        adj[c2v[Q]].append((c2v[P], 0))

    que = deque()
    que.append(1)
    seen = [-1] * len(adj)
    seen[1] = 0
    while que:
        v = que.popleft()
        for u, cost in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + cost
                if cost:
                    que.append(u)
                else:
                    que.appendleft(u)
    print(seen[N] // 2)


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

import math

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

c = a/b
p = []

for x in range(n + 1):
    d = math.floor(c * x) - a * math.floor(x / b)
    p.append(d)
    p.sort()
    if len(p) == 2:
        del p[0]


print(p[0])


### FIXED CODE ###

import sys
input = sys.stdin.readline

import math

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

    if b > n:
        print(math.floor(a*n/b))

    else:
        print(math.floor(a*(b-1)/b) - a*math.floor((b-1)/b))

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

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
 
n, q = map(int, input().split())
g = [list() for i in range(n)]
node = [0] * n
 
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    g[a].append(b)
    g[b].append(a)
 
for i in range(q):
    p, x = map(int, input().split())
    node[p-1] += x
 
def dfs(v, p=-1):
    for u in g[v]:
        if u == p: continue
        node[u] += node[v]
        dfs(u, v)
 
dfs(0)
print(*node)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

n, q = map(int, input().split())
g = [list() for i in range(n)]
node = [0] * n

for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    g[a].append(b)
    g[b].append(a)

for i in range(q):
    p, x = map(int, input().split())
    node[p-1] += x

def dfs(v, p=-1):
    for u in g[v]:
        if u == p: continue
        node[u] += node[v]
        dfs(u, v)

dfs(0)
print(*node)
### BUGGY CODE ###

import itertools as it 
 
n = input()
l = list(map(int, input().split()))
 
l.sort()
 
triangles = set()
for a, b, c in it.combinations(l, 3):
    if a + b > c and b + c > a and a + c > b:
        triangles.add((a, b, c))
 
print(len(triangles))

### FIXED CODE ###

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

l.sort()
count = 0
  
for i in range(0,n-2): 

    k = i + 2

    for j in range(i+1,n): 

        while (k < n and l[i] + l[j] > l[k]): 
            k += 1

        if(k>j): 
            count += k - j - 1

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

from collections import defaultdict
N = int(input())

counts = [0,0,0,0]
for a in map(int,input().split()):
  counts[a] += 1

dp = defaultdict(float)
dp[tuple(counts)] = 1
res = 1
increment = 1

while increment > 10**-10:
  ndp = defaultdict(float)
  for (a,b,c,d),p in dp.items():
    ndp[(a,b,c,d)] += p*a/N
    if b > 0:
      ndp[(a+1,b-1,c,d)] += p*b/N
    if c > 0:
      ndp[(a,b+1,c-1,d)] += p*c/N
    if d > 0:
      ndp[(a,b,c+1,d-1)] += p*d/N
  dp = ndp
  increment = 1-dp[(N,0,0,0)]
  res += increment

print(res)


### FIXED CODE ###

from collections import defaultdict
import sys
from functools import lru_cache
sys.setrecursionlimit(100000)
N = int(input())
 
counts = [0,0,0]
for a in map(int,input().split()):
  counts[a-1] += 1

A,B,C = counts


# dp[i][j][k] = 残り1個の皿がi枚、残り2個の皿がj枚、残り3個の皿がk枚のときの回数の期待値
# dp[i][j][k] = (i/N)(dp[i-1][j][k])+(j/N)(dp[i+1][j-1][k])+(k/N)(dp[i][j+1][k-1])+(N-i-j-k/N)(dp[i][j][k])+1
# dp[i][j][k] = (i(dp[i-1][j][k])+j(dp[i+1][j-1][k])+k(dp[i][j+1][k-1])+N)/(i+j+k)
dp = [[[None]*(C+1) for _ in range(B+C+1)] for _ in range(A+B+C+1)]
dp[0][0][0] = 0

for k in range(C+1):
  for j in range(B+C+1-k):
    for i in range(A+B+C+1-k-j):
      try:
        dp[i][j][k] =((i*dp[i-1][j][k] if i else 0)+
                      (j*dp[i+1][j-1][k] if j else 0)+
                      (k*dp[i][j+1][k-1] if k else 0)+
                      N)/(i+j+k)
      except ZeroDivisionError:
        pass

print(dp[A][B][C])
### BUGGY CODE ###

def main(S, T):
    S = list(S)
    T = list(T)
    if S == T:
        return "Yes"
    l = len(S)
    for i in range(l):
        s = S[i]
        t = T[i]
        if s != t:
            for j in range(l):
                if S[j] == s:
                    S[j] = t
                elif S[j] == t:
                    S[j] = s
            #print("%s -> %s"%(s, t), "".join(S))
    return "Yes" if S == T else "No"

assert main("chokudai", "redcoder") == "No"
assert main("azzel", "apple") == "Yes"
assert main("abcdefghijklmnopqrstuvwxyz", "ibyhqfrekavclxjstdwgpzmonu") == "Yes"
S = input()
T = input()
print(main(S, T))


### FIXED CODE ###

import sys
import collections

def main(S, T):
    print(S, file=sys.stderr)
    print(T, file=sys.stderr)

    m = dict()
    for s, t in zip(S, T):
        if s in m and m[s] != t:
            return "No"
        m[s] = t
    print("  ".join(m), file=sys.stderr)
    print("  ".join(m.values()), file=sys.stderr)
    c = set()
    for t in m.values():
        if t in c:
            return "No"
        c.add(t)
    return "Yes" 

assert main("chokudai", "redcoder") == "No"
assert main("azzel", "apple") == "Yes"
assert main("abcdefghijklmnopqrstuvwxyz", "ibyhqfrekavclxjstdwgpzmonu") == "Yes"
S = input()
T = input()
print(main(S, T))
### BUGGY CODE ###

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

count = 0
for i in range(N):
    for j in range(i+1,N):
        if abs(i-j) == As[i] + As[j]:
            count += 1

print(count)


### FIXED CODE ###

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

i_plus_Ai = [0 for i in range(N)]
dict = {}
for i in range(N):
    i_plus_Ai[i] = i + As[i]
    tmp = i - As[i]
    if tmp not in dict:
        dict[tmp] = [i]
    else:
        dict[tmp].append(i)

count = 0
for i in range(N):
    if i_plus_Ai[i] in dict:
        kouho = dict[i_plus_Ai[i]]
        for j in range(len(kouho)):
            if kouho[j] > i:
                count += len(kouho) - j
                break

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

h,w = map(int,input().split())
A = []
for _ in range(h):
    a = list(map(int,input().split()))
    A.append(a)
B = []
for _ in range(h):
    b = list(map(int,input().split()))
    B.append(b)
g = [[0]*(w+1) for _ in range(h+1)]
m = 0
for i in range(1,h+1):
    for j in range(1,w+1):
        g[i][j] = abs(A[i-1][j-1]-B[i-1][j-1])
m  = 80*(h+w-1)//2
dp = [[[False for _ in range(m+1)] for _ in range(w+1)] for _ in range(h+1)]
dp[1][1][g[1][1]] = True

for i in range(1,h+1):
    for j in range(1,w+1):
        for k in range(m+1):
            if k + g[i][j]<m:
                dp[i][j][k] = dp[i][j][k] or dp[i-1][j][abs(k-g[i][j])] or dp[i-1][j][k+g[i][j]] or dp[i][j-1][abs(k-g[i][j])] or dp[i][j-1][k+g[i][j]]
            else:
                dp[i][j][k] = dp[i][j][k] or dp[i-1][j][abs(k-g[i][j])] or dp[i][j-1][abs(k-g[i][j])]
            

for k in range(m+1):
    if dp[-1][-1][k]:
        print(k);exit()



### FIXED CODE ###

H, W = map(int, input().split())
A = [None]*H
for i in range(H):
    A[i] = list(map(int, input().split()))
B = [None]*H
for i in range(H):
    B[i] = list(map(int, input().split()))

C = [[None]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        C[i][j] = abs(A[i][j]-B[i][j])

K = 80*(H+W-1)//2 + 1
dp = [[[0]*(K+1) for _ in range(W)] for _ in range(H)]# 答えから80*(H+W-1)を引く
dp[0][0][C[0][0]] = 1

for i in range(H):
    for j in range(W):
        for k in range(K+1):
            if i and dp[i-1][j][k]:
                if k+C[i][j] < K:
                    dp[i][j][k+C[i][j]] = 1
                dp[i][j][abs(k-C[i][j])] = 1
            if j and dp[i][j-1][k]:
                if k+C[i][j] < K:
                    dp[i][j][k+C[i][j]] = 1
                dp[i][j][abs(k-C[i][j])] = 1

for k in range(K+1):
    res = dp[H-1][W-1][k]
    if res:
        print(k)
        break
### BUGGY CODE ###

s = int(input())

t = [False] * 1000000

while True:
  if s > 1000000:
    continue
  if t[s] == True:
    break
  if s % 2 == 0:
    s = s // 2
  else:
    s = 3 * s + 1

print(s)

### FIXED CODE ###

s = int(input())
 
t = [False] * 1000001
i = 1
while True:
  if s <= 1000000 and t[s] == True:
    break
  t[s] = True
  i += 1
  if s % 2 == 0:
    s = s // 2
  else:
    s = 3 * s + 1
 
print(i)
### BUGGY CODE ###

N, Ma, Mb = map(int, input().split())
D = []
atotal, btotal = 0, 0
for i in range(N):
    a, b, c = map(int, input().split())
    D.append((a, b, c))
    atotal += a
    btotal += b

Inf = 10**4
DP = [[[Inf for b in range(btotal+1)] for a in range(atotal+1)] for i in range(N+1)]
DP[0][0][0] = 0
for i in range(N):
    for a in range(atotal+1):
        for b in range(btotal+1):
            if D[i][0] + a <= atotal and D[i][1] + b <= btotal:
                DP[i+1][a + D[i][0]][b + D[i][1]] = min(DP[i+1][a + D[i][0]][b+D[i][1]], \
                    DP[i][a][b] + D[i][2])
                DP[i+1][a][b] = min(DP[i+1][a][b], DP[i][a][b])

ans = Inf
for a in range(1, atotal+1):
    for b in range(1, btotal+1):
        if a*Mb == b*Ma:
            ans = min(ans, DP[N][a][b])

print(ans if ans < Inf else -1)

### FIXED CODE ###

N, Ma, Mb = map(int, input().split())
D = []
atotal, btotal = 0, 0
for i in range(N):
    a, b, c = map(int, input().split())
    D.append((a, b, c))
    atotal += a
    btotal += b
Inf = 10**4

def DP(i, a, b, memo = {}):
    if i == 0 and a == b == 0:
        return 0
    elif i == 0:
        return Inf
    try:
        return memo[(i, a, b)]
    except KeyError:
        if a - D[i-1][0] >= 0 and b - D[i-1][1] >= 0:
            ret = min(DP(i-1, a, b, memo), DP(i-1, a-D[i-1][0], b-D[i-1][1], memo) + D[i-1][2])
        else:
            ret = DP(i-1, a, b, memo)
        memo[(i, a, b)] = ret
        return ret

memo = {}
ans = Inf
for a in range(1, atotal+1):
    for b in range(1, btotal+1):
        if a*Mb == b*Ma:
            ans = min(ans, DP(N, a, b, memo))

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

# -*- coding: utf-8 -*-
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

N = int(input())
An = list(map(int, input().split()))
Bn = list(map(int, input().split()))
Cn = list(map(int, input().split()))

An.sort()
Bn.sort()
Cn.sort()
#
# print(An)
# print(Bn)
# print(Cn)
#B
B_cnt = []
j = 0
for i in range(N):
    while j < N:
        if Bn[i] < Cn[j]:
            B_cnt.append(N - j)
            break
        else:
            j += 1
# print(B_cnt)

A_cnt = 0
j = 0
for i in range(N):
    while j < N:
        if An[i] < Bn[j]:
            for cnt in B_cnt[j:]:
                A_cnt += cnt
            break
        else:
            j += 1

print(A_cnt)



### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

N = int(input())
An = list(map(int, input().split()))
Bn = list(map(int, input().split()))
Cn = list(map(int, input().split()))

An.sort()
Bn.sort()
Cn.sort()

# print(An)
# print(Bn)
# print(Cn)

# B
C_cnt = []
C_sum = 0
j = 0
for i in range(N):
    while j < N:
        if Bn[i] < Cn[j]:
            C_cnt.append(N - j)
            C_sum += N - j
            break
        else:
            j += 1


B_cnt = []
temp_sum = 0
for cnt in C_cnt:
    B_cnt.append(C_sum - temp_sum)
    temp_sum += cnt

A_cnt = 0
j = 0
for i in range(N):
    while j < N:
        if An[i] < Bn[j]:
            if j < len(B_cnt):
                A_cnt += B_cnt[j]
            break
        else:
            j += 1

# print(C_cnt)
# print(B_cnt)
print(A_cnt)
### BUGGY CODE ###

def main():
    n = int(input())
    s = input()
    x = set()

    table = [[0 for _ in range(10)] for _ in range(10)]

    for i in range(n)[:-2]:
        for j in range(n)[i + 1:-1]:
            s_i, s_j = int(s[i]), int(s[j])
            if table[s_i][s_j] == 10:
                continue
            for k in range(n)[j + 1:]:
                item = s[i] + s[j] + s[k]
                if item not in x:
                    x.add(item)
                    table[s_i][s_j] += 1

    print(len(x))


if __name__ == '__main__':
    main()


### FIXED CODE ###

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

    c = 0
    l1 = set()
    for i in range(n)[:-2]:
        if s[i] in l1:
            continue
        l1.add(s[i])
        l2 = set()
        for j in range(n)[i + 1:-1]:
            if s[j] in l2:
                continue
            l2.add(s[j])
            c += len(set(list(s[j + 1:])))

    print(c)


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

k = int(input())
import math
def gcd(a,b,c):
  return (math.gcd(a, math.gcd(b, c)))
tsum=0
for a in range (1,k+1):
  for b in range (1,k+1):
    for c in range (1,k+1):
      tsum+= gcd(a,b,c)
print(tsum)

### FIXED CODE ###

k = int(input())
from math import gcd
tsum=0
for a in range (1,k+1):
  for b in range (1,k+1):
    for c in range (1,k+1):
      tsum+= gcd(a,gcd(b,c))
print(tsum)
### BUGGY CODE ###

#!/usr/bin/env python

n=int(raw_input().strip())

power=1
for i in range(1,n+1):
    power=power*i

print power%(10**9+7)

### FIXED CODE ###

N = input()
ans = 1
for i in range(1, N + 1):
	ans = (ans * i) % (1e9 + 7)
print int(ans)
### BUGGY CODE ###

H,W = map(int,raw_input().split())

while True:
    if H == 0 and W == 0:
        break
    for i in range(0,H/2):
        print ("#."* (W/2) + "#"* (W%2))
        print (".#"* (W/2) + "."* (W%2))
    if H%2 == 1:
        print ("#."* (W/2) + "#"* (W%2))
    print""


         

### FIXED CODE ###

while True:
    H,W = map(int,raw_input().split())
    if H == 0 and W == 0:
        break
    for i in range(0,H/2):
        print ("#."* (W/2) + "#"* (W%2))
        print (".#"* (W/2) + "."* (W%2))
    if H%2 == 1:
        print ("#."* (W/2) + "#"* (W%2))
    print""
### BUGGY CODE ###

h, n = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]
inf = 1 << 30
dp = [inf] * (h + 1)
dp[h] = 0

for i in range(n):
    for j in range(h, 0, -1):
        nx = max(0, j - ab[i][0])
        dp[nx] = min(dp[nx], dp[j] + ab[i][1])
print(dp[0])


### FIXED CODE ###

h, n = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]
inf = 1 << 30
dp = [inf] * (h + 1)
dp[h] = 0

for i in range(n):
    for j in range(h, 0, -1):
        nx = max(0, j - ab[i][0])
        dp[nx] = min(dp[nx], dp[j] + ab[i][1])
print(dp[0])
### BUGGY CODE ###

N=int(input())
l=list(map(int,input().split()))
max_n=max(l)
min_n=min(l)
res=float('inf')
for j in range(max_n-min_n+N+1):
  ans=0
  for i in range(N):
    ans+=abs(max_n+i-l[i]-j)
  if res > ans:
    res = ans
print(res)

### FIXED CODE ###

N=int(input())
l=list(map(int,input().split()))
for i in range(N):
  l[i] -= i
l.sort()
center_num=l[N//2]
ans=0
for i in range(N):
  ans+=abs(l[i]-center_num)
print(ans)
### BUGGY CODE ###

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


n, u, v = map(int, input().split())

GRAPH = {i:[] for i in range(1, n + 1)}
for _ in range(n - 1):
    a, b = map(int, input().split())
    GRAPH[a].append(b)
    GRAPH[b].append(a)

def dfs(now, prev = 0):
    PARENT[now] = prev
    DEPTH[now] = DEPTH[prev] + 1
    if len(GRAPH[now]) == 1:
        LEAVES.append((DEPTH[now], now))
    
    for w in GRAPH[now]:
        if w == prev:
            continue
        next = w
        dfs(next, now)

PARENT = {}
DEPTH = {0:-1}
LEAVES = []
dfs(v)

PATH = []
now = u
while True:
    PATH.append(now)
    if now == v:
        break
    now = PARENT[now]

LEAVES.sort(reverse = True)
for leaf in LEAVES:
    now = leaf[1]
    while True:
        if now in PATH:
            break
        now = PARENT[now]
    lca = now
    
    du, dv = DEPTH[u] - DEPTH[lca], DEPTH[lca]
    if du < dv:
        print(leaf[0] - 1)
        exit()


### FIXED CODE ###

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


n, u, v = map(int, input().split())

GRAPH = {i:[] for i in range(1, n + 1)}
for _ in range(n - 1):
    a, b = map(int, input().split())
    GRAPH[a].append(b)
    GRAPH[b].append(a)

def dfs(now, prev = 0):
    PARENT[now] = prev
    DEPTH[now] = DEPTH[prev] + 1
    if len(GRAPH[now]) == 1:
        LEAVES.append((DEPTH[now], now))
    
    for w in GRAPH[now]:
        if w == prev:
            continue
        next = w
        dfs(next, now)

PARENT = {}
DEPTH = {0:-1}
LEAVES = []
dfs(v)

PATH = {i:False for i in range(1, n + 1)}
now = u
while True:
    PATH[now] = True
    if now == v:
        break
    now = PARENT[now]

LEAVES.sort(reverse = True)
for leaf in LEAVES:
    now = leaf[1]
    while True:
        if PATH[now]:
            break
        now = PARENT[now]
    lca = now
    
    du, dv = DEPTH[u] - DEPTH[lca], DEPTH[lca]
    if du < dv:
        print(leaf[0] - 1)
        exit()
### BUGGY CODE ###

from itertools import accumulate as acc
from bisect import bisect_left as bl

def ans(n):
    tmp=0
    for i in range(N):
        tmp+=abs(a[i]-a[n-1])
    return tmp


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

ans=10**18
p=0
q=2
for j in range(1,N-2):
    q=min(q,j+1)
    while p<j-1 and abs(a[j]-a[p]*2)>abs(a[j]-a[p+1]*2):
        p+=1
    while q<N-2 and abs(a[j]+a[N-1]-a[q]*2)>abs(a[j]+a[N-1]-a[q+1]*2):
        q+=1

    P,Q,R,S=a[p], a[j]-a[p], a[q]-a[j], a[N-1]-a[q]
    ans=min(ans, max(P,Q,R,S)-min(P,Q,R,S))

print(ans)

### FIXED CODE ###

from itertools import accumulate as acc
from bisect import bisect_left as bl

def ans(n):
    tmp=0
    for i in range(N):
        tmp+=abs(a[i]-a[n-1])
    return tmp


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

ans=10**18
for j in range(1,N-2):
    x=a[j]/2
    p=bl(a,x)
    if p==j: p-=1
    elif p>0 and x-a[p-1]<a[p]-x: p-=1

    y=(a[j]+a[N-1])/2

    q=bl(a,y)
    if q==N-1: q-=1
    elif q>j+1 and y-a[q-1]<a[q]-y: q-=1

    P,Q,R,S=a[p], a[j]-a[p], a[q]-a[j], a[N-1]-a[q]
    ans=min(ans, max(P,Q,R,S)-min(P,Q,R,S))

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

#S = input()
reverse_S = input()[::-1]
n = len(reverse_S)
count = 0
mod = 0
mods = [0] * 2019
mods[0] = 1
x = 1
for s in reverse_S:
    mod = (mod + (int(s) * x)) % 2019
    mods[mod] = mods[mod] + 1
    x = x * 10

for v in mods:
    count = count + v*(v-1)//2

print(count)


### FIXED CODE ###

reverse_S = input()[::-1]
n = len(reverse_S)
count = 0
mod = 0
mods = [0] * 2019
mods[0] = 1
x = 1
for s in reverse_S:
    mod = (mod + (int(s) * x)) % 2019
    mods[mod] = mods[mod] + 1
    x = x * 10
    x = x % 2019

for v in mods:
    count = count + v*(v-1)//2

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

def main():
    import sys
    sys.setrecursionlimit(1000000)

    N = int(input())
    A = [[]]
    for _ in range(N):
        A.append([0]+list(map(int,input().split())))

    #AR[i][j] => iにとって選手jとの試合が何番目か
    AR = [[]]
    for i in range(1,N+1):
        AR.append([0]*(N+1))
        for j in range(1,N):
            b = A[i][j]
            AR[i][b] = j

    edges = {}
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            edges[(i,j)] = []
            jForI = AR[i][j]
            if jForI < N-1:
                nxForI = A[i][jForI+1]
                edges[(i,j)].append((min(i,nxForI),max(i,nxForI)))
            iForJ = AR[j][i]
            if iForJ < N-1:
                nxForJ = A[j][iForJ+1]
                edges[(i,j)].append((min(j,nxForJ),max(j,nxForJ)))

    steps = {}
    def dfs(i,j):
        #iとjの試合を1日目とし、試合終了まで何日かかるかを返す。
        if (i,j) not in steps:
            steps[(i,j)] = 0
            res = 1
            for a,b in edges[(i,j)]:
                res = max(res,dfs(a,b)+1)
            steps[(i,j)] = res
        elif steps[(i,j)] == 0:
            print(-1)
            exit()
        return steps[(i,j)]

    ans = 0
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            ans = max(ans,dfs(i,j))
    print(ans)
main()

### FIXED CODE ###

"""
最長経路問題として解く。

各試合のノードを作成。
各試合ノードごとに、「この試合が終わったら、次はこの試合ができるようになる。」という対応関係を作っていく。
"""
def main():
    import sys
    sys.setrecursionlimit(1000000)
    input = sys.stdin.readline

    N = int(input())

    A = [[0]*(N)]
    for i in range(N):
        A.append([0]+list(map(int,input().split())))
    
    #選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
    reverseMemo = [[-1]*(N+1) for _ in range(N+1)]
    for i in range(1,N+1):
        for j in range(1,N):
            a = A[i][j]
            reverseMemo[i][a] = j
    edges = {}
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            match = (i,j)
            edges[match] = []
            if reverseMemo[i][j] != N-1:
                nx = A[i][reverseMemo[i][j]+1]
                edges[match].append((min(i,nx),max(i,nx)))
            if reverseMemo[j][i] != N-1:
                nx = A[j][reverseMemo[j][i]+1]
                edges[match].append((min(j,nx),max(j,nx)))
    
    del reverseMemo
    del A
    
    stepMemo = {}
    def dfs(i,j,path):
        #i,jの試合日を含めて、あと何日必要なのかを返す。
        if (i,j) not in stepMemo:
            if (i,j) in path:
                print(-1)
                exit()
            else:
                path.add((i,j))
            res = 1
            for a,b in edges[(i,j)]:
                res = max(res,dfs(a,b,path)+1)
            stepMemo[(i,j)] = res
        return stepMemo[(i,j)]

    ans = 0
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            if (i,j) not in stepMemo:
                ans = max(ans,dfs(i,j,set()))
    print(ans)
main()
### BUGGY CODE ###

n, a, b = map(int, input().split())
mod = pow(10, 9) + 7
ans = 0
u, d = 1, 1

for i in range(1, n+1):
    u *= (n+1-i)
    d *= i
    if i not in (a, b):
        ans += u//d
        ans %= mod

print(ans)

### FIXED CODE ###

def cmb(n, r, p):
    r = min(r, n - r)
    upper = 1
    for i in range(n, n - r, -1):
        upper = (upper * i) % p

    lower = 1
    for i in range(1, r + 1):
        lower = (lower * i) % p

    # フェルマーの小定理よりp素数ならupper**(p-2)は逆元
    return (upper * pow(lower, p - 2, p)) % p

mod = pow(10, 9) + 7
n, a, b = map(int, input().split())
ans = (pow(2, n, mod) - 1 - cmb(n, a, mod) - cmb(n, b, mod))%mod
print(ans)