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

n=int(input())
a=list(map(int,input().split()))
s=0
for j in range(len(bin(max(a)))-2):
    cnt1=0
    cnt0=0
    for i in range(n):
      if (a[i]>>j)&1:
        cnt1+=1
      else:
        cnt0+=1
    s+=cnt1*cnt0*2**j
print(s%(10**9+7))


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
mod=10**9+7
for j in range(60):
    cnt1=sum([1 for i in a if i>>j&1])
    cnt0=n-cnt1
    ans+=(cnt1*cnt0*2**j)
print(ans%(10**9+7))
### BUGGY CODE ###

n,p = map(int,input().split())
s = input()[::-1]
res = 0
for start in range(n):
    num = 0
    for i,end in enumerate(range(start,n)):
        num += (int(s[end]) * 10**i)
        num %= p
        if num == 0:
            res += 1
print(res)

### FIXED CODE ###

from collections import defaultdict

n, p = map(int,input().split())
s = input()

res = 0

if p not in [2,5]:
    crem = 0
    
    crem_10 = [1]
    for i in range(1,n):
        crem_10 += [(crem_10[-1] * (10%p)) % p]
        
    dic_p = defaultdict(lambda : 0)
    for i,subs in enumerate(s[::-1]):
        crem += (int(subs) % p * crem_10[i]) % p
        crem %= p

        if crem == 0:
            res += 1
        res += dic_p[crem]

        dic_p[crem] += 1
        
else:
    for i,subs in enumerate(s[::-1]):
        if int(subs) % p == 0:
            res += n - i
    
print(res)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import itertools


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # Failed to predict input format
    N, M, X = [int(x) for x in input().split()]
    C = []
    A = []
    for i in range(N):
        tmp = [int(x) for x in input().split()]
        C.append(tmp[0])
        A.append(tmp[1:])
    CA = [[C[i], v] for i, v in enumerate(A)]
    l = list(itertools.permutations(CA, N))
    anss = [100100100] * len(l)
    for i, v in enumerate(l):
        arr = [0] * M
        s = 0
        for j in v:
            arr = python_list_add(arr, j[1])
            s += j[0]
            if all([x >= X for x in arr]):
                anss[i] = s
                break
    ans = min(anss)
    if ans == 100100100:
        print(-1)
        return
    print(ans)
    return


def python_list_add(in1, in2):
    return [a + b for a, b in zip(in1, in2)]





    
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import itertools


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N, M, X = [int(x) for x in input().split()]
    C = []
    A = []
    for i in range(N):
        tmp = [int(x) for x in input().split()]
        C.append(tmp[0])
        A.append(tmp[1:])
    CA = [[C[i], v] for i, v in enumerate(A)]

    # TLE
    # l = list(itertools.permutations(CA, N))
    # anss = [100100100] * len(l)
    # for i, v in enumerate(l):
    #     arr = [0] * M
    #     s = 0
    #     for j in v:
    #         arr = python_list_add(arr, j[1])
    #         s += j[0]
    #         if all([x >= X for x in arr]):
    #             anss[i] = s
    #             break
    # ans = min(anss)
    # if ans == 100100100:
    #     print(-1)
    #     return
    # print(ans)

    # bit全探索
    anss = []
    for i in range(2 ** N):
        s = 0
        arr = [0] * M
        for j in range(N):
            if i >> j & 1:
                s += CA[j][0]
                arr = python_list_add(arr, CA[j][1])
            if all([x >= X for x in arr]):
                anss.append(s)
    print(min(anss) if anss else -1)

    return


def python_list_add(in1, in2):
    return [a + b for a, b in zip(in1, in2)]


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

s=input()
b=0
m=len(s)
for i in range(m-3):
    a=s[i]+s[i+1]+s[i+2]
    
    for j in range(i+3,m):

        a=a+s[j]
        a=int(a)

        if a%2019==0:
            b+=1
        a=str(a)
print(b)


### FIXED CODE ###

s=input()
b=0
m=len(s)
c=[0 for i in range(2019)]
c[0]=c[0]+1
a=""
e=0
f=1
s= ''.join(list(reversed(s)))
for i in s:
    e+=int(i)*f
    g=e%2019
    c[g]+=1
    f*=10
    f%=2019
