Harryxun/stf_run huggingface dataset:
import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_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)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""
n=  int(sys.stdin.readline())
p=list(range(2,n))
if n ==1:
    print(0)
elif n == 2:#なぜ？
    print(1)
else:
    print(n*(n-1)//2)

### FIXED CODE ###

import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_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)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""
n=  int(sys.stdin.readline())
if n ==1:
    print(0)
elif n == 2:#なぜ？
    print(1)
else:
    print(n*(n-1)//2)
N=int(input())
p=list(map(int,input().split("\n")))
ans=sum(p)-(max(p)2)
print(int(ans))

### FIXED CODE ###

p=[]
N=int(input())
for i in range(N):
  p.append(int(input()))
ans=sum(p)-(max(p)/2)
print(int(ans))
import math
n = int(input())
ls = "abcdefghijklmnopqrstuvwxyz"
#i = 1
cnt = math.ceil(math.log(25 * n / 26 + 1, 26)) - 1
ans = ""
#print(cnt, n)
n -= 1
for i in range(cnt, -1, -1):
    if i == 0:
        res = n // (26 ** i)
    else:
        res = n // (26 ** i) - 1
    ans += ls[res]
    n -= 26 ** i * (res + 1)
print(ans)

### FIXED CODE ###

import math
n = int(input())
ls = "abcdefghijklmnopqrstuvwxyz"
cnt = 0
base = 26
while n >= base ** cnt:
    n -= base ** cnt
    cnt += 1
ans = ""
#print(cnt, n)
for i in range(cnt-1, -1, -1):
    res = n // (base ** i)
    ans += ls[res]
    n -= base ** i * res
print(ans)
# -*- coding: utf-8 -*-
def  inpl(): return list(map(int, input().split()))
N, M = inpl()
A = sorted(inpl())
cost = [1e9, 2, 5, 5, 4, 5, 6, 3, 7, 6]
mincost = min([cost[a] for a in A])
maxcost = max([cost[a] for a in A])

DP = [0]*N
for a in A:
    if N - cost[a] >= 0:
        DP[N-cost[a]] = a

ans = DP[0]
for j in range(N//2 + 1):
    DP2 = [0]*N
    ok = False
    for i in range(max(0, N-maxcost*(j+1)), N-mincost*j):
        v = DP[i]
        if v == 0:
            continue
        for a in A:
            nk = i - cost[a]
            if nk >= 0:
                ok = True
                DP2[nk] = max(DP2[nk], 10*v + a)
    ans = max(ans, DP2[0])
    DP = DP2
    if ok == False:
        break

print(ans)


### FIXED CODE ###

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

A, B = inpl()

if B%A == 0:
    print(A+B)
else:
    print(B-A)
A, B, C, D, E, F= (int(i) for i in input().split())

dens=0
for a in range(30+1):
  for b in range(30+1):
    waterA=100*a*A
    waterAB=waterA+100*b*B
    if  waterA<= F and 0 < waterAB <= F:
      for c in range(100+1):
        for d in range(100+1):
          if waterAB+c*C+d*D <= F:
            if c*C+d*D <= (a*A+b*B)*E:
              if dens < (c*C+d*D)/(waterAB+c*C+d*D):
                dens=(c*C+d*D)/(waterAB+c*C+d*D)
                max=waterAB+c*C+d*D
              
print(max,int(max*dens))

### FIXED CODE ###

a, b, c, d, e, f= (int(i) for i in input().split()) 

waterlist=[]
for i in range(0,f+100*a,100*a):
  for j in range(0,f+100*b,100*b):
    if i+j <=f:
      waterlist+=[i+j]
waterlist=list(set(waterlist))
#print(x)

sugarlist=[]
for i in range(int(f/c)+1):
  for j in range(int(f/d)+1):
    if c*i+d*j <=f:
      sugarlist+=[c*i+d*j]
sugarlist=list(set(sugarlist))
#print(y)

density=0

for i in range(len(waterlist)):
  for j in range(len(sugarlist)):
    if 0 < waterlist[i]+sugarlist[j] <= f and sugarlist[j]<=waterlist[i]/100*e:
      tmp=sugarlist[j]/(waterlist[i]+sugarlist[j])
      if density <= tmp:
        density = tmp
        ans1=waterlist[i]+sugarlist[j]
        ans2=sugarlist[j]
        
print(ans1,ans2)
n,k=[int(i)for i in input().split()]
s=str(input())
S=list(s)
S[k-1]=S[k-1].lower
A=''.join(S)
print(A)

### FIXED CODE ###

n,k = map(int, input().split())
s = input()
 
t = s[:k-1]+str.lower(s[k-1])+s[k:]
print(t)
n,m,r=map(int,input().split())
r-=n*m
if r<0:print(0);exit(0);
from math import *
print(int(factorial(n+r-1)/factorial(r)/factorial(n-1)))

### FIXED CODE ###

n,m,r=map(int,input().split())
r-=n*m
if r<0:print(0);exit(0);
from math import *
print(factorial(n+r-1)//factorial(r)//factorial(n-1))
list=[int(input()) for i in range(5)]
S=sum(list)
Z=0
for x in list:
  y = -(-x//10)*10
  Z=(y-x, Z)
  print(S-Z)

### FIXED CODE ###

X=[int(input()) for i in range(5)]
Y=[]
for x in X:
  Y.append(-(-x//10)*10-x)
print(sum(X)+sum(Y)-(max(Y)))
inputarray = input().split(' ')
N = int(inputarray[0])
A = int(inputarray[1])
B = int(inputarray[2])
blue = 'b'
red = 'r'
ballcolumn = ''
for i in range(round(N/(A+B))+1):
    ballcolumn+=blue*A
    ballcolumn+=red*B
targetstring = ballcolumn[:N]
print(targetstring.count('b'))

### FIXED CODE ###

inputarray = input().split(' ')
N = int(inputarray[0])
A = int(inputarray[1])
B = int(inputarray[2])
blue = 'b'
red = 'r'
amari = N % (A+B)
if A >= amari: 
    countnum = N // (A+B) * A +amari
else:
    countnum = N // (A+B) * A +A
print(countnum)
s = list(input())
count = 0
ans = []
for i in s:
    if i == 'A' or i =='C' or i =='G' or i =='T':
        count += 1
    else:
        ans.append(count)
        count = 0
print(max(ans))

### FIXED CODE ###

s = input()
count = 0
ans = 0
for i in s:
    if i in'AGCT':
        count += 1
    else:
        count = 0
    ans = max(ans, count)
print(ans)
class Dice(object):
    def __init__(self, top, south, east, west, north, bottom):
        self.top = top
        self.south = south
        self.east = east
        self.west = west
        self.north = north
        self.bottom = bottom
    def rollN(self):
        prevN = self.north
        prevB = self.bottom
        prevS = self.south
        self.north = self.top
        self.bottom = prevN
        self.south = prevB
        self.top = prevS
    def rollS(self):
        prevS = self.south
        prevB = self.bottom
        prevN = self.north
        self.south = top
        self.bottom = prevS
        self.north = prevB
        self.top = prevN
    def rollE(self):
        prevE = self.east
        prevB = self.bottom
        prevW = self.west
        self.east = self.top
        self.bottom = prevE
        self.west = prevB
        self.top = prevW
    def rollW(self):
        prevW = self.west
        prevB = self.bottom
        prevE = self.east
        self.west = top
        self.bottom = prevW
        self.east = prevB
        self.top = prevE

diceInit = [int(n) for n in raw_input().split][:6:]
instruction = raw_input()

diceI = Dice(diceInit[0], diceInit[1], diceInit[2], diceInit[3], diceInit[4], diceInit[5])

for item in instruction:
    if item == 'N':
        diceI.rollN()
    elif item == 'E':
        diceI.rollE()
    elif item == 'W':
        diceI.rollW()
    elif item == 'S':
        diceI.rollS()

print diceI.top

### FIXED CODE ###

class Dice(object):
    def __init__(self, top, south, east, west, north, bottom):
        self.top = top
        self.south = south
        self.east = east
        self.west = west
        self.north = north
        self.bottom = bottom
    def rollN(self):
        prevN = self.north
        prevB = self.bottom
        prevS = self.south
        self.north = self.top
        self.bottom = prevN
        self.south = prevB
        self.top = prevS
    def rollS(self):
        prevS = self.south
        prevB = self.bottom
        prevN = self.north
        self.south = self.top
        self.bottom = prevS
        self.north = prevB
        self.top = prevN
    def rollE(self):
        prevE = self.east
        prevB = self.bottom
        prevW = self.west
        self.east = self.top
        self.bottom = prevE
        self.west = prevB
        self.top = prevW
    def rollW(self):
        prevW = self.west
        prevB = self.bottom
        prevE = self.east
        self.west = self.top
        self.bottom = prevW
        self.east = prevB
        self.top = prevE

diceInit = [int(n) for n in raw_input().split()][:6:]
instruction = raw_input()

diceI = Dice(diceInit[0], diceInit[1], diceInit[2], diceInit[3], diceInit[4], diceInit[5])

for item in instruction:
    if item == 'N':
        diceI.rollN()
    elif item == 'E':
        diceI.rollE()
    elif item == 'W':
        diceI.rollW()
    elif item == 'S':
        diceI.rollS()

print diceI.top
a=sorted[int(i) for i in input().split()]
if a[1]-a[0]==a[2]-a[1]:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

a=sorted([int(i) for i in input().split()])
if a[1]-a[0]==a[2]-a[1]:
    print("YES")
else:
    print("NO")
from collections import Counter

N, M = map(int, input().split())
ab_list = []
for _ in range(M):
    a, b = map(int, input().split())
    ab_list.append([a,b])    

nodes_color = {node:0 for node in range(1, N+1)}#set([a for ab in ab_list for a in ab])}
def func(v,c):
    if nodes_color[v] == 0:
        nodes_color[v] = c
    elif nodes_color[v] == -c:
        return False
    else:
        return True
    
    for ab in ab_list:
        if v in ab:
            for a in ab:
                if a==v:
                    continue
                if not func(a, -c):
                    return False
    return True

def bipartite_graph_check():
    for i in range(1,N+1):
        if nodes_color[i] == 0:
            if not func(i,1):
#                 print("Not Bipartite graph")
                return False
    return True

if bipartite_graph_check():
    b,w = Counter(nodes_color.values()).values()
    print(int(b*w-M))
else:
    print(int(N*(N-1)/2-M))


### FIXED CODE ###

from collections import Counter
import sys
sys.setrecursionlimit(1000000)
N,M = map(int, input().split())
 
# 隣接リスト
l = [[] for i in range(N+1)] 
for i in range(M):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

nodes_color = {node:0 for node in range(1, N+1)}#set([a for ab in ab_list for a in ab])}

nibu = True
stack = [1]

nodes_color[1] = 1

while stack:
    node = stack.pop()
    for next_node in l[node]:
        if nodes_color[next_node]==0:
            stack.append(next_node)
            nodes_color[next_node] = - nodes_color[node]
        else:
            if nodes_color[next_node]==nodes_color[node]:
                nibu = False
                break
    if not nibu:
        break

if nibu:
    b,w = Counter(nodes_color.values()).values()
    print(int(b*w-M))
else:
    print(int(N*(N-1)/2-M))
N = int(input())
x, y, h = [[0]*N, [0]*N, [0]*N]
for n in range(N):
  x[n], y[n], h[n] = map(int, input().split())

def f():
  for xx in range(101):
    for yy in range(101):
      height = []
      for n in range(N):
        height.append(abs(x[n]-xx)+abs(y[n]-yy)+h[n])
      if len(set(height)) == 1:
        return [xx, yy, height[0]]
print(*f())

### FIXED CODE ###

N = int(input())
x, y, h = [[0]*N, [0]*N, [0]*N]
for n in range(N):
  x[n], y[n], h[n] = map(int, input().split())
  if h[n] > 0:
    hi = n

def g(xx, yy, height):
  for n in range(N):
    if max(height-abs(xx-x[n])-abs(yy-y[n]), 0) != h[n]:
      return False
  return True

def f():
  for xx in range(101):
    for yy in range(101):
      height = abs(xx-x[hi])+abs(yy-y[hi])+h[hi]
      if g(xx, yy, height) is True:
        return [xx, yy, height]
print(*f())
n = int(input())
xy = [list(map(int,input().split())) for _ in range(n)]

for x in range(101):
    for y in range(101):
        h = [0,10**10]
        h_memo = 0
        for i in range(n):
            if xy[i][2] == 0:
                h[1] = min(h[1],abs(xy[0]-x) + abs(xy[1]-y))
            else:
                h_memo = xy[i][2] + abs(xy[i][0]-x) + abs(xy[i][1]-y)
            #print(x,y,h[1],h_memo)
            if h[0]!=0:
                if h_memo == h[0]:
                    continue
                elif h_memo != h[0]:
                    break
                elif h[1] < h[0]:
                    break
            elif h[0]==0 and h_memo!=0:
                h[0] = h_memo
            elif h[0]==0 and h_memo==0:
                if h[1] < (abs(xy[0]-x) + abs(xy[1]-y)):
                    break
        else:               
            #print(x+1,y+1,h[0])
            if h[0]==0:
                continue
            else:
                print(x,y,h[0])
                

### FIXED CODE ###

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

for x in range(101):
    for y in range(101):
        h_memo = 0
        for i in range(n):
            if xy[i][2] != 0:
                h_memo = xy[i][2] + abs(xy[i][0]-x) + abs(xy[i][1]-y)
                break
        for i in range(n):
            if xy[i][2] != max(0,h_memo-abs(xy[i][0]-x)-abs(xy[i][1]-y)):
                break

        else:               
            #print(x+1,y+1,h[0])

            print(x,y,h_memo)
            break
import collections


n = int(input())
odd = []
even = []
for i,j in enumerate(map(int,input().split())):
    if i % 2 == 0:
        even += [j]
    else:
        odd += [j]
odd = sorted(collections.Counter(odd).items(),key=lambda x:(x[1]),reverse=True)
even = sorted(collections.Counter(even).items(),key=lambda x:(x[1]),reverse=True)

if len(odd) == 1 and len(even) == 1:
    if odd[0][0] == even[0][0]:
        print(n//2)
    else:
        print(0)
elif len(odd) == 1 or len(even) == 1:
    if len(odd) == 1:
        print((n//2 - odd[1][1]) + (n//2 - even[1][1]))
    elif len(even) == 1:
        print((n//2 - odd[1][1]) + (n//2 - even[0][1]))
else:
    if odd[0][1] + even[1][1] > odd[1][1] + even[0][1]:
        print((n//2 - odd[0][1]) + (n//2 - even[1][1]))
    else:
        print((n//2 - odd[1][1]) + (n//2 - even[0][1]))

### FIXED CODE ###

import collections

n = int(input())
odd = []
even = []
for i, j in enumerate(map(int, input().split())):
    if i % 2 == 0:
        even += [j]
    else:
        odd += [j]
odd = sorted(collections.Counter(odd).items(), reverse=True, key=lambda x: x[1])
even = sorted(collections.Counter(even).items(), reverse=True, key=lambda x: x[1])

if len(odd) == 1 and len(even) == 1 and odd[0][0] == even[0][0]:
    print(n // 2)
elif odd[0][0] == even[0][0]:
    if odd[0][1] == even[0][1]:
        for i in range(2):
            if odd[i][1] == even[i][1]:
                continue
            elif odd[i][1] > even[i][1]:
                print((n // 2 - odd[1][1]) + (n // 2 - even[0][1]))
                break
            elif odd[i][1] < even[i][1]:
                print((n // 2 - odd[0][1]) + (n // 2 - even[1][1]))
                break
        else:
            print((n // 2 - odd[0][1]) + (n // 2 - even[1][1]))
else:
    print((n // 2 - odd[0][1]) + (n // 2 - even[0][1]))
N, K = map(int, input().split())
dic = {}
ans = []
uniq = []
etc = []
def calc_ans(ans):
    x = 0
    tmp = 0
    for i in range(K):
      tmp += ans[i][0]
      x += ans[i][1]
    return tmp + (x * x)

for i in range(N):
    l = list(map(int, input().split()))
    if dic.get(l[0]):
        dic[l[0]].append(l[1])
    else:
        dic[l[0]] = [l[1]]
if N <= K:
    ans = 0
    for i in dic.keys():
        ans += sum(dic[i])
    ans += len(dic.keys()) * len(dic.keys())
    print(ans)
    exit()
for t in dic.keys():
    dic[t].sort(reverse=True)
    uniq.append((dic[t][0], t))
uniq.sort(reverse=True)
for i in range(K):
  ans.append((uniq[i][0], 1))
  for n in dic[uniq[i][1]][1:]:
      if n <= uniq[K-1][0]:
          break
      etc.append((n, 0))
etc.sort(reverse=True)
ans_res = calc_ans(ans)
for n in etc:
    ans[-1] = n
    tmp_res = calc_ans(ans)
    if ans_res > tmp_res:
        print(ans_res)
        exit()
    else:
        ans_res = tmp_res
print(ans_res)

### FIXED CODE ###

N,K = map(int,input().split())
td = [[int(i) for i in input().split()] for _ in range(N)]
td.sort(key=lambda x:x[1],reverse=True)
ans = 0
ls = set()
dl = []
for i in range(K):
    ans += td[i][1]
    if not td[i][0] in ls:
        ls.add(td[i][0])
    else:
        dl.append(td[i][1])
ans = ans + len(ls)**2
res = ans
for i in range(K,N):
    if not dl:
        break
    if td[i][0] in ls:
        continue
    ans += len(ls)*2+1
    ans += td[i][1]
    ans -= dl[-1]
    del dl[-1]
    res = max(res,ans)
    ls.add(td[i][0])
print(res)
a = input()
date = list(a)
year = int(date[0])*1000 + int(date[1])*100 + int(date[2])*10 + int(date[3])
mon = int(date[4])*10 + int(date[5])
day = int(date[6])*10 + int(date[7])
if year < 2019 and mon < 5 :
  print("Heise")
else :
  print("TBD")
 


### FIXED CODE ###

a = input()
date = list(a)
year = int(date[0])*1000 + int(date[1])*100 + int(date[2])*10 + int(date[3])
mon = int(date[5])*10 + int(date[6])
day = int(date[8])*10 + int(date[9])
if year < 2019 or mon < 5 :
  print("Heisei")
else :
  print("TBD")
count = int(input())
numlist = list(map(int, sorted(input().split())))
result = 0

"""
for i in range(count-1):
  result = (numlist[i+1] + numlist[i]) / 2
"""

  #resultの結果をもう一回listに戻してsortする必要があるかも
  
while len(numlist) >= 2:
  sum = (numlist[1] + numlist[0]) / 2
  del numlist[0:2] #0,1番目の要素を削除
  numlist.append(sum)
  numlist = sorted(numlist)
  #print(sum)
  #print(numlist)
  
print(sum)


### FIXED CODE ###

a = int(input())
s = input()
 
if a >= 3200:
  print(s)
else:
  print("red")
import numpy as np
import math


def calc(A,B,C):
    a = np.linalg.norm(B - C)
    b = np.linalg.norm(C - A)
    c = np.linalg.norm(A - B)
    cosC = np.inner(A-C, B-C)/(b*a)
    if cosC <= 0:
        return 0
    tanC = math.sqrt(1/(cosC**2)-1)
    return (1 - 1/cosC + tanC) * (a+b-c)/4


a = np.array(ai())
b = np.array(ai())
c = np.array(ai())
print(max(calc(a,b,c),calc(b,c,a),calc(c,a,b)))

### FIXED CODE ###

ai = lambda: list(map(int, input().split()))

import numpy as np
import math


def calc(A,B,C):
    a = np.linalg.norm(B - C)
    b = np.linalg.norm(C - A)
    c = np.linalg.norm(A - B)
    s = (a + b + c) / 2
    area = (s * (s - a) * (s - b) * (s - c)) ** 0.5
    r = 2 * area / (a + b + c)
    m = max(a,b,c)
    return m/(2+m/r)


a = np.array(ai())
b = np.array(ai())
c = np.array(ai())
print(calc(a,b,c))
import math

a, b, x = [int(v) for v in input().split(' ')]

l1 = x / (a * a)
l2 = b - l1

tan2 = (a / 2) / l2
rad2 = math.atan(tan2)

if l1 >= l2:
    tan = l2 / (a / 2)
    print(90 - math.degrees(math.atan(tan)))
else:
    tan1 = (a / 2) / l1
    rad1 = math.atan(tan1)
    if rad1 <= rad2:
        print(90 - math.degrees(rad2))
    else:
        tan3 = (2 * x) / (a * b * b)
        print(90-math.degrees(math.atan(tan3)))

### FIXED CODE ###

import math

a, b, x = [int(v) for v in input().split(' ')]


if a * a * b / 2.0 <= x:
    l = b - (x / (a * a))
    tan = l / (a / 2)
    print(math.degrees(math.atan(tan)))
else:
    tan = (2 * x) / (a * b * b)
    print(90-math.degrees(math.atan(tan)))
a = []
while 1:
 s = input()
 if s == 'END_OF_TEXT':
  break
 else:
  s = list(s.split(''))
  s = list(s[0].split())
  a.append(s)

print(a.count(a[0]) - 1)

### FIXED CODE ###

word = input()
counter = 0
while 1:
 s = input()
 if s == 'END_OF_TEXT':
  break
 else:
  s = list(s.lower().split())
  counter += s.count(word)
  counter += s.count(word + '.')

print(counter)
s=list(input())
x=0
y=0
while x=0:
  if s[0]!="A":
    del s[0]
  else:
    x=1
while y=0:
  if s[-1]!="Z":
    del s[-1]
  else:
    y=1
print(len(s))
    

### FIXED CODE ###

s=list(input())
x=0
y=0
for i in range(0,len(s)):
  if s[i]=="A":
    x=i
    break
for i in range(1,len(s)):
  if s[-i]=="Z":
    y=i
    break
print(len(s)-x-y+1)
import sys
sys.setrecursionlimit(10000)

n, q = map(int, input().split())
tl = [list() for _ in range(n)]
ans = [0] * n

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

def rec(p, x):
    ans[p-1] += x
    for num in tl[p-1]:
        rec(num, x)

for i in range(q):
    p, x = map(int, input().split())
    rec(p, x)

print(" ".join(map(str, ans)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
 
n, q = map(int, input().split())
tl = [list() for _ in range(n)]
xl = [0] * n
ans = [0] * n
 
for i in range(n-1):
    a, b = map(int, input().split())
    tl[a-1].append(b-1)
    tl[b-1].append(a-1)
 
for i in range(q):
    p, x = map(int, input().split())
    xl[p-1] += x

def rec(p, parent, x):
    x += xl[p]
    ans[p] = x
    for num in tl[p]:
        if num == parent: continue
        rec(num, p, x)

rec(0, -1, 0)
 
print(*ans)
n,m = [int(i) for i in input().split()]
if n <= 1:
  a = 0
else:
  a = n*(n-1)/2
if m <= 1:
  b = 0
else:
  b = m*(m-1)/2
print(ab)

### FIXED CODE ###

n,m = [int(i) for i in input().split()]
if n <= 1:
  a = 0
else:
  a = n*(n-1)/2
if m <= 1:
  b = 0
else:
  b = m*(m-1)/2
print(int(a+b))
import sys
sys.setrecursionlimit(100001)
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    n+=2
    return fibonacci_sub2(n-2, 1, 0)

def fibonacci_sub2(n, fibo_minus1, fibo_minus2):
    return fibo_minus1 if n==0 else fibonacci_sub2(n-1, fibo_minus1+fibo_minus2, fibo_minus1)


N,M = map(int, input().split()) #1 2
if M != 0:
    a = [int(input()) for i in range(M)]
else:
    if N == 1:
        print(1)
        exit()
    else:
        print(fibonacci(N)%1000000007)
        exit()
ans = []
nstep = range(N)
preidx = 0

for idx,i in enumerate(a):
    if i - preidx == 1 and idx != 0:
        print(0)
        exit()
    if idx == 0 and i-preidx-1 != 0:
        ans.append([idx,max(0,i-preidx-1)])
    elif idx > 0:
        ans.append([idx,max(0,i-preidx-2)])
    preidx = i
else:
    if preidx != N:
        ans.append([idx,max(0,N-preidx-1)])

fibsum = 1
for idx,val in enumerate(ans):
    fibsum *= max(1,fibonacci(val[1]))
    fibsum %= 1000000007 
print(fibsum) 


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000001)
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    n+=2
    return fibonacci_sub2(n-2, 1, 0)%1000000007

def fibonacci_sub2(n, fibo_minus1, fibo_minus2):
    return fibo_minus1%1000000007 if n==0 else fibonacci_sub2(n-1, (fibo_minus1+fibo_minus2)%1000000007, fibo_minus1%1000000007)%1000000007


N,M = map(int, input().split()) #1 2
if M != 0:
    a = [int(input()) for i in range(M)]
else:
    if N == 1:
        print(1)
        exit()
    else:
        print(fibonacci(N)%1000000007)
        exit()
ans = []
nstep = range(N)
preidx = 0

for idx,i in enumerate(a):
    if i - preidx == 1 and idx != 0:
        print(0)
        exit()
    if idx == 0 and i-preidx-1 != 0:
        ans.append([idx,max(0,i-preidx-1)])
    elif idx > 0:
        ans.append([idx,max(0,i-preidx-2)])
    preidx = i
else:
    if preidx != N:
        ans.append([idx,max(0,N-preidx-1)])

fibsum = 1
for idx,val in enumerate(ans):
    fibsum *= max(1,fibonacci(val[1]))
    fibsum %= 1000000007 
print(fibsum)
N,M = map(int,input().split())
A = list(map(int,input().split()))

ans = N - sum(A)
if sum(A) < N
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

ans = N - sum(A)
if sum(A) > N:
    print(-1)
else:
    print(ans)