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

N = int(input())
arr = str(input())
lst =[]
for i in arr.split():
    lst.append(i)
multi = 1
for i in lst:
    multi *= int(i)
if multi > pow(10,18): print(-1)
else: print(multi)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
def nhan(A):
    multi = 1
    for i in A:
        multi *= i
        if multi > 10**18: return -1
    return multi
print(nhan(A))
### BUGGY CODE ###

N = int(input())

A= []
for i in range(N-1):
    A.append(i+2)

A.append(1)

count = 0

for i in range(N):
    count += (i+1)%A[i]

print(count)

### FIXED CODE ###

N = int(input())
print(N*(N-1)//2)
### BUGGY CODE ###

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))

for _ in range(m):
    b, c = map(int, input().split())
    C = [c for i in range(b)]
    A.extend(C)

A = sorted(A, reverse=True)
result = [A[i] for i in range(n)]
print(sum(result))

### FIXED CODE ###

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]
BC.sort(key=lambda x: -x[1])

maxi = n*2
extend = A.extend
[extend([ls[1]] * ls[0]) for ls in BC if len(A) <= maxi]
A.sort(reverse=True)

print(sum(A[:n]))
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
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 functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N = INT()
    A = LIST()

    ans = 0
    for i in range(N-1):
        for j in range(i+1, N):
            ans += A[i] * A[j] % mod

    print(ans % mod)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
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 functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N = INT()
    A = LIST()

    l = [A[0]]
    for i in range(N-2):
        l.append(l[-1] + A[i+1])

    ans = 0
    for i in range(N-1):
        ans += l[i] * A[i+1] % mod

    print(ans % mod)


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

import heapq

N = int(input())
L_list = list(map(int,input().split()))
L_list.sort()
ans = 0
list = []
M = 0

for i in range(N-1):
    for j in range(N-i-1):
        list.append((L_list[i]+L_list[j+i+1],i,j+i+1))
        M += 1

for k in range(N):
    for z in range(M):
        if L_list[k] < list[z][0]:
            if (k > list[z][2]):
                ans += 1

print(ans)



### FIXED CODE ###

import bisect

N = int(input())
l = list(map(int, input().split()))
l.sort()

ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        insert_index = bisect.bisect_left(l, l[i] + l[j],j) #l[i] + l[j]を挿入できる点を探す。同じ者がlにすでにある時は、一番左になるようにする
        ans += (insert_index - j - 1)

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

N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 1
for i in range(K):
    ans *= A[i]

for i in range(K, N):
    newans = (ans * A[i]) // A[i-K]
    print('Yes' if ans < newans else 'No')


### FIXED CODE ###

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

for ai_k, ai in zip(A, A[K:]):
    print('Yes' if ai_k < ai else 'No')
### BUGGY CODE ###



def Maximum_Profit(A,N):
    Max = A[1]-A[0]
    for i in range(N-1):
        for j in range(i+1,N):
            if (A[j]-A[i]) > Max :
                Max = A[j]-A[i]
    return Max

N = int(input())
A = [] 
for i in range (N):
    A.append(input())
A = list(map(int,A))
print(Maximum_Profit(A,N))


### FIXED CODE ###

n = int(input())
numbers = []

minv = int(input())
num = int(input())

max_r = num - minv

if(minv > num):
    minv = num

for i in range(2,n):
    num = int(input())
    if(max_r <(num - minv)):
        max_r = num - minv

    if(minv > num):
        minv = num

print(max_r)
### BUGGY CODE ###

N, K = map(int, input().split(' '))
h = list(map(int, input().split(' ')))
dp = [float('inf')]*(len(h))
dp[0] = 0
for i in range(1, len(h)):
    dp[i] = min([dp[j] + abs(h[i] - h[j]) for j in range(max(0, i-K), i)])
print(dp[-1])

### FIXED CODE ###

import numpy as np

N, K = map(int, input().split(' '))
h = np.array(list(map(int, input().split(' '))))
dp = np.zeros(len(h), dtype=int)
for i in range(1, len(h)):
    start = max(0, i-K)
    dp[i] = min(dp[start:i] + np.abs(h[i] - h[start:i]))