e = sum(i * (i - 1) // 2 for i in c)
print(e)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)


k = int(input())

x = 0

for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            x += gcd(a, b, c)

print(x)

### FIXED CODE ###

from math import gcd


k = int(input())

ans = 0

gcd_sum = [0] * 201

for i in range(1, k+1):
    for j in range(1, k+1):
        gcd_sum[i] += gcd(i, j)

for a in range(1, k+1):
    for b in range(1, k+1):
        q = gcd(a, b)
        ans += gcd_sum[q]

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

n = int(input())
a = list(map(int, input().split()))
for i in range(1, n+1):
    print(a[i-1:].count(i))

### FIXED CODE ###

from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
d = defaultdict(int)
for i in a:
    d[i] += 1
for j in range(1, n+1):
    print(d.get(j, 0))
### BUGGY CODE ###

import numpy as np
A = 'Yes'
N = int(input())
t = np.array([[0,0,0]])
for n in range(N):
     a = [[int(i) for i in input().split()]]
     t = np.append(t, np.array(a), axis=0)
     diff = t[n+1] -t[n]
     cond = np.abs(diff[1]) + np.abs(diff[2])
     if cond > diff[0]:
        A='No'
        break
     if np.sum(t[n+1]) % 2 ==1:
        A = 'No'
        break
print(A)

### FIXED CODE ###

N = int(input())
t_list = [0]
x_list = [0]
y_list = [0]
A = 'Yes'
for i in range(N):
    ti, xi, yi = map(int, input().split())
    t_list.append(ti)
    x_list.append(xi)
    y_list.append(yi)
    if ((abs(x_list[i+1] - x_list[i]) + abs(y_list[i+1] - y_list[i]) > (t_list[i+1] - t_list[i]))):
        A = 'No'
        break
    if (x_list[i+1] + y_list[i+1] - t_list[i+1])%2 != 0:
        A = 'No'
        break
print(A)
### BUGGY CODE ###

prime = []
def isPrime(n):
    if n == 1:
        return False
    if n in prime:
        return True
    k = 2
    while k*k <= n:
        if n%k==0:
            return False
        k += 1
    prime.append(n)
    return True

