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

# No DP No LIFE
# 配るDP, 要復習
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    H, N = MAP()
    L = [LIST() for i in range(N)]
    A = []
    B = []
    for i in range(N):
        A.append(L[i][0])
        B.append(L[i][1])

    dp = [INF] * 20010
    dp[0] = 0
    for i in range(10010):
        for j in range(N):
            dp[i+A[j]] = min(dp[i+A[j]], dp[i]+B[j])
    ans = INF
    for i in range(H, 20010):
        ans = min(ans, dp[i])
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

# No DP No LIFE
# 配るDP, 要復習
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    H, N = MAP()
    L = [LIST() for i in range(N)]
    A = []
    B = []
    for i in range(N):
        A.append(L[i][0])
        B.append(L[i][1])

    dp = [INF] * 20010
    dp[0] = 0
    for i in range(10010):
        for j in range(N):
            dp[i+A[j]] = min(dp[i+A[j]], dp[i]+B[j])
    ans = INF
    for i in range(H, 20010):
        ans = min(ans, dp[i])
    print(ans)

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

S = input()
n = len(S)
a = [0]*(n+1)
l = [0]*2019

a[0] = int(S)
l[a[0]%2019] += 1

for i in range(n):
    a[i+1] = a[i] - int(S[i]+'0'*(n-i-1))
    l[a[i+1]%2019] += 1

