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

# ABC100 C "*3 or /2"

import numpy
N = int(input())
a = numpy.array(list(map(int, input().split())))
# a.sort(reversed = False)
a.sort()
a = a[::-1]

count = 1

if all(elem % 2 !=0 for elem in a) == True:
    ans = 0
else:
    while True:
        if all(elem % 2 !=0 for elem in a) == True:
            ans = count -1
            break
        else:
            for ind in range(N):
                if a[ind] % 2 ==0:
                    i = ind
                    break
            a[i] = a[i]/2
            a[:i] = a[:i]*3
            a[i+1:] = a[i+1:]*3
            a.sort()
            a = a[::-1]
            count += 1
        
print(ans)

### FIXED CODE ###

import numpy
N = int(input())
a = numpy.array(list(map(int, input().split())))
count = 0

for i in range(N):
    if a[i] % 2 == 0:
        x = a[i]
        while True:
            if x %2 != 0:
                break
            else:
                x = x/2
                count+=1
print(count)
### BUGGY CODE ###

n,m = map(int, input().split())
a = [int(input()) for i in range(m)]
memo = [0]*(n+1)

memo[0] = 1
if 1 in a:
    memo[1] = 0
else:
    memo[1] = 1
for i in range(2,n+1):
    if i in a:
        continue
    memo[i] = (memo[i-1] + memo[i-2])%1000000007

print(memo[n])

### FIXED CODE ###

n,m = map(int, input().split())
a = set([int(input()) for i in range(m)])
memo = [0]*(n+1)

memo[0] = 1
if 1 in a:
    memo[1] = 0
else:
    memo[1] = 1
for i in range(2,n+1):
    if i in a:
        continue
    memo[i] = (memo[i-1] + memo[i-2])%1000000007

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

import fractions
a,b=list(map(int,input().split()))
cnt=0

def f(a,b):
  max=fractions.gcd(a,b)
  if min(a,b)==1:re=[max]
  else:re=[1,max]
  for i in range(2,max):
    if a%i==0 and b%i==0:re.append(i)
  return re
 
def g(n):
  if n==0:return False
  for i in range(2,n):
    if n%i==0:return False
  else:return True

for i in f(a,b):
  if g(i)==True:
    cnt+=1
print(cnt)

### FIXED CODE ###

import math,fractions
a,b=list(map(int,input().split()))

def f(n):
    a=[1]
    while n%2==0:
        a.append(2)
        n//=2
    f=3
    while f*f<= n:
        if n%f==0:
            a.append(f)
            n//= f
        else:
            f+= 2
    if n!=1:
        a.append(n)
    return a

def g(n,r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))
 
ans=set(f(a))&set(f(b))
#print(ans)
print(len(ans))
### BUGGY CODE ###

n = int(input())
s = []
ans = 0
for _ in range(n):
    s.append(sorted(str(input())))
for i in range(n-1):
    for j in range(i+1, n):
        if s[i] == s[j]: ans +=1
print(ans)

### FIXED CODE ###

n = int(input())
s = []
d = {}
for _ in range(n):
    s.append("".join(sorted(str(input()))))
for si in s:
    if si not in d.keys():
        d[si] = 1
    else: d[si] += 1
ans = 0
val = d.values()
for v in val:
    ans += v*(v-1)/2
print(int(ans))
### BUGGY CODE ###

import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, P = list(map(int, sys.stdin.buffer.readline().split()))
S = list(map(int, list(sys.stdin.buffer.readline().decode().rstrip())))


def toint(l, r):
    return int(''.join(map(str, S[l:r])))


def test():
    ans = 0
    for l, r in itertools.combinations_with_replacement(range(N), r=2):
        s = toint(l, r + 1)
        ans += s % P == 0
    print(ans)


def solve25():
    ret = 0
    for d in range(N):
        if S[d] % P == 0:
            ret += d + 1
    return ret


# 10 mod P で割れない
if P in [2, 5]:
    ans = solve25()
    print(ans)
    exit()

# test()