Q = int(input())
L = [0]*Q
R = [0]*Q
cnt = 0
for i in range(Q):
    l, r = map(int,input().split())
    j = l
    while l <= j and j <= r:
        if isPrime(j) and isPrime((j+1)//2):
            cnt += 1
        j += 1
    print(cnt)
    cnt = 0


### FIXED CODE ###

#Pはiが素数かどうかを表すlist
#素数でないと判明したらFalseに書き換える
P = [True]*100001
for i in range(2,100001):#2から始める
    if P[i]:
        for j in range(i+i,100000,i): #stepはi
            P[j] = False

#2017に似た数の個数をあらかじめ求める
#C[i]はi以下の2017に似た数の個数
C = [0 for _ in range(100002)]
#まずC[i]にiと(i+1)/2が2017likeであれば1を格納
for i in range(3,100000,2):
    if P[i] and P[(i+1)//2]:
        C[i] += 1
#C[i]はi<以下>の2017likeな数の個数なので，
#下から個数を足していく（累積和という）
for i in range(3,100000):
    C[i+1] += C[i]
Q = int(input())
for i in range(Q):
    l,r = map(int,input().split())
    print(C[r]-C[l-1])
### BUGGY CODE ###

import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


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

    N, K = il()
    A = il()

    ret = [1] * N
    ret[0] = A[0]
    for n in range(1, N):
        ret[n] *= A[n] * ret[n - 1]
        if n >= K:
            ret[n] //= A[n - K]

    for k in range(K, N):
        if ret[k - 1] < ret[k]:
            print('Yes')
        else:
            print('No')


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


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

    N, K = il()
    A = il()

    for k in range(K, N):
        if A[k - K] < A[k]:
            print('Yes')
        else:
            print('No')


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


N,M=map(int,input().split())
LR=[list(map(int,input().split())) for _ in range(M)]
cnt=0
for i in range(1,N+1):
    for l,r in LR:
        if i<l or r<i:
            break
    else:
        cnt+=1
print(cnt)

### FIXED CODE ###

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

mm=0
mx=10**5
for _ in range(M):
    l,r = map(int,input().split())
    mm = max(mm,l)
    mx= min(mx,r)
print(max(mx-mm+1,0))
### BUGGY CODE ###

import math
from sys import stdin,stdout
#% 998244353
from heapq import heapify,heappop,heappush
import collections

n,k=list(map(int,stdin.readline().split()))
a=list(map(int,stdin.readline().split()))


for i in range(min(k,100)):
    #nw=[0]*n
    pr=[0]*n
    for x,d in enumerate(a):
        if d==0:
            pr[x]+=1
            if x!=n-1:
                pr[x+1]-=1
            continue
        l=math.floor(x-d)
        r=math.floor(x+d)
        l=max(0,l)
        r=min(n-1,r)
        pr[l]+=1
        if r!=n-1:
            pr[r+1]-=1
    
    for m in range(1,n):
        pr[m]+=pr[m-1]
    
    a[:]=pr


        

for i in a:
    print(i,end=" ")

### FIXED CODE ###

import math
from sys import stdin,stdout
#% 998244353
from heapq import heapify,heappop,heappush
import collections

n,k=list(map(int,stdin.readline().split()))
a=list(map(int,stdin.readline().split()))


for i in range(min(k,100)):
    #nw=[0]*n
    pr=[0]*n
    for x,d in enumerate(a):
        if d==0:
            pr[x]+=1
            if x!=n-1:
                pr[x+1]-=1
            continue
        l=math.floor(x-d)
        r=math.floor(x+d)
        l=max(0,l)
        r=min(n-1,r)
        pr[l]+=1
        if r!=n-1:
            pr[r+1]-=1
    
    for m in range(1,n):
        pr[m]+=pr[m-1]
    
    a[:]=pr


        

for i in a:
    print(i,end=" ")
### BUGGY CODE ###

n,m=map(int, input().split())
p=[]
y=[]
for i in range(m):
    a,b=map(int, input().split())
    p.append(a)
    y.append(b)

prefecture=[]
for j in range(n):
    city=[] # number
    for i in range(m):
        if(p[i]==j+1):
            city.append(y[i])
    city.sort()
    prefecture.append(city)

for i in range(m):
    print('{0:06d}{1:06d}'.format(p[i],prefecture[p[i]-1].index(y[i])+1))

### FIXED CODE ###

n,m=map(int, input().split())
prefecture=[]
for i in range(m):
    pk,yk=map(int, input().split())
    prefecture.append([pk,yk,i])

prefecture.sort(key=lambda x:(x[0],x[1])) # x[0]:pで整理したうえでx[1]:yで整理
p_num=prefecture[0][0]
city_num=1
for i in range(m):
    if(prefecture[i][0]!=p_num):
        p_num=prefecture[i][0]
        city_num=1

    prefecture[i].append(city_num)
    city_num+=1

prefecture.sort(key=lambda x:x[2])

for i in range(m):
    print('{0:06d}{1:06d}'.format(prefecture[i][0], prefecture[i][3]))
### BUGGY CODE ###

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

for i in range(N):
    if A[i] == 0:
        ans = 0
        break
    else:
        ans *= A[i]

if ans <= 10 ** 18:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

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

if 0 in A:
    ans = 0
else:
    for i in range(N):
        ans *= A[i]
        if ans > 10 ** 18:
            ans = -1
            break

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

def diffarray(arr):
    sum = 0
    tmp = arr[0]
    for digit in arr[1:]:
        sum += abs(tmp - digit)
        tmp = digit
    return sum

def neighbor_diff(i, arr):
    if i == 0:
        return abs(arr[i] - arr[i+1])
    if i == len(arr) - 1:
        return abs(arr[i-1] - arr[i])
    else:
        return abs(arr[i-1] - arr[i]) + abs(arr[i] - arr[i+1])

def swap_arr(arr, i, j):
    tmp_i = arr[i]
    arr[i] = arr[j]
    arr[j] = tmp_i
    return


def search_diff(i,j,arr):
    '''
    数列arrのi番目とj番目をスワップさせた場合の差の総量の変化
    :return: 変化量
    '''
    tmp = - neighbor_diff(i, arr) - neighbor_diff(j, arr)

    swapped_arr = arr[:]
    swap_arr(swapped_arr, i, j)

    tmp += neighbor_diff(i, swapped_arr) + neighbor_diff(j, swapped_arr)
    return tmp

def change(arr):
    '''

    :param arr: 検証元の数列
    :return: 検証した結果見つかった最も差が大きい数列
    '''
    ret_arr = arr[:]

    for i in range(0, len(arr)):
        for j in range(i, len(arr)):
            henka = search_diff(i, j, arr)
            if henka > 0:
                swap_arr(arr,i,j)
            #print(i,j,henka,max,arr,swapped_arr)
    return True

def main():
    N = int(input())
    arr=[]
    for i in range(N):
        arr.append(int(input()))
    arr.sort()

    mid, mod = divmod(N, 2)

    start_arr = []
    for i in range(mid):
        start_arr.append(arr[i])
        start_arr.append(arr[-i-1])
    if mod == 1:
        start_arr.append(arr[mid])

    assert(len(arr) == len(start_arr))
    while True:
        nochange = change(start_arr)
        if nochange:
            break

    #print(start_arr,diffarray(start_arr[1:-1]))
    print(diffarray(start_arr))
    return


main()

### FIXED CODE ###

def main():
    N = int(input())
    array = [int(input()) for _ in range(N)]
    array.sort()

    div, mod = divmod(N, 2)
    if mod == 0:
        fore, last_in_fore, first_in_rear, rear = array[:div-1], array[div-1], array[div], array[div+1:]

        a = 2 * sum(rear) + first_in_rear - last_in_fore - 2 * sum(fore)
        print(a)
        return
    else:
        #mode1 (mrfrm):(1,2,-2,2,1)
        array1=array[:]
        fore1=[]
        rear1=[]
        while True:
            fore1.append(array1.pop(0))
            if len(array1) <= 2:
                break
            rear1.append(array1.pop(-1))
        mid1 = array1
        a1 = 2 * sum(rear1) + sum(mid1) - 2 * sum(fore1)

        #mode2 (mfrfm):(1,-2,2,-2,1)
        array2 = array[:]
        fore2=[]
        rear2=[]
        while True:
            rear2.append(array2.pop(-1))
            if len(array2) <= 2:
                break
            fore2.append(array2.pop(0))
        mid2 = array2
        a2 = 2 * sum(rear2) - sum(mid2) - 2 * sum(fore2)

        print(max(a1, a2))
        return
    return


main()
### BUGGY CODE ###

N = int(input())
H=[int(x) for x in input().split()]

ans='Yes'
for n in range(N-1,0,-1):
    num=H[n]
    check=max(set(H[:n]))
    if check > num+1:
        ans='No'
print(ans)

### FIXED CODE ###

N=int(input())
H=[int(x) for x in input().split()]

max_h=0
ans='Yes'

for n in range(N):
    if H[n] > max_h:
        max_h = H[n]
        
    if H[n] < max_h-1:
        ans='No'
        
print(ans)
### BUGGY CODE ###

import numpy as np
n, k = map(int, input().split())
p = np.array(list(map(int, input().split())))
p += 1
ans = np.zeros(n-k+1)
for i in range(k):
    ans += p[i:n-k+1+i]
print(max(ans)/2)

### FIXED CODE ###

import numpy as np
n, k = map(int, input().split())
p = np.array(list(map(int, input().split())))
p += 1
sum_E = np.cumsum(p)
sum_e = np.append([0], sum_E)
ans = -1
for i in range(n-k+1):
    ans = max(ans, sum_e[i+k] - sum_e[i])
print(ans/2)
### BUGGY CODE ###

x = int(input())
d = 0
ans = 0
while d < x:
  d += d//100
  ans += 1
print(ans)

### FIXED CODE ###

def main():
    ans = 0
    m = 100
    x = int(input())
    while m < x:
        m += m//100
        ans += 1 
    
    print(ans)

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

n,k,q = map(int,input().split())
point = [k for i in range(n)]

for _ in range(q):
  ans = int(input())
  for i in range(n):
    if ans - 1 != i:
      point[i]-=1

for i in range(n):
  if point[i] > 0:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

n,k,q = map(int,input().split())
point = [0 for i in range(n)]

for _ in range(q):
  ans = int(input())
  point[ans-1] += 1
  
for i in range(n):
  if k + point[i] - q > 0:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

n,k,q=map(int,input().split())

A=[k]*n
for i in range(q):
    a=int(input())
    for j in range(n):
        if j!=a:
            A[j-1]-=1

for i in range(n):
    if A[i]<=0:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

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

A=[m-q]*n
for i in range(q):
    a=int(input())
    A[a-1]+=1

for i in range(n):
    if A[i]<=0:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

[N, M] = list(map(int, input().split(' ')))
card_list = list(map(int, input().split(' ')))

card_list.sort()

for i in range(M):
  [B, C] = list(map(int, input().split(' ')))
  for k in range(B):
    if (card_list[k] < C):
      card_list[k] = C
    else:
      break
  card_list.sort()
  
print(sum(card_list))

### FIXED CODE ###

[N, M] = list(map(int, input().split(' ')))
card_list = list(map(int, input().split(' ')))

card_list.sort()
compare_list = []

for i in range(M):
  (B, C) = list(map(int, input().split(' ')))
  compare_list.append((C,B))
    
compare_list.sort()

ans = 0
for i in range(N):
  if compare_list == []:
    ans += sum(card_list[i:])
    break
  if card_list[-1] > compare_list[-1][0]:
    ans += card_list.pop()
  elif compare_list[-1][1] > 0:
    ans += compare_list[-1][0]
    tmp = compare_list.pop()
    a = tmp[0]
    b = tmp[1]
    if b != 1:
      compare_list.append((a,b-1)) 
      
print(ans)
### BUGGY CODE ###

import re
N, Q = map(int, input().split())
S = input()
S_lr = []
lr = []
for i in range(Q):
    k = map(int, input().split())
    lr.append(k)

for i in range(Q):
    l, r = lr[i]
    s = S[l-1:r]
    print(len(re.findall('AC', s)))



### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
	t[i+1] = t[i] + (1 if S[i:i+2] == 'AC' else 0)

for i in range(Q):
	l, r = map(int, input().split())
	print(t[r-1] - t[l-1])
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

n = int(input())

answer = 0

for i in range(1,n+1):
  
  for j in range(1,n+1):
    
    for h in range(1,n+1):
      f = gcd(i,j,h)
      answer += f
      
print(answer)


### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

n = int(input())

answer = 0.0

for i in range(1,n+1):
  
  for j in range(1,n+1):
    
    for h in range(1,n+1):
      f = gcd(i,j,h)
      answer += f
      
print(int(answer))
### BUGGY CODE ###

import numpy as np

N = int(input())

N_list = np.array(range(N))

N_np   = np.sum(N_list)

print(int(N_np))

### FIXED CODE ###

N = int(input())

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

import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    h = [int(input()) for i in range(N)]
    H = sorted(h)
    ans = 10**9 +1
    for i in range(N-K+1):
        high = max(H[i:i+K]) - min(H[i:i+K])
        ans = min(ans, high)
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    h = [int(input()) for i in range(N)]
    H = sorted(h)

    ans = 10**9 +1
    for i in range(N-K+1):
        high = H[i+K-1] - H[i] 
        ans = min(ans, high)
    print(ans)

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

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

if n == 1:
  print(1)
else:
  ans = a.count(0) + a.count(1)
  for x in range(1, max(a)):
    res = a.count(x) + a.count(x+1) + a.count(x-1)
    ans = max(ans, res)
    
  print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
ans = 0
for x in range(min(a), max(a)+1):
  res = c[x] + c[x+1] + c[x-1]
  ans = max(ans, res)
print(ans)
### BUGGY CODE ###

n,m=map(int, input().split())
a = []
for i in range(m):
    a.append(int(input()))

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 in a):
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]