print(dp[-1])
### BUGGY CODE ###

#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []
    for _ in range(n):
        v, w = LI()
        V.append(v)
        W.append(w)
    
    q = I()
    vl = []
    maxL = 0
    for _ in range(q):
        v, l = LI()
        maxL = max(maxL, l)
        vl.append([v,l])
    
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1) for _ in range(m + 1)]
    
    for i in range(1, m+1):
        v, w = V[i-1], W[i-1]
        for j in range(maxL+1):
            if j < w:
                dp[i][j] = dp[i>>1][j]
            else:
                dp[i][j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)
    
    for i in range(q):
        v, L = vl[i]
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        tmp = v
        v_ = []
        w_ = []
        while tmp > m:
            v_.append(V[tmp-1])
            w_.append(W[tmp-1])
            tmp >>= 1
            cnt += 1
        ret = dp[tmp][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_tmp[b] = w_tmp[b - lsb] + w_[l-1]
            if w_tmp[b] > L:
                continue
            v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
            ret = max(ret, v_tmp[b] + dp[tmp][L - w_tmp[b]])
        print(ret)
    return

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        if i <= m:
            d_ = dp[(i+1)>>1][:]
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
            dp.append(d_)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        v_ = []
        w_ = []
        while v > m:
            v_.append(V[v-1])
            w_.append(W[v-1])
            v >>= 1
            cnt += 1
        ret = dp[v][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_t = w_tmp[b - lsb] + w_[l-1]
            w_tmp[b] = w_t
            if w_t <= L:
                v_t = v_tmp[b - lsb] + v_[l-1]
                v_tmp[b] = v_t
                ret = max(ret, v_t + dp[v][L - w_t])
        print(ret)
    return

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

s = input()
ans = 0
while 1:
    
    temp1 = s.count("01")
    ans += temp1
    s = s.replace("01", "")
    temp2 = s.count("10")
    ans += temp2
    s = s.replace("10", "")
    if temp1 == 0 and temp2 == 0:
        break
    
print(ans*2)


### FIXED CODE ###


s = input()

blue = s.count("1")
red = s.count("0")

print(2*min(blue, red))
### BUGGY CODE ###

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

def s(n,a):
  b = [0]*n
  for i in range(n):
    l = max(0,i-a[i])
    r = min(n-1,i+a[i])
    b[l] += 1
    if r < n - 1:
      b[r+1] -= 1
  for i in range(n-1):
    b[i+1] += b[i]
  return b

for i in range(min(41,K)):
  A = s(N,A)
  
print(*A)
      


### FIXED CODE ###

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

def s(n,a):
  b = [0]*n
  for i in range(n):
    l = max(0,i-a[i])
    r = min(n-1,i+a[i])
    b[l] += 1
    if r < n - 1:
      b[r+1] -= 1
  for i in range(n-1):
    b[i+1] += b[i]
  return b

for i in range(min(41,K)):
  A = s(N,A)
  
print(*A)
### BUGGY CODE ###

from collections import deque
N = int(input())
A = list(map(int, input().split()))

A.sort()
A = deque(set(A))
while len(A) > 1:
  s = []
  for i in range(len(A)-1):
    div = A[-1] % A[0]
    A.pop()
    if (div != 0) and (div not in s):
      s.append(div)
  s.append(A[0])
  s.sort()
  A = deque(s)
print(*A)

### FIXED CODE ###

from collections import deque
N = int(input())
A = list(map(int, input().split()))

A.sort()
A = deque(A)
while len(A) > 1:
  s = []
  for i in range(len(A)-1):
    div = A[-1] % A[0]
    A.pop()
    if div != 0:
      s.append(div)
  s.append(A[0])
  s.sort()
  A = deque(s)
print(*A)
### BUGGY CODE ###

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

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

lst=[None]*(N+1)
def func(n):
    if n in a:
        return 0
    if n<=1:
        return 1
    else:
        if lst[n]:
            return lst[n]
        else:
            temp=(func(n-1)+func(n-2))%(10**9+7)
            lst[n]=temp
            return temp

print(func(N))

### FIXED CODE ###

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

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

lst=[None]*(N+1)
def func(n):
    #if n in a:
    #    return 0
    if n<=1:
        return 1
    else:
        if lst[n]:
            return lst[n]
        else:
            temp=(func(n-1)+func(n-2))%(10**9+7)
            lst[n]=temp
            return temp



a=[-1]+a+[N+1]
answer=1
for i in range(M+1):
    if a[i+1]-a[i]==1:
        print(0)
        break
    answer=( func(a[i+1]-a[i]-2)*answer )%(10**9+7)
else:
    print(answer)
### BUGGY CODE ###

import heapq



N = int(input())
xy = [None] * N
yx = [None] * N

for i in range(N):
    x,y = map(int, input().split())
    xy[i] = (x, y, i)
    yx[i] = (y, x, i)


xy.sort()
yx.sort()


es = [[] for _ in range(N)]
for i in range(N-1):
    heapq.heappush(es[xy[i][2]], (abs(xy[i][0] - xy[i+1][0]), xy[i+1][2]))
    heapq.heappush(es[xy[i+1][2]], (abs(xy[i][0] - xy[i+1][0]), xy[i][2]))

    heapq.heappush(es[yx[i][2]], (abs(yx[i][0] - yx[i+1][0]), yx[i+1][2]))
    heapq.heappush(es[yx[i+1][2]], (abs(yx[i][0] - yx[i+1][0]), yx[i][2]))


used = [False] * N
used[0] = True
ans = 0

q = []
for c,nxt in es[0]:
    heapq.heappush(q, (c, nxt))

while q:
    c, curr = heapq.heappop(q)
    
    if used[curr]:
        continue

    used[curr] = True
    for nc, nxt in es[curr]:
        heapq.heappush(q, (nc, nxt))
    ans += c

print(ans)

### FIXED CODE ###

N = int(input())
towns = [tuple(map(int, input().split())) for _ in range(N)]

xs = []
ys = []

for i, (x,y) in enumerate(towns):
    xs.append((x, i))
    ys.append((y, i))

xs.sort()
ys.sort()

es = []
for (x1, i1), (x2, i2) in zip(xs, xs[1:]):
    es.append((x2-x1, i1, i2)) #i1からi2までのコストがx2-x1、絶対値とってないけど

for (y1, i1), (y2, i2) in zip(ys, ys[1:]):
    es.append((y2-y1, i1, i2)) #i1からi2までのコストがy2-y1、
es.sort()

class UnionFind:
    def __init__(self, N):
        #初めの親ノードはすべて異なる
        self.parent = [i for i in range(N)]
        #木の高さ
        self.rank = [0] * N
        self.count = 0

    #どのUnionに所属するか判定
    def root(self, a):
        #親が根の場合
        if self.parent[a] == a:
            return a
        else:
            #親の親を調べなおす＆見つかった根に接続しなおす
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]

    #同じUnionか判定
    def is_same(self, a, b):
        return self.root(a) == self.root(b)

    #Unionを作る
    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return
        #高いほうの下に小さいほうを繋ぐ
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count +=1


ans = 0
uf = UnionFind(N)
for d,a,b in es:
    #すでに繋がれてるならスキップ
    if uf.is_same(a,b):
        continue
    uf.unite(a,b) #esはソート済みのため短い順から重複をせずにN個の町が繋がれることが保証される
    ans += d
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    S = input()
    N = len(S)
    p = 10**9 + 7
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] = 1

    for i in range(N):
        if S[i] == '?':
            for j in range(13):
                for k in range(10):
                    dp[i+1][(10*j+k)%13] += dp[i][j]
                    dp[i+1][(10*j+k)%13] %= p
        else:
            s = int(S[i])
            for j in range(13):
                dp[i+1][(10*j+s)%13] = dp[i][j]
    print(dp[N][5])
    

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    S = input()
    N = len(S)
    p = 10**9 + 7
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] = 1

    for i in range(N):
        if S[i] == '?':
            for j in range(13):
                for k in range(10):
                    dp[i+1][(10*j+k)%13] += dp[i][j]
                    dp[i+1][(10*j+k)%13] %= p
        else:
            s = int(S[i])
            for j in range(13):
                dp[i+1][(10*j+s)%13] = dp[i][j]
    print(dp[N][5])
    

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