print(sum(map(lambda x: x*(x-1)//2, l)))


### FIXED CODE ###

import sys

input = sys.stdin.readline

S = input().rstrip()
n = len(S)
l = [0]*2019
d = 10

t = int(S[n-1])
l[t%2019] += 1

l[0] += 1

for i in range(n-2, -1, -1):
    t += int(S[i])*d%2019
    l[t%2019] += 1 
    d *= 10
    d %= 2019

ans = 0

for i in l:
    ans += i*(i-1)//2

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

a=int(input())
b=list(map(int,input().split()))
c={}
for i in set(b):
    c[i]=b.count(i)


for i in range(a):
    if i+1 in b:
        print(c[i+1])
    else:
        print(0)

### FIXED CODE ###

a=int(input())
b=list(map(int,input().split()))
c={}
for i in range(len(b)):
    try:
        c[b[i]]+=1
    except KeyError:
        c[b[i]]=1

    
for i in range(a):
    try:
        print(c[i+1])
    except KeyError:
        print(0)
### BUGGY CODE ###

#coding: UTF-8
import math
N = int(input())
#print(N)



for i in range(1,N+1):
  if i <=5:
    print(0)
    continue
  cnt = 0
  m = int(math.sqrt(i))
  #平方根までやればよい
  for x in range(1,m):
    if i - x**2 <= 4:
      continue
    for y in range(x,m):
      if i - x**2 -y**2 <= 3:
        continue
      for z in range(y,m):
        a = (x+y+z)**2 -x*y -y*z - z*x
        if a == i:
          if x==y==z:
            cnt += 1
          elif x==y or y==z:
            cnt += 3
          else:
            cnt += 6
  print(cnt)

### FIXED CODE ###

#coding: UTF-8
import math
N = int(input())
#print(N)

ans = [0]*10001

for x in range(1,101):
  for y in range(1,101):
    for z in range(1,101):
      a = x**2+y**2+z**2+x*y+y*z+z*x
      if a <=10000:
        ans[a] += 1
    
for i in range(1,N+1):
  print(ans[i])
### BUGGY CODE ###

N = int(input())
S = input()
S += S[0:2]

for ans in ['SS','SW','WS','WW']:
    for i in range(1,N+1):
        if (ans[-1] == 'S' and S[i] == 'o') or (ans[-1] == 'W' and S[i] == 'x'):
            ans += ans[-2]
        else:
            ans += ('S' if ans[-2] == 'W' else 'W')
    if ans[:2] == ans[N:]:
        print(ans[:N])
        exit()
print(-1)


### FIXED CODE ###

N = int(input())
S = input()
S += S[0:2]

for ans in ['SS','SW','WS','WW']:
    for i in range(1,N+1):
        if (ans[-1] == 'S' and S[i] == 'o') or (ans[-1] == 'W' and S[i] == 'x'):
            ans += ans[-2]
        else:
            ans += ('S' if ans[-2] == 'W' else 'W')
    if ans[:2] == ans[N:]:
        print(ans[:N])
        exit()
print(-1)
### BUGGY CODE ###

import numpy as np

def solve(N, M, Q, L, R, p, q):
    A = np.zeros((N+2, N+2), dtype=int)
    S = np.zeros((N+2, N+2), dtype=int)
    for i in range(M):
        A[L[i], R[i]] += 1
    S[0,0] = A[0,0]
    for i in range(1, N+1):
        for j in range(1, N+1):
            S[i,:] = S[i-1,:] + A[i,:]
    res = []
    D = {}
    for i in range(Q):
        x1, x2 = p[i], q[i]
        if not (x1, x2) in D:
            a = sum(S[p[i]-1,p[i]:q[i]+1])
            b = sum(S[q[i],p[i]:q[i]+1])
            D[x1, x2] = b - a
        res.append(D[x1, x2])
    return "\n".join(map(str, res))

N, M, Q = map(int, input().split())
L, R = [0]*M, [0]*M
for i in range(M):
    L[i], R[i] = map(int, input().split())
p, q = [0]*Q, [0]*Q
for i in range(Q):
    p[i], q[i] = map(int, input().split())
print(solve(N, M, Q, L, R, p, q))

### FIXED CODE ###

import numpy as np

def solve(N, M, Q, L, R, p, q):
    A = np.zeros((N+1, N+1), dtype=int)
    for i in range(M):
        A[L[i], R[i]] += 1
    S = np.zeros((N+1, N+1), dtype=int)
    S[0,0] = A[0,0]
    for i in range(1, N+1):
        S[i,:] = S[i-1,:] + A[i,:]
    for j in range(1, N+1):
        S[:,j] += S[:,j-1]
    res = []
    for i in range(Q):
        x1, x2 = p[i]-1, q[i]
        a = S[x2,x2]
        b = S[x1,x2]
        c = S[x2,x1]
        d = S[x1,x1]
        res.append(a - b - c + d)
    return "\n".join(map(str, res))

N, M, Q = map(int, input().split())
L, R = [0]*M, [0]*M
for i in range(M):
    L[i], R[i] = map(int, input().split())
p, q = [0]*Q, [0]*Q
for i in range(Q):
    p[i], q[i] = map(int, input().split())
print(solve(N, M, Q, L, R, p, q))
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    a[i] -= 1
mod = -1
num = [0]
prev = 0
cnt = 0
# num.append(0)
while True:
    # print(num, cnt)
    if not a[prev] in num:
        num.append(a[prev])
        prev = a[prev]
    else:
        lpst = a[prev] 
        mod = cnt - num.index(a[prev]) + 1
        break
    cnt += 1

# print(mod, lpst)
now = 0
while k > 0:
    if now == lpst:
        k %= mod
    if k == 0:
        break
    now = a[now]
    k -= 1
    # print(now, k)


print(now+1)

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    a[i] -= 1
used = set()
num = [0]*n
used.add(0)
now = 0
cnt = 0
while True:
    cnt += 1
    if not a[now] in used:
        used.add(a[now])
        num[a[now]] = cnt
        now = a[now]
    else:
        lps = a[now]
        mod = cnt - num[a[now]]
        # k %= mod
        break
now = 0
# print(mod, lps, k, num)
while k:
    if now == lps:
        k %= mod
    if k == 0:
        break
    now = a[now]
    k -= 1

print(now+1)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc059/tasks/arc072_a
# C - Sequence
import copy
N = int(input().split()[0])
a_list = list(map(int, input().split()))

c = 0
w_list = copy.copy(a_list)

c_list = []

for mode in [0, 1]:
    s_list = []
    w_list = copy.copy(a_list)
    c = 0
    for i in range(N):
        s = sum(w_list[:i+1])

        if i % 2 == mode and s < 0:
            w_list[i] += abs(s)
            c += abs(s)
        elif i % 2 != mode and s >= 0:
            w_list[i] -= abs(s+1)
            c += abs(s+1)

        s = sum(w_list[:i+1])

        if s == 0:
            a = w_list[i]
            w_list[i] = a + 1 if a >= 0 else a - 1
            c += 1

        s = sum(w_list[:i+1])
        s_list.append(s)

    c_list.append(c)

ans = min(c_list)
print(ans)


### FIXED CODE ###

# https://atcoder.jp/contests/abc059/tasks/arc072_a
# C - Sequence
import copy
N = int(input().split()[0])
a_list = list(map(int, input().split()))

w_list_1 = copy.copy(a_list)
w_list_2 = copy.copy(a_list)
c_1, c_2 = 0, 0
s_1, s_2 = 0, 0
c_list = []

for i in range(N):  # 10 ** 5
    # 偶数項を正にする場合
    before = w_list_1[i]
    s_1 += before

    if i % 2 == 0 and s_1 < 0:
        w_list_1[i] += abs(s_1)
        c_1 += abs(s_1)
    elif i % 2 != 0 and s_1 >= 0:
        w_list_1[i] -= abs(s_1+1)
        c_1 += abs(s_1+1)

    s_1 = s_1 - before + w_list_1[i]

    if s_1 == 0:
        a = w_list_1[i]
        w_list_1[i] = a + 1 if a >= 0 else a - 1
        s_1 = 1 if a >= 0 else -1
        c_1 += 1

    # 偶数項を負にする場合
    before = w_list_2[i]
    s_2 += before

    if i % 2 == 1 and s_2 < 0:
        w_list_2[i] += abs(s_2)
        c_2 += abs(s_2)
    elif i % 2 != 1 and s_2 >= 0:
        w_list_2[i] -= abs(s_2+1)
        c_2 += abs(s_2+1)

    s_2 = s_2 - before + w_list_2[i]

    if s_2 == 0:
        a = w_list_2[i]
        w_list_2[i] = a + 1 if a >= 0 else a - 1
        s_2 = 1 if a >= 0 else -1
        c_2 += 1

ans = min([c_1, c_2])
print(ans)
### BUGGY CODE ###

n,w=map(int,input().split())
l=[list(map(int,input().split())) for _ in [0]*n]
dp=[[0 for _ in range(w+1)] for _ in range(n)]
dp[0][l[0][0]]=l[0][1]
for i in range(1,n):
    for j in range(w+1):
        if j-l[i][0]>=0:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-l[i][0]]+l[i][1])
        else:dp[i][j]=dp[i-1][j]
print(max(dp[n-1]))

### FIXED CODE ###

n,w=map(int,input().split())
l=[list(map(int,input().split())) for _ in [0]*n]
dp=[0 for _ in range(w+1)]
for i in range(n):
    for j in range(w,l[i][0]-1,-1):
        dp[j]=max(dp[j],dp[j-l[i][0]]+l[i][1])
print(max(dp))
### BUGGY CODE ###

S = input()
N = len(S)
for _ in range(N//2):
    S = S.replace('01','').replace('10','')
    S = S.replace('10','').replace('01','')
    if S.count('01') == 0 and S.count('10') == 0:
        break
print(N - len(S))

### FIXED CODE ###

S = input()
r = S.count('0')
b = S.count('1')
print(min(r,b)*2)
### BUGGY CODE ###

s = int(input())
a = [s]
i = 1
while True:
  if s % 2 == 0:
    s = s // 2
  else:
    s = 3 * s + 1
  if s in a:
    print(len(a) + 1)
  a.append(s)

### FIXED CODE ###

s = int(input())
a = [s]
i = 1
while True:
  if s % 2 == 0:
    s = s // 2
  else:
    s = 3 * s + 1
  if s in a:
    print(len(a) + 1)
    break
  a.append(s)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

s = input().rstrip()
n = len(s)
ranges = []
g = [[] for _ in range(n + 1)]
ans = 0

for i in range(n):
    for j in range(i + 3, i + 10**6):
        if j >= n:
            continue
        s_ = s[i:j + 1]
        if int(s_) % 2019 == 0:
            ranges.append([i, j + 1])
            g[i].append(j + 1)

visited = set()
ans = 0

for i in range(n):
    if i in visited or len(g[i]) == 0:
        continue
    visited.add(i)
    d = 1
    while True:
        i = g[i][0]
        if len(g[i]) == 0:
            ans += (1 + d) * d // 2
            break
        else:
            d += 1
            visited.add(i)

print(ans)

    

        

### FIXED CODE ###

import sys
input = sys.stdin.readline

mod = 2019

s = input().rstrip()
n = len(s)

t = [int(s[n - 1])]

mul = 10
for i in range(n - 2, -1, -1):
    t.append((t[-1] + int(s[i])*mul) % mod)
    mul *= 10
    mul %= mod
t.append(0)

from collections import Counter

c = Counter(t)
ans = 0

for i in c.keys():
    ans += c[i]*(c[i] - 1) // 2

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

import numpy as np
from heapq import heappush, heappop

n, m, s, t = map(int, input().split())
G = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    G[u].append((v, a, b))
    G[v].append((u, a, b))


def dijkstra(start, mode):
    INF = 10 ** 15
    dist = [INF] * (n+1)
    dist[start] = 0
    q = [(0, start)]
    while q:
        d, v = heappop(q)
        if dist[v] < d:
            continue
        for w, *a in G[v]:
            d1 = d + a[mode]
            if dist[w] > d1:
                dist[w] = d1
                heappush(q, (d1, w))
    return dist


d1 = np.array(dijkstra(s, 0))
d2 = np.array(dijkstra(t, 1))

# print(d1)

d = []
for i in range(n+1):
    d.append(d1[i]+d2[i])
for i in range(1, n+1):
    print(10**15-min(d[i:]))


### FIXED CODE ###

import numpy as np
from heapq import heappush, heappop

n, m, s, t = map(int, input().split())
G = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    G[u].append((v, a, b))
    G[v].append((u, a, b))


def dijkstra(start, mode):
    INF = 10 ** 15
    dist = [INF] * (n+1)
    dist[start] = 0
    q = [(0, start)]
    while q:
        d, v = heappop(q)
        if dist[v] < d:
            continue
        for w, *a in G[v]:
            d1 = d + a[mode]
            if dist[w] > d1:
                dist[w] = d1
                heappush(q, (d1, w))
    return dist


d1 = np.array(dijkstra(s, 0))
d2 = np.array(dijkstra(t, 1))

# print(d1)


d = []
for i in range(n+1):
    d.append(d1[i]+d2[i])


ans = []
B = 10**15
for i in range(n):
    B = min(B, d[n-i])
    ans.append(B)
ans = ans[::-1]

for i in range(n):
    print(10**15-ans[i])
### BUGGY CODE ###

n = int(input())
xl = []
ans = 0
for i in range(n):
  xl.append(list(map(int, input().split())))
xl.sort(key = lambda x:x[1])
road = set()
for i in range(n):
  sub = {}
  location = xl[i][0]
  arm = xl[i][1]
  sub = {j for j in range(max(0, location-arm+1), location+arm)}
  num_sub = len(sub)
  num_road = len(road)
  Z = road|sub
  if len(Z) ==num_sub + num_road:
    road = Z
    ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
X = []
for i in range(n):
  x, l = map(int, input().split())
  X.append([x-l, x+l])
X.sort()
temp = X[0][1]
count = n
for i in range(1,n):
  if temp>X[i][0]:
    count -= 1
    temp = min(temp, X[i][1])
  else:
    temp = X[i][1]
print(count)
### BUGGY CODE ###

def gcd(a, b):
	if a < b:
		a, b = b, a
	if b == 0:
		return a
	c = a % b
	return gcd(b, c)

n = int(input())
a = list(map(int,input().split()))
gcds = []

maxt = 0
for i in range(n):

	b = a[0:i]
	b += (a[i+1:n])
	tmp = b[0]

	for bi in b[1::]:
		tmp = gcd(tmp,bi)
		
	if maxt < tmp:
		maxt = tmp
 
print (maxt)


### FIXED CODE ###

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a


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

l = [0]*(n+2) # l(i) = A1, A2, ..., A(i-1)のgcd
r = [0]*(n+2) # r(i) = Ai, A(i+1), ..., A(n)のgcd

for i in range(n):
	l[i+1] = gcd(l[i],a[i])
for i in reversed(range(n)):
	r[i] = gcd(r[i+1],a[i])

ext = [0] * n
for i in range(n):
	ext[i] = gcd(l[i],r[i+1])

print (max(ext))
### BUGGY CODE ###

R,G,B,N =map(int,input().split())

cnt =0
    
for r in range(N+1):
    
    for g in range(N+1-r*R):
        
        ball =  r*R+g*G  
        
        res = N-ball
        
        if  res >=0  and res%B ==0:
            cnt+=1
    
print(cnt)
            


### FIXED CODE ###

R,G,B,N =map(int,input().split())

cnt =0
    
for r in range(int(N/R)+1):
  ball = N-r*R 
  for g in range(int(ball/G)+1):
    res = N- (r*R+g*G)
    if  res >=0 and res%B ==0:
      cnt+=1
    
print(cnt)
### BUGGY CODE ###

S = input()
Q = int(input())
s = list(S)

rev = 0

for i in range(Q):
    query = input()
    ti = list(query)[0]
    if ti == '1':
        rev = (rev + 1) % 2
    else:
        ti, fi, ci = query.split()
        if (int(fi) + rev) == 2:
            s.append(ci)
        else:
            s.insert(0, ci)

if rev == 1:
    s.reverse()
print(''.join(s))

### FIXED CODE ###

class Node:
    def __init__(self, char: str):
        self.before = None
        self.char = char
        self.next = None

class Linked_List:
    def __init__(self):
        self.head = None
        self.tail = None
    
    def add_head(self, node):
        if self.head is None:
            self.head = node
            self.tail = node
        else:
            node.next = self.head
            self.head.before = node
            self.head = node

    def add_tail(self, node):
        if self.tail is None:
            self.head = node
            self.tail = node
        else:
            node.before = self.tail
            self.tail.next = node
            self.tail = node

    def show(self, is_reversed: bool):
        ret = []
        node = self.tail if is_reversed else self.head
        while not node is None:
            c = ''.join(list(node.char)[::-1]) if is_reversed else node.char
            ret.append(c)
            node = node.before if is_reversed else node.next
        print(''.join(ret))

S = input()
Q = int(input())
ll = Linked_List()
ll.add_head(Node(S))
is_reversed = False

for _ in range(Q):
    query = input()
    if query[0] == '1':
        is_reversed = False if is_reversed else True
    else:
        t, f, c = query.split()
        if is_reversed:
            c = ''.join(list(c)[::-1])
        if f == '1':
            if is_reversed:
                ll.add_tail(Node(c))
            else:
                ll.add_head(Node(c))
        else:
            if is_reversed:
                ll.add_head(Node(c))
            else:
                ll.add_tail(Node(c))

ll.show(is_reversed)
### BUGGY CODE ###

def z_algorithm(S):
    n = len(S)
    A = [0] * n
    A[0] = n
    L = 0
    R = 0
    # 過去にS[R]まで調べたとする
    for i in range(1, n):
        if R <= i:
            L = R = i
            while R < n and S[R] == S[R - L]:
                R += 1
            A[i] = R - L
        elif A[i - L] < R - i:
            A[i] = A[i - L]
        else:
            L = i
            while R < n and S[R] == S[R - L]:
                R += 1
            A[i] = R - L
    return A


def main():
    N = int(input())
    S = input()
    l = len(S)
    answer = 0
    for i in range(1, N - 1):
        a = z_algorithm(S[i:])
        for j in range(1, l - i):
            cnt = min(j, a[j])
            if cnt > answer:
                answer = cnt

    print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def z_algorithm(S):
    n = len(S)
    A = [0] * n
    A[0] = n
    L = 0
    R = 0
    # 過去にS[R]まで調べたとする
    for i in range(1, n):
        if R <= i:
            L = R = i
            while R < n and S[R] == S[R - L]:
                R += 1
            A[i] = R - L
        elif A[i - L] < R - i:
            A[i] = A[i - L]
        else:
            L = i
            while R < n and S[R] == S[R - L]:
                R += 1
            A[i] = R - L
    return A


def main():
    N = int(input())
    S = input()
    answer = 0
    for i in range(N):
        a = z_algorithm(S[i:])
        for j in range(1, N - i):
            cnt = min(j, a[j])
            if cnt > answer:
                answer = cnt

    print(answer)


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

import math
N=int(input())
X=math.factorial(N)
Y=X%(1000000007)
print(Y)

### FIXED CODE ###

import math
N=int(input())
X=math.factorial(N)
Y=X%(1000000007)
print(Y)
### BUGGY CODE ###

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

ans = 0

for k in range(N):
  # k＝０を避けるため
  s = P[0:k+1]
  min_k = min(s)
  if min_k == P[k]:
    ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
 
m = 10**6
ans = 0
for p in P:
    if p < m:
        m = p
        ans += 1
print(ans)
### BUGGY CODE ###

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

AI = sorted([(a, i) for i, a in enumerate(A)])

dic = list()
tmp = 0
for i, (a, pos) in enumerate(AI):
    if a > 2 * 10**5:
        break
    if tmp != a:
        tmp = a
        dic.append((a, i))

nums = [a for (a, i) in dic]
inds = [i for (a, i) in dic]
inds.append(N)
L = len(dic)


def check(p1, p2):
    # print(p1, p2)
    sumsum = nums[p1] + nums[p2]
    ret = 0
    for i in range(inds[p1], inds[p1+1]):
        for j in range(inds[p2], inds[p2+1]):
            if sumsum == abs(AI[i][1] - AI[j][1]):
                ret += 1
    # print("return ", ret)
    return ret // 2 if p1 == p2 else ret


# print(dic)
# print(nums)
# print(inds)

ans = 0
for i in range(L):
    for j in range(i, L):
        if nums[i] + nums[j] > 2 * 10**5:
            continue
        ans += check(i, j)

print(ans)


### FIXED CODE ###

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

L = {}
R = {}
for i, a in enumerate(A):
    x = i + 1 + a
    L[x] = L[x] + 1 if x in L else 1

    x = i + 1 - a
    R[x] = R[x] + 1 if x in R else 1

# print(L, R)

ans = 0
for x in L.keys():
    ans += L[x] * (R[x] if x in R else 0)

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

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

n,m=[int(i) for i in input().split()]
a1=[int(input()) for i in range(m)]
a1.append(n+1)
c1=1
a2=0
for i in range(m+1):
    a3=a1[i]-1-a2
    a4=a3//2
    c2=0
    c3=1
    for j in range(0,a4+1):
        c3=combinations_count(a3-j,j)
        c2+=c3
        #print(c3)
    #print(c2)
    c1=c1*c2%(1000000007)
    a2=a1[i]+1



print(c1)


### FIXED CODE ###

#フィボナッチ数列か…
#c問題も解けないのか…
#典型問題なんだろうな
#踏めない段の分は除いて考えれば良い
n,m=input().split()
n,m=int(n),int(m)
ax=[1]*(n+1)
for i in range(m):
    ax[int(input())]=0
bx=[1,1]
for i in range(2,n+1):
    if ax[i-1]==1:
        f1=bx[i-1]
    else:
        f1=0
    if ax[i-2]==1:
        f2=bx[i-2]
    else:
        f2=0
    bx.append((f1+f2)%(10**9+7))

print(bx[n])
### BUGGY CODE ###

INF = 1000000000

def solve(s,g,E,n):
  D = [INF for i in range(n)]
  D[s] = 0
  V = [(0,s)]
  while V:
    v = V.pop(0)
    for e in E[v[1]]:
      if D[v[1]] + e[1] < D[e[0]]:
        D[e[0]] = D[v[1]] + e[1]
        V.append((D[e[0]],e[0]))
        V.sort()
  if D[g] >= INF:
    print(-1)
  else:
    print(D[g])
  
while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    E = [[] for i in range(n)]
    for i in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        solve(lst[1] - 1, lst[2] - 1, E, n)
      elif lst[0] == 1:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])
  except EOFError:
    break


### FIXED CODE ###

from heapq import heappush,heappop

def dij(s,g,E):
  h = []
  U = []
  heappush(h,(0,s))
  while h:
    v = heappop(h)
    if v[1] == g:
      if v[0] >= INF:print(-1)
      else:print(v[0])
      break
    U.append(v[1])
    for e in E[v[1]]:
      if not e[0] in U:
        heappush(h,(v[0] + e[1],e[0]))
  else:print(-1)
INF = 100000000
while True:
  try:
    n,k = map(int,input().split())
    if n == 0 and k == 0: break
    E = [[] for i in range(n)]
    for _ in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        dij(lst[1] - 1, lst[2] - 1, E)
      else:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])

  except EOFError:
    break