print(dp[n]%(10**9+7))

### FIXED CODE ###

N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])
INF = 1000000007

dp = [0] * (N + 1)
dp[0] = 1
if 1 not in a:
	dp[1] = 1
else:
	dp[1] = 0
for i in range(2, N + 1):
	if i in a:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= INF

print(dp[N])
### BUGGY CODE ###

import sys
from collections import defaultdict

h,w,m = map(int, sys.stdin.readline().split())
targets = [tuple(map(lambda x: int(x)-1, sys.stdin.readline().split())) for _ in range(m)]

num_in_h = defaultdict(int)
num_in_w = defaultdict(int)
for t in targets:
    num_in_h[t[0]] += 1
    num_in_w[t[1]] += 1

max_h_list = [kv[0] for kv in num_in_h.items() if kv[1] == max(num_in_h.values())]
max_w_list = [kv[0] for kv in num_in_w.items() if kv[1] == max(num_in_w.values())]
ans = max(num_in_h.values()) + max(num_in_w.values())

point = 0
comb = len(max_h_list) * len(max_w_list)
targets = set(targets)
for t in targets:
    if t[0] in max_h_list and t[1] in max_w_list:
        point += 1 # 爆破地点に爆破対象あり

print(ans if comb != point else ans-1)


### FIXED CODE ###