n = int(input())

total = 0
for i in range(1, n+1):
    if i == n:
        break
    total += i % (i+1)
print(total)

### FIXED CODE ###

n = int(input())
print(n*(n-1)//2)
### BUGGY CODE ###

import time
N = int(input())
L = list(map(int, input().split()))

L = sorted(L)

# print(L)

# 三角形なのでa>b>cになるように選べば, a+b>cとなる
ans = 0
for i in range(N-2):
    a = L[i]
    for j in range(i+1, N-1):
        # print("i:{}, j:{}".format(i, j))
        b = L[j]
        left = j+1
        right = N-1
        c = L[N-1]
        if a+b>c:
            # print("true - k:{}".format(N-1))
            # print("num_c:{}".format())
            ans += N-j-1
        else:
            mid = right
            while left < right:
                if mid == (left+right)//2:
                    break
                mid = (left+right)//2
                # print("left:{}, mid:{}, right:{}".format(left, mid, right))
                c = L[mid]
                if a+b>c:
                    left = mid
                else:
                    right = mid
                # time.sleep(0.05)
            # print("false - k:{}".format(mid))
            if a+b>c:
                # print("a+b>c:{}".format(True))
                ans += mid - j
            else:
                # print("a+b>c:{}".format(False))
                ans += mid - j - 1
        # print("ans of ({},{}): {}".format(i,j,ans))

print(ans)


### FIXED CODE ###

import time
N = int(input())
L = list(map(int, input().split()))

L = sorted(L)

# print(L)

# 三角形なのでa>b>cになるように選べば, a+b>cとなる
ans = 0
for i in range(N-2):
    a = L[i]
    for j in range(i+1, N-1):
        # print("i:{}, j:{}".format(i, j))
        b = L[j]
        left = j+1
        right = N-1
        c = L[N-1]
        if a+b>c:
            # print("true - k:{}".format(N-1))
            # print("num_c:{}".format())
            ans += N-j-1
        else:
            mid = right
            while left < right:
                if mid == (left+right)//2:
                    break
                mid = (left+right)//2
                # print("left:{}, mid:{}, right:{}".format(left, mid, right))
                c = L[mid]
                if a+b>c:
                    left = mid
                else:
                    right = mid
                # time.sleep(0.05)
            # print("false - k:{}".format(mid))
            if a+b>c:
                # print("a+b>c:{}".format(True))
                ans += mid - j
            else:
                # print("a+b>c:{}".format(False))
                ans += mid - j - 1
        # print("ans of ({},{}): {}".format(i,j,ans))

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

import math
import time

A,B,N = map(int,input().split())
max_n = -1
st = time.time()
for i in range(N+1) :
    # n = math.floor((A * i)/B) - A * math.floor(i/B)
    # n = ((A * i) // B) - A * (i // B)
    n = ((A * i) // B) - A * (i // B)
    # print(i,n)
    if (max_n < n) :
        max_n = n
    
    if (time.time() - st > 2) :
        break

print(max_n)

### FIXED CODE ###

def f(x) :
    return ((A * x) // B) - A * (x // B)

A,B,N = map(int,input().split())
print(f(min(B-1,N)))
### BUGGY CODE ###

N = int(input())

A = []

[A.append(int(input())) for x in range(N)]

max_num = 0

for i in range(N):
    for j in range(N):
        if j != i and max_num < A[j]:
            max_num = A[j]
    print(max_num)
    max_num = 0


### FIXED CODE ###

N = int(input())

A = []

[A.append(int(input())) for x in range(N)]

max_num = max(A)
num = A.index(max(A))
A[num] = 0

st_max_num = max(A)

for i in range(num):
    print(max_num)
print(st_max_num)

for i in range(num+1,N):
    print(max_num)
### BUGGY CODE ###

N,A = map(int,input().split())
L = list(map(int,input().split()))
#for i in range(N) :
#    L[i] -= A
#L = sorted(L)
ans = 0
for bit in range(1 << N) :
    calc = 0
    ctr = 0
    for k in range(N) :
        if bit & (1 << k) :
            calc += L[k]
            ctr += 1
    if calc == 0 :
        continue
    if calc == A*ctr :
        ans += 1
print(ans)


### FIXED CODE ###

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

X = list(map(int,input().split()))

ma = max(X)

dp = [[[0 for s in range(ma*N+1)] for k in range(N+1)] for i in range(N+1)]

dp[0][0][0] = 1

for i in range(1,N+1) :
    for k in range(i+1) :
        for s in range(ma*N+1) :
            if (k >= 1) and (s >= X[i-1]) :
                dp[i][k][s] = dp[i-1][k][s] + dp[i-1][k-1][s-X[i-1]]
            else :
                dp[i][k][s] = dp[i-1][k][s]

ans = 0

for k in range(1,N+1) :
    if k*A > ma*N :
        break
    ans += dp[N][k][k*A]

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

import sys
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
g = []
for i in range(n-1):
    u,v,w = na()
    g.append([u,v,w])

a = [0,0]+[-1]*(n-1)

while True:
    f = False
    for i in range(n-1):
        b = True
        if g[i][2]%2 == 0:
            b = False
        if a[g[i][0]] == -1 or a[g[i][1]] == -1:
            f = True
        if a[g[i][0]] == 0:
            if b:
                a[g[i][1]] = 1
            else:
                a[g[i][1]] = 0
        elif a[g[i][0]] == 1:
            if b:
                a[g[i][1]] = 0
            else:
                a[g[i][1]] = 1
        if a[g[i][1]] == 0:
            if b:
                a[g[i][0]] = 1
            else:
                a[g[i][0]] = 0
        elif a[g[i][1]] == 1:
            if b:
                a[g[i][0]] = 0
            else:
                a[g[i][0]] = 1
    if not f:
        break

for i in range(1,n+1):
    print(a[i])

### FIXED CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
g = [[] for i in range(n)]

for i in range(n-1):
    u,v,w = na()
    g[u-1].append((v-1,w))
    g[v-1].append((u-1,w))

dp = [0]*n

def f(a,b,c):
    dp[b] = c
    for i,j in g[b]:
        if i != a:
            f(b,i,c+j)

f(0,0,0)

for k in dp:
    print(k%2)
### BUGGY CODE ###

n, m = map(int, input().split())

a_list=[]

for index in range(m):
    a_list.append(int(input()))

ans_list=[]

for index in range(n + 1):
    ans_list.append(0)

for index in range(n + 1):
    if index == 0:
        ans_list[index] += 1
        continue
    if index == 1 and (index not in a_list):
        ans_list[index] += ans_list[index - 1]
        continue
    
    if index not in a_list:
        if (index - 1) not in a_list:
            ans_list[index] += ans_list[index - 1]
            ans_list[index] %= 1000000007
        if (index - 2) not in a_list:
            ans_list[index] += ans_list[index - 2]
            ans_list[index] %= 1000000007

print(ans_list[n])


### FIXED CODE ###

n, m = map(int, input().split())

a_set=set()

for index in range(m):
    a_set.add(int(input()))

ans_list=[]

for index in range(n + 1):
    ans_list.append(0)

for index in range(n + 1):
    if index == 0:
        ans_list[index] += 1
        continue
    if index == 1 and (index not in a_set):
        ans_list[index] += ans_list[index - 1]
        continue
    
    if index not in a_set:
        if (index - 1) not in a_set:
            ans_list[index] += ans_list[index - 1]
            ans_list[index] %= 1000000007
        if (index - 2) not in a_set:
            ans_list[index] += ans_list[index - 2]
            ans_list[index] %= 1000000007

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

n,k=map(int,input().split())
h=[int(input()) for _ in range(n)]
h.sort()
INF=2*10**9
ans=INF
for i in range(n-k+1):
	diff=max(h[i:i+k])-min(h[i:i+k])
	if ans>diff:
		ans=diff
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
h=[int(input()) for _ in range(n)]
h.sort()
INF=2*10**9
ans=INF
for i in range(n-k+1):
	diff=h[i+k-1]-h[i]
	if ans>diff:
		ans=diff
		if ans==0:
			print(0)
			exit()
print(ans)