def to_index(i, p):
    if i == 0:
        return p % P
    return (p - toint(1, i + 1)) * pow(pow(10, i, P), P - 2, P) % P


mod_counts = [0] * P
ans = 0
for i, c in enumerate(S):
    mod_counts[to_index(i, c)] += 1
    ans += mod_counts[to_index(i, 0)]
print(ans)


### FIXED CODE ###

import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def toint(l, r):
    return int(''.join(map(str, S[l:r])))


def test():
    ans = 0
    for l, r in itertools.combinations_with_replacement(range(N), r=2):
        s = toint(l, r + 1)
        ans += s % P == 0
    print(ans)


def solve25():
    ret = 0
    for d in range(N):
        if S[d] % P == 0:
            ret += d + 1
    return ret


def mod_invs(max, mod):
    """
    逆元 0, 1/1, 1/2, 1/3, ..., 1/max
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    invs[0] = 0
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


N, P = list(map(int, sys.stdin.buffer.readline().split()))
S = list(map(int, list(sys.stdin.buffer.readline().decode().rstrip())))

# 10 mod P で割れない
if P in [2, 5]:
    ans = solve25()
    print(ans)
    exit()

# test()

powers = []
p = 1
for _ in range(N):
    powers.append(p)
    p = p * 10 % P
# int(S[1:1]), int(S[1:2]), int(S[1:3]), ...
s_additions = [0]
s = 0
for i in range(1, N):
    s = (s * 10 + S[i]) % P
    s_additions.append(s)
invs = mod_invs(max=P - 1, mod=P)


def to_index(i, p):
    # もともと x だったのが、i 番目で p になっているときの x を返す
    if i == 0:
        return p % P
    return (p - s_additions[i]) * invs[powers[i]] % P


mod_counts = [0] * P
ans = 0
for i, c in enumerate(S):
    mod_counts[to_index(i, c)] += 1
    ans += mod_counts[to_index(i, 0)]
print(ans)
### BUGGY CODE ###

import math

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

for i in range(n):
    ans = 0
    A_tmp = A[: i] + A[i + 1: ]
    D = dict.fromkeys(A_tmp, 0)
    for k in D.keys():
        D[k] = A_tmp.count(k)
    for v in D.values():
        if v >= 2:
            ans += math.factorial(v) // (2 * math.factorial(v - 2))
    print(ans)

### FIXED CODE ###

import math
import collections

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

equal = 0
elements = collections.Counter(A)
equal = sum([v * (v - 1) // 2 for v in elements.values()])

for i in range(n):
    equal_i = elements[A[i]] - 1
    print(equal - equal_i)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()

for i in range(Q):
  l, r = map(int, input().split())
  P = S[l-1: r]
  cnt = 0
  flg = False
  for p in P:
    if flg:
      if p == 'C':
        cnt += 1
      flg = False
    elif p == 'A':
      flg = True
  print(cnt)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
 
C = [0]
 
cnt = 0
flg = False
for s in S:
  if flg:
    if s == 'C':
      cnt += 1
    flg = False
  if s == 'A':
    flg = True
  C.append(cnt)
 
for i in range(Q):
  l, r = map(int, input().split())
  ans = C[r] - C[l-1]
  if l-2 >= 0 and S[l-1] == 'C' and S[l-2] == 'A':
    ans -= 1
  print(ans)
### BUGGY CODE ###

n = int(input())
trans = [int(input()) for _ in range(5)]

people = [n, 0, 0, 0, 0, 0]
cnt = 0

while people[5] < n:
    for i in reversed(range(0, len(trans))):
        if people[i] >= trans[i]:
            people[i] -= trans[i]
            people[i+1] += trans[i]
        else:
            people[i + 1] += people[i]
            people[i] = 0
    cnt += 1
print(cnt)
    


### FIXED CODE ###

import math
n = int(input())
trans = [int(input()) for _ in range(5)]

min_trans = min(trans)
print(math.ceil(n/min_trans) + 4)
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
grid = '#' * (W+2)
for _ in range(H):
    grid += '#' + input() + '#'
grid += '#' * (W+2)
move = [1, -1, W+2, -W-2]

def bfs(start):
  lst = [10**9] *((H+2)*(W+2))
  lst[start] = 0
  q = deque([start])
  while q:
    x = q.popleft()
    dx = lst[x]
    for d in move:
      y = x + d
      if grid[y] == '#':
        continue
      dy = dx + 1
      if dy > lst[y]:
        continue
      lst[y] = dy
      q.append(y)
  ans = max(x for x in lst if x < 10**9)
  return ans
  
  
print(max(bfs(i) for i in range((H+2)*(W+2)) if grid[i] != '#'))

### FIXED CODE ###

from collections import deque
import sys

H, W = map(int, input().split())
grid = '#' * (W+2)
for _ in range(H):
    grid += '#' + input() + '#'
grid += '#' * (W+2)
move = [1, -1, W+2, -W-2]

def bfs(start):
  lst = [10**9] *((H+2)*(W+2))
  lst[start] = 0
  q = deque([start])
  while q:
    x = q.popleft()
    dx = lst[x]
    for d in move:
      y = x + d
      if grid[y] == '#':
        continue
      dy = dx + 1
      if dy >= lst[y]:
        continue
      lst[y] = dy
      q.append(y)
  return max(x for x in lst if x < 10**9)
  
  
print(max(bfs(i) for i in range((H+2)*(W+2)) if grid[i] != '#'))
### BUGGY CODE ###

N,K=map(int,input().split())
L=list(map(int,input().split()))
M=0
M_IND=0

for i in range(len(L)-(K-1)):
  tmp = sum(L[i:i+K])
  #print(tmp)
  if M < tmp:
    M = tmp
    M_IND=i
#print(M_IND)
#for k in range(L[M_IND,M_IND+K])
ANS=0
for i in L[M_IND:M_IND+K]:
  #print(i)
  ex = 0
  p = 1/i
  for x in range(i+1):
      px = p*x
      ex += px
  ANS += ex
print(ANS)

### FIXED CODE ###

def kitai(n):
  return (int(n)+1)/2

import numpy as np
n,k=map(int,input().split())

L=np.array([list(map(kitai, input().split()))]).reshape(-1)

from itertools import accumulate

acc = [0]+ list(accumulate(L)) # 0を忘れずに
ans = 0
for i in range(n-k+1):
  ans = max(ans,acc[i+k]-acc[i])
print(ans)
### BUGGY CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline
N, M = map(int, input().split())
g = defaultdict(list)
for i in range(M):
  a, b = map(int, input().split())
  g[a].append(b)
  g[b].append(a)
ans = [0 for _ in range(N+1)]
#print(g)
current = [1]
while 0 in ans[2:]:
  #print(ans)
  next = []
  for i in current:
    #print('i',i)
    for j in g[i]:
      if ans[j] == 0:
        ans[j] = i
        next.append(j)
  current = next
print('Yes')
for i in range(2,N+1):
  print(ans[i])


### FIXED CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline
N, M = map(int, input().split())
g = defaultdict(list)
for i in range(M):
  a, b = map(int, input().split())
  g[a].append(b)
  g[b].append(a)
que = [1]
ans = [0 for _ in range(N+1)]
while len(que)>0:
  current = que.pop(0)
  for next in g[current]:
    if ans[next] == 0:
      que.append(next)
      ans[next] = current
print('Yes')
for i in range(2,N+1):
  print(ans[i])
### BUGGY CODE ###

N=int(input())
L=list(map(int,input().split()))
A=1
ANS=0
while A!=0:
  A = 0
  for i in range(N):
    if L[i] % 2 == 0 and A == 0:
      L[i] = L[i] // 2
      A = 1
    else:
      L[i] *= 3
  if A != 0:
  	ANS += 1
print(ANS)

### FIXED CODE ###

N=int(input())
L=list(map(int,input().split()))
A=1
ANS=IND=0
while A!=0:
  A = 0
  for i in range(IND, N):
    if L[i] % 2 == 0 and A == 0:
      L[i] = L[i] // 2
      A = 1
      break
    else:
      IND += 1
  if A != 0:
  	ANS += 1
print(ANS)
### BUGGY CODE ###

n,k = map(int,input().split())
H = sorted([int(input()) for _ in range(n)])
ans = float("INF")
for i in range(0,n - k + 1):
  selected = H[i:k + i]
  ans = min(ans,max(selected) - min(selected))
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
H = sorted([int(input()) for _ in range(n)])
ans = float("INF")
for i in range(n - k + 1):
  diff = H[k + i -1] - H[i]
  ans = min(ans,diff)
print(ans)
### BUGGY CODE ###

def d_moving_piece():
    N, K = [int(i) for i in input().split()]
    P = [int(i) - 1 for i in input().split()]  # マスの番号は 0-indexed とする
    C = [int(i) for i in input().split()]

    # 順列をサイクルごとに分解
    is_visited = [False] * N
    cycles = []  # サイクルごとのスコアを記録
    for i in range(N):
        if is_visited[i]:
            continue

        current = i
        t = []
        while not is_visited[current]:
            is_visited[current] = True
            t.append(C[current])
            current = P[current]
        cycles.append(t)

    ans = -float('inf')
    for s in cycles:
        m = len(s)

        # サイクルを 2 周したものの累積和
        total = [0] * (2 * m + 1)
        for i in range(2 * m):
            total[i + 1] = total[i] + s[i % m]

        reminder = [-float('inf')] * m  # [r]: 連続する r 個の和の最大値
        for i in range(m):
            for j in range(m):
                reminder[j] = max(reminder[j], total[i + j] - total[i])

        # 「余り」の長さで場合分け
        for r in range(m):
            if r > K:
                continue  # 移動できる回数より多く動いたことになり、矛盾

            q = (K - r) // m  # この回数だけサイクルを 1 周する
            if r == 0 and q == 0:
                continue  # 動いていないので、除外

            if total[m] > 0:
                # 周回したほうが得なので、可能な限り周回する
                ans = max(ans, reminder[r] + total[m] * q)
            elif r > 0:
                # 周回すると損なので、必要なだけ (r 回) 移動したら終わる
                ans = max(ans, reminder[r])
    return ans

print(d_moving_piece())

### FIXED CODE ###

def d_moving_piece():
    N, K = [int(i) for i in input().split()]
    P = [int(i) - 1 for i in input().split()]  # マスの番号は 0-indexed とする
    C = [int(i) for i in input().split()]

    # 順列をサイクルごとに分解
    is_visited = [False] * N
    cycles = []  # サイクルごとのスコアを記録
    for i in range(N):
        if is_visited[i]:
            continue

        current = i
        t = []
        while not is_visited[current]:
            is_visited[current] = True
            t.append(C[current])
            current = P[current]
        cycles.append(t)

    ans = -float('inf')
    for s in cycles:
        m = len(s)

        # サイクルを 2 周したものの累積和
        total = [0] * (2 * m + 1)
        for i in range(2 * m):
            total[i + 1] = total[i] + s[i % m]

        reminder = [-float('inf')] * m  # [r]: 連続する r 個の和の最大値
        for i in range(m):
            for j in range(m):
                reminder[j] = max(reminder[j], total[i + j] - total[i])

        # 「余り」の長さで場合分け
        for r in range(m):
            if r > K:
                continue  # 移動できる回数より多く動いたことになり、矛盾

            q = (K - r) // m  # この回数だけサイクルを 1 周する
            if r == 0 and q == 0:
                continue  # 動いていないので、除外

            if total[m] > 0:
                # 周回したほうが得なので、可能な限り周回する
                ans = max(ans, reminder[r] + total[m] * q)
            elif r > 0:
                # 周回すると損なので、必要なだけ (r 回) 移動したら終わる
                ans = max(ans, reminder[r])
    return ans

print(d_moving_piece())
### BUGGY CODE ###

a,b,c,n=map(int,input().split())
q=0
for i in range(n//a+1):
  for j in range((n-a*i)//b+1):
    t=n-i*a-j*b
    if t%c==0and t//c>=0:
      q+=1
print(q)


### FIXED CODE ###

a,b,c,n=map(int,input().split())
q=0
for i in range(n//a+1):
  for j in range((n-a*i)//b+1):
    t=n-i*a-j*b
    if t%c==0:
      q+=1
print(q)
### BUGGY CODE ###

def binarySearch(list_a, key):
    left = 0
    right = len(list_a)
    while left < right:
        mid = (left + right) // 2
        if list_a[mid] == key:
            return mid
            break
        elif key < list_a[mid]:
            right = mid
        else:
            left = mid+1
    else:
        return mid

n,k = map(int, input().split())
list_x = list((map(int, input().split())))
ans = 10**9
key_point = binarySearch(list_x,0)
for i in range(key_point-k+1,key_point+1):
    if i < 0:
        continue
    try:
        prob_list = list_x[i:i+k]
        dist = min(abs(prob_list[0]),abs(prob_list[k-1])) + (prob_list[k-1] - prob_list[0])
        if ans > dist:
            ans = dist
    except:
        pass
print(ans)

### FIXED CODE ###

def binarySearch(list_a, key):
    left = 0
    right = len(list_a)
    while left < right:
        mid = (left + right) // 2
        if list_a[mid] == key:
            return mid
            break
        elif key < list_a[mid]:
            right = mid
        else:
            left = mid+1
    else:
        return mid

n,k = map(int, input().split())
list_x = list((map(int, input().split())))
ans = 10**9
key_point = binarySearch(list_x,0)
for i in range(key_point-k,key_point+1):
    if i < 0:
        continue
    try:
        dist = min(abs(list_x[i]),abs(list_x[i+k-1])) + (list_x[i+k-1] - list_x[i])
        if ans > dist:
            ans = dist
    except:
        pass
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0
len_s = len(s)

for i in range(len_s):
    for j in range(i+1, len_s):
        if s[i] == s[j]:
            continue
        for k in range(j+1, len_s):
            if (s[i] != s[k] and s[j] != s[k]) and (j-i != k-j):
                ans += 1

print(ans)


### FIXED CODE ###

n = int(input())
s = input()
ans = s.count('R') * s.count('G') * s.count('B')

for i in range(n):
    for j in range(i+1, n-1):
        k = 2 * j - i
        if(k < n):
            if s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
                ans -= 1

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

X,K,D = map(int, input().split())
x = 0
if X == 0:
  if K%2 == 0:
    print (0)
  else:
    print (abs(D))
  x =1
elif X < 0:
  if abs(X) >= K*D:
    print (abs(X+K*D))
    x = 1
  if x == 0:
    for i in range (K):
      X += D
      if X >= 0:
        if (K-i-1)%2 == 0:
          print (abs(X))
        else:
          print (abs(X-D))
        x = 1
        break
else:
  if X >= K*D:
    print (X-K*D)
    x = 1
  if x == 0:
    for i in range (K):
      X -= D
      if X < 0:
        if (K-i)%2 == 0:
          print (abs(X+D))
        else:
          print (abs(X))
        x = 1
        break

### FIXED CODE ###

X,K,D = map(int, input().split())
x = 0
if X == 0:
  if K%2 == 0:
    print (0)
  else:
    print (abs(D))
  x =1
elif X < 0:
  if abs(X) >= K*D:
    print (abs(X+K*D))
  else:
    K = K-(-1*X//D)
    X = X+(-1*X//D)*D
    if K%2 == 0:
      print (abs(X))
    else:
      print (abs(X+D))
else:
  if X >= K*D:
    print (X-K*D)
  else:
    K = K-(X//D)
    X = X-(X//D)*D
    if K%2 == 0:
      print (abs(X))
    else:
      print (abs(X-D))
### BUGGY CODE ###

N = int(input())
si = [''.join(sorted(list(input()))) for i in range(N)]

result = []
for i in si:
    result.append(si.count(i)-1)

print(int(sum(result)/2))


### FIXED CODE ###

from collections import Counter

N = int(input())
si = [''.join(sorted(list(input()))) for i in range(N)]

count = Counter(si)

ans = 0
for s in set(si):
    n = count[s]
    ans += n * (n-1) // 2

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

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



if N>K:
    dp=[1000000000]*N
    dp[0]=0
    for i in range(1,K):
        dp[i]=abs(H[i]-H[0])

    for i in range(K,N):
        for j in range(1,K+1):
            dp[i]=min(dp[i], dp[i-j]+abs(H[i-j]-H[i]))

    print(dp[N-1])

else:
    print(abs(H[N-1]-H[0]))

### FIXED CODE ###

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



if N>K:
    dp=[1000000000]*N
    dp[0]=0
    for i in range(1,K):
        dp[i]=abs(H[i]-H[0])

    for i in range(K,N):
        for j in range(1,K+1):
            dp[i]=min(dp[i], dp[i-j]+abs(H[i-j]-H[i]))

    print(dp[N-1])

else:
    print(abs(H[N-1]-H[0]))
### BUGGY CODE ###

# https://atcoder.jp/contests/abc151/tasks/abc151_e
# NCK種のすべてのSについてf(S)の合計をもとめる.
# S1,S2...とすると
# sum_i f(Si) = max(S1) + max(S2) ... max(S NCK) - (min(S1) + min(S2) ... min(S NCK))
# となる。
# sum_i max(Si)について考えると、ある要素を固定したときにそれが最大となるような集合を全パターン持ってくれば簡単に計算できる
# 例えば 1 1 3 4 (K=2)で 4が最大となるとり方は3C1(K-1)
# 3が最大となるとり方は(2C1)
# 1が最大となるとり方は(1C1)
# 1が最大となるとり方は(0C1=0)
# 以上によりsum_i max(Si) = 4 * 3C1 + 2*2C1 + 1*1C1 となる

MOD = 10**9 + 7


def combination_mod(n, r, mod):
    if r > n or n == 0:
        return 0  # このような通りの数は無いため便宜上こう定義する
    r = min(r, n - r)
    nf = rf = 1
    for i in range(r):
        nf = nf * (n - i) % mod
        rf = rf * (i + 1) % mod
    return nf * pow(rf, mod - 2, mod) % mod


import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


N, K = read_ints()
A = read_ints()
A.sort()

# 通りの数を先に計算しておく
k = K - 1
conbi = []
for i in range(N):
    conbi.append(combination_mod(i, k, MOD))
# conbi[i]はA_reverse[i]にかけることに対応


ans = 0
# maxを足す
for a, c in zip(A, conbi):
    ans += a * c
    if ans >= MOD:
        ans %= MOD

        # minを引く
for a, c in zip(A[::-1], conbi):
    ans -= a * c
    if ans >= MOD:
        ans %= MOD


print(ans)


### FIXED CODE ###

# https://atcoder.jp/contests/abc151/tasks/abc151_e
# NCK種のすべてのSについてf(S)の合計をもとめる.
# S1,S2...とすると
# sum_i f(Si) = max(S1) + max(S2) ... max(S NCK) - (min(S1) + min(S2) ... min(S NCK))
# となる。
# sum_i max(Si)について考えると、ある要素を固定したときにそれが最大となるような集合を全パターン持ってくれば簡単に計算できる
# 例えば 1 1 3 4 (K=2)で 4が最大となるとり方は3C1(K-1)
# 3が最大となるとり方は(2C1)
# 1が最大となるとり方は(1C1)
# 1が最大となるとり方は(0C1=0)
# 以上によりsum_i max(Si) = 4 * 3C1 + 2*2C1 + 1*1C1 + 1*0C1となる
# 注意としてiC(K-1)をiについてリストにするときいちいちcombination_modを呼び出すとTLEになるので、一気にここを用意する必要がある。
# 具体的には(K-1)!の逆元を計算を計算しておいて
# 分子についてはかけて割って調節すれば良い？


MOD = 10**9 + 7


def combination_mod(n, r, mod):
    if r > n or n == 0:
        return 0  # このような通りの数は無いため便宜上こう定義する
    r = min(r, n - r)
    nf = rf = 1
    for i in range(r):
        nf = nf * (n - i) % mod
        rf = rf * (i + 1) % mod
    return nf * pow(rf, mod - 2, mod) % mod


import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


N, K = read_ints()
A = read_ints()
A.sort()


# 通りの数を先に計算しておく
k = K - 1
k_fact = 1
for i in range(k):
    k_fact = k_fact * (i + 1) % MOD
k_fact_inv = pow(k_fact, MOD - 2, MOD)
conbi = [0]
correct = []
tmp = 1
for i in range(1, N):
    if i < k:
        conbi.append(0)
        tmp *= i
        if tmp >= MOD:
            tmp %= MOD
    else:
        tmp *= i
        tmp %= MOD
        conbi.append((tmp % MOD) * k_fact_inv)
        tmp *= pow(i - k + 1, MOD - 2, MOD)  # 逆元をかけて割ったことにする。
        # tmp //= (i - k + 1)
    # correct.append(combination_mod(i, k, MOD)) #確認用
# conbi[i]はA_reverse[i]にかけることに対応

# print(conbi)
# print(correct)

ans = 0
# maxを足す
for a, c in zip(A, conbi):
    ans += a * c
    if ans >= MOD:
        ans %= MOD

        # minを引く
for a, c in zip(A[::-1], conbi):
    ans -= a * c
    if ans >= MOD:
        ans %= MOD


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

N, M, L = map(int, input().split())
INF = float('inf')

dist = [[INF] * N for _ in range(N)]

for _ in range(M):
    fr, to, cost = map(int, input().split())
    fr -= 1
    to -= 1
    dist[fr][to] = cost
    dist[to][fr] = cost

for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

fuel = [[INF] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if dist[i][j] <= L:
            fuel[i][j] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            fuel[i][j] = min(fuel[i][j], fuel[i][k] + fuel[k][j])

Q = int(input())
ans = []
for _ in range(Q):
    start, end = map(int, input().split())
    start -= 1
    end -= 1

    ans.append(fuel[start][end] - 1 if fuel[start][end] != INF else -1)

print(*ans, sep='\n')


### FIXED CODE ###

import sys
input = sys.stdin.readline
INF = float('inf')

N, M, L = map(int, input().split())
ABC = [tuple(map(int, input().split())) for _ in range(M)]
Q = int(input())
ST = [tuple(map(int, input().split())) for _ in range(Q)]

dist = [[INF] * N for _ in range(N)]
fuel = [[INF] * N for _ in range(N)]

for i in range(N):
    dist[i][i] = 0
    fuel[i][i] = 0

for fr, to, cost in ABC:
    if cost > L:
        continue
    fr -= 1
    to -= 1
    dist[fr][to] = cost
    dist[to][fr] = cost

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = dist[i][k] + dist[k][j]
            if dist[i][j] > d:
                dist[i][j] = d
            if d <= L:
                fuel[i][j] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = fuel[i][k] + fuel[k][j]
            if fuel[i][j] > d:
                fuel[i][j] = d

for start, end in ST:
    print(fuel[start - 1][end - 1] - 1 if fuel[start - 1][end - 1] != INF else -1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
MOD = 10 ** 9 + 7

dp = [0] * (n + 1)
dp[0] = 1
if 1 in a:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2, n + 1):
    if i not in a:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD

print(dp[-1])

### FIXED CODE ###

n, m = map(int, input().split())
a = [0] * (n + 1)
for _ in range(m):
    a[int(input())] = True
MOD = 10 ** 9 + 7

dp = [0] * (n + 1)
dp[0] = 1
if not a[1]:
    dp[1] = 1

for i in range(2, n + 1):
    if not a[i]:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD

print(dp[-1])