import sys

h,w,m = map(int, sys.stdin.readline().split())
num_in_h = [0] * h
num_in_w = [0] * w
targets = set()
for _ in range(m):
    t_h, t_w = map(lambda x: int(x)-1, sys.stdin.readline().split())
    num_in_h[t_h] += 1
    num_in_w[t_w] += 1
    targets.add((t_h, t_w))

max_h = max(num_in_h)
max_w = max(num_in_w)
max_h_set = set([i for i, v in enumerate(num_in_h) if v == max_h])
max_w_set = set([i for i, v in enumerate(num_in_w) if v == max_w])
ans = max_h + max_w - 1

flag = False
for i in max_h_set:
    for j in max_w_set:
        if (i, j) not in targets:
            flag = True
            break
    if flag: break

print(ans+1 if flag else ans)
### BUGGY CODE ###

def warshall_floyd(edge):
  e=edge
  for k in range(len(e)):
    for i in range(len(e)):
      for j in range(len(e)):e[i][j]=min(e[i][j],e[i][k]+e[k][j])
  return e
n,m,l=map(int,input().split())
edge=[n*[10**10]for _ in range(n)]
for i in range(n):edge[i][i]=0
for _ in range(m):
  a,b,c=map(int,input().split())
  a-=1;b-=1
  edge[a][b]=edge[b][a]=c
edge=warshall_floyd(edge)
edgee=[n*[10**10]for _ in range(n)]
for i in range(n):
  edgee[i][i]=0
  for j in range(n):
    if edge[i][j]<=l:edgee[i][j]=1
edgee=warshall_floyd(edgee)
q=int(input())
for _ in range(q):
  s,t=map(int,input().split())
  s-=1;t-=1
  ans=edgee[s][t]
  if ans==10**10:print(-1)
  else:print(ans-1)

### FIXED CODE ###

def warshall_floyd(edge):
  e=edge
  for k in range(len(e)):
    for i in range(len(e)):
      for j in range(len(e)):e[i][j]=min(e[i][j],e[i][k]+e[k][j])
  return e
n,m,l=map(int,input().split())
edge=[n*[10**10]for _ in range(n)]
for i in range(n):edge[i][i]=0
for _ in range(m):
  a,b,c=map(int,input().split())
  a-=1;b-=1
  edge[a][b]=edge[b][a]=c
edge=warshall_floyd(edge)
edgee=[n*[10**10]for _ in range(n)]
for i in range(n):
  edgee[i][i]=0
  for j in range(n):
    if edge[i][j]<=l:edgee[i][j]=1
edgee=warshall_floyd(edgee)
q=int(input())
for _ in range(q):
  s,t=map(int,input().split())
  s-=1;t-=1
  ans=edgee[s][t]
  if ans==10**10:print(-1)
  else:print(ans-1)