Harryxun/stf_run huggingface dataset:
import math
import fractions
import sys
import itertools
import numpy as np
#入力:N(int:整数)
def input1():
	return int(input())

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))


N=input1()
A=np.array(input_array())
mod=10**9-7
s=0

for i in range(60):
	c1=np.count_nonzero(A & 1)
	s+=2**i*c1*(n-c1)
	A = A >> 1

print(s % mod













### FIXED CODE ###

import numpy as np

n = int(input())
arr = np.array([int(i) for i in input().split()])
mod = 10 ** 9 + 7
s = 0

for i in range(60):
    c1 = np.count_nonzero(arr & 1) # 自分がnp.sumを利用したがどうしても正解になれなかった。なぜ？
    s += 2 ** i * c1 * (n - c1)
    arr >>= 1

print(s % mod)
a = int(input())
b = int(input())
mul = a*b
print(mul)

### FIXED CODE ###

a, b = map(int,input().split())
mul = a*b
print(mul)
a,b,h=map(int,inpuut().split())
print((a+b)*h/2)

### FIXED CODE ###

a=int(input())
b=int(input())
h=int(input())
print((a+b)*h//2)
import sys
sys.setrecursionlimit(100001)

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
visited = [False] * n
for _ in range(m):
    a, b = map(int, input().split())
    la = len(edges[a - 1])
    lb = len(edges[b - 1])
    edges[a - 1].append([b - 1, lb])
    edges[b - 1].append([a - 1, la])

def dfs(p, v):
    visited[v] = True
    for (i, r) in edges[v]:
        if not visited[i] and r != -1 and i != p:
            dfs(v, i)
    odd = False
    pr = -1
    for (i, r) in edges[v]:
        if i != p:
            if r != -1:
                edges[i][r][1] = -1
                odd = not odd
        else:
            pr = r
    if odd:
        edges[p][pr][1] = -1

if m % 2 == 1:
    print(-1)
else:
    dfs(-1, 0)
    for v in range(n):
        for (i, r) in edges[v]:
            if r >= 0:
                print(v + 1, i + 1)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
def doit(a):
    c = {}
    for ai in a:
        c[ai] = c.get(ai, 0) + 1
    if len(c) > 3:
        return "No"
    k = list(sorted(c.keys()))
    if len(k) == 1:
        if k[0] == 0:
            return "Yes"
    if len(k) == 2:
        if k[0] == 0 and c[k[0]] * 2 == c[k[1]]:
            return "Yes"
    if len(k) == 3:
        if c[k[0]] == c[k[1]] == c[k[2]] and k[0] ^ k[1] == k[2]:
            return "Yes"
    return "No"

print(doit(sorted(a)))
import math
 
N,D = map(int, input().split())
count = 0
for i in range(0, N):
  x[i] = list(int(input()))
  if D >= math.sqrt(x[i][0]**2 + x[i][1]**2):
    count = count + 1
 
print(count)

### FIXED CODE ###

import math
 
N,D = map(int, input().split())
count = 0
for i in range(0, N):
  x = list(map(int, input().split()))
  if D >= math.sqrt(x[0]**2 + x[1]**2):
    count = count + 1
 
print(count)
n, m = [int(x) for x in input().strip().split()]
a= n, m = [int(x) for x in input().strip().split()]

a.sort(reverse=True)
s = sum(a)
thresh = s/(4*m)
flag=True
for i in range(m):
    if a[i]< thresh:
        flag=False
        break

if flag:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

n, m = [int(x) for x in input().strip().split()]
a = [int(x) for x in input().strip().split()]

a.sort(reverse=True)
s = sum(a)
thresh = s/(4*m)
flag=True
for i in range(m):
    if a[i]< thresh:
        flag=False
        break

if flag:
    print("Yes")
else:
    print("No")
a,b,x=map(int,input().split())
import math
rec=a*a*b/2
if x<=rec:
    c=x*2/a/b

    print(math.degrees(math.atan(b/c)))
else:
    x=a*a*b-x
    c=x*2/a/b
    print(90-math.degrees(math.atan(b/c)))


### FIXED CODE ###

a,b,x=map(int,input().split())
import math
rec=a*a*b/2
if x==a*a*b:
    print(0)
    exit()
if x<=rec:
    c=x*2/a/b

    print(math.degrees(math.atan(b/c)))
else:
    x=a*a*b-x
    c=x*2/a/a
    print(90-math.degrees(math.atan(a/c)))
import math as mt
A,B,N = map(int,input().split())
print(math.floor((A*N)/B)-A*math.floor(N/B))

### FIXED CODE ###

import math
A,B,N = map(int,input().split())
if B-1>N:
    print(math.floor((A*N)/B)-A*math.floor(N/B))
else:
    print(math.floor((A*(B-1))/B)-A*math.floor((B-1)/B))
import sys; sys.stdin = open('input.txt')

n = int(raw_input())

a = raw_input()
b = raw_input()

res = n

for i in xrange(n):
    if a.endswith(b[:n-i]):
        break
    res += 1

print res

### FIXED CODE ###

# import sys; sys.stdin = open('input.txt')

n = int(raw_input())

a = raw_input()
b = raw_input()

res = n

for i in xrange(n):
    if a.endswith(b[:n-i]):
        break
    res += 1

print res
import sys
input = sys.stdin.readline

n = int(input())
xy = [[[] for _ in range(10**5+1)] for __ in range(2)]

for _ in range(n):
    x,y = map(int,input().split())
    xy[0][x].append(y)
    xy[1][y].append(x)

ans = 0
used = [[False for _ in range(10**5+1)] for __ in range(2)]

def dfs(i,flag):
    for v in xy[flag][i]:
        if not used[1-flag][v]:
            used[1-flag][v] = True
            dfs(v,1-flag)
            count[1-flag] += 1

for i in range(10**5+1):
    if xy[0][i] and not used[0][i]:
        used[0][i] = True
        count = [1,0]
        dfs(i,0)
        ans += count[0]*count[1]

ans -= n
print(ans)

### FIXED CODE ###

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

n = int(input())
xy = [[[] for _ in range(10**5+1)] for __ in range(2)]

for _ in range(n):
    x,y = map(int,input().split())
    xy[0][x].append(y)
    xy[1][y].append(x)

ans = 0
used = [[False for _ in range(10**5+1)] for __ in range(2)]

def dfs(i,flag):
    for v in xy[flag][i]:
        if not used[1-flag][v]:
            used[1-flag][v] = True
            dfs(v,1-flag)
            count[1-flag] += 1

for i in range(10**5+1):
    if xy[0][i] and not used[0][i]:
        used[0][i] = True
        count = [1,0]
        dfs(i,0)
        ans += count[0]*count[1]

ans -= n
print(ans)
import math

N, M = map(int, input().split())
N, M = max(N,M), min(N,M)
MOd = 10**9+7

if N == M:
    ans = math.factorial(N) ** 2 * 2
elif N - M == 1:
    ans = math.factorial(M) ** 2 * N
else:
    ans = 0

print(ans // MOD)

### FIXED CODE ###

import math

N, M = map(int, input().split())
N, M = max(N,M), min(N,M)
MOD = 10**9+7

if N == M:
    ans = math.factorial(N) ** 2 * 2
elif N - M == 1:
    ans = math.factorial(M) ** 2 * N
else:
    ans = 0

print(ans % MOD)
S= int(input())
A=S.count('+')
B=S.count('-')
print(A-B)

### FIXED CODE ###

S= input()
A=S.count('+')
B=S.count('-')
print(A-B)
N = int(input())
A = list(map(int,input().split()))
import collections

c = collections.Counter(A)
keys = c.keys()
ans_dict = {}
ans_dict2 = {}
for key in keys:
    ans_dict[key] = cmb(c[key]-1,2)
    ans_dict2[key] = cmb(c[key],2)

SUM  = sum(ans_dict2.values())

# print(ans_dict)
# print(ans_dict2)

for key in A:
    print(SUM-ans_dict2[key]+ans_dict[key])

### FIXED CODE ###

def cmb(n, r):
    if r > n: return 0
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

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

c = collections.Counter(A)
keys = c.keys()
ans_dict = {}
ans_dict2 = {}
for key in keys:
    ans_dict[key] = cmb(c[key]-1,2)
    ans_dict2[key] = cmb(c[key],2)

SUM  = sum(ans_dict2.values())

# print(ans_dict)
# print(ans_dict2)

for key in A:
    print(SUM-ans_dict2[key]+ans_dict[key])
a=input()
b=input()
m=int(a)+int(b)
if m<10
	print(m)
elif 
	print("error")
	

### FIXED CODE ###

# coding: utf-8
a,b=input().split()
m=int(a)+int(b)
if m<10:
  print(int(m))
else:
  print("error")
n=int(input())
money=100
year=0
while(money<n){
  year=year+1
  money=money*1.01
}
print(year)

### FIXED CODE ###

n=int(input())
money=100
year=0
while(money<n):
  year=year+1
  money=int(money*1.01)
print(year)
a = [int(i) for i in input().split()] 
if a[0]*a[1]/2==0:
  print("Even")
 else:
  print("Odd")

### FIXED CODE ###

a, b = map(int, input().split())
print(["Even","Odd"][a*b%2])
s=input()
if s=="A":
  print("T")
eilf s=="T":
  print("A")
eilf s=="C":
  print("G")
eilf s=="G":
  print("C")

### FIXED CODE ###

s=input()
if s=="A":
  print("T")
elif s=="T":
  print("A")
elif s=="C":
  print("G")
elif s=="G":
  print("C")
x,n = map(int,input().split())
a = list(map(int,input().split()))
ans = min(a)-1
for i in range(1,102):
    if i in a:
        continue
    if abs(x-i) < abs(x-ans):
        ans = i
print(ans)

### FIXED CODE ###

x,n = map(int,input().split())
a = list(map(int,input().split()))
if n == 0:
    print(x)
    exit()
ans = min(a)-1
for i in range(1,102):
    if i in a:
        continue
    if abs(x-i) < abs(x-ans):
        ans = i
print(ans)
d = int(input())

if d == 22:
  print("Christmas Eve Eve Eve")
elif d == 23:
  print("Christmas Eve Eve")
elif d == 24:
  print("Christmas Eve")
elif d == 25:
  print("Christmas")
else:
  break


### FIXED CODE ###

d = int(input())
 
if d == 22:
  print("Christmas Eve Eve Eve")
elif d == 23:
  print("Christmas Eve Eve")
elif d == 24:
  print("Christmas Eve")
elif d == 25:
  print("Christmas")
else:
  exit()
S = input()
T = input()
N = len(T)

flag = False
pos = 51
ans = ""
for i in range(len(S)-4):
    cnt = 0
    for j in range(N):
        if S[i+j] == "?" or S[i+j] == T[j]:
            cnt += 1
        else:
            break
    if cnt == N:
        pos = i
        flag = True
if flag:
    for i in range(len(S)):
        if pos <= i and i < pos + N:
            ans += T[i-pos]
        elif S[i] == "?":
            ans += "a"
        else:
            ans += S[i]
else:
    ans = "UNRESTORABLE"
print(ans)

### FIXED CODE ###

S = input()
T = input()
N = len(T)

if len(S) < N:
    print("UNRESTORABLE")
    import sys
    sys.exit()

flag = False
pos = 51
ans = ""
for i in range(len(S)-N+1):
    cnt = 0
    for j in range(N):
        if S[i+j] == "?" or S[i+j] == T[j]:
            cnt += 1
        else:
            break
    if cnt == N:
        pos = i
        flag = True
if flag:
    for i in range(len(S)):
        if pos <= i and i < pos + N:
            ans += T[i-pos]
        elif S[i] == "?":
            ans += "a"
        else:
            ans += S[i]
else:
    ans = "UNRESTORABLE"
print(ans)
input()
nums = list(map(int, input().split()))
 
i = 0
while all(n % 2 == 0 for n in num):
  nums = [n/2 for n in nums]
  i += 1
 
print(i)



### FIXED CODE ###

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

count = 0
while all(n % 2 == 0 for n in Nums):
  Nums = [n/2 for n in Nums]
  count += 1

print(count)
n = int(input())
card = list(map(int,input().split()))

card.sort()

for i in range(n//2):
            ans += card[2*i]-card[2*i+1]
if n%2==1:
            ans += card[-1]

print(ans)

### FIXED CODE ###

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

card.sort(reverse=True)

asum = 0
bsum = 0
for i in range(n):
  if i%2==0:
    asum += card[i]
  else:
    bsum += card[i]

print(asum-bsum)
from heapq import *
def main():
    import numpy as np
    xs,ys,xt,yt=map(int,input().split())
    n=int(input())
    xyr=[[xs,ys,0],[xt,yt,0]]+[list(map(int,input().split())) for _ in [0]*n]
    inf=float('inf')
    g=[[] for _ in [0]*(n+2)]
    for i in range(n+1):
        x1,y1,r1=xyr[i]
        xy1=np.array([x1,y1])
        for j in range(i+1,n+2):
            x2,y2,r2=xyr[j]
            xy2=np.array([x2,y2])
            d_temp=max(0,np.linalg.norm(xy1-xy2)-r1-r2)
            g[i].append([j,d_temp])
            g[j].append([i,d_temp])
    d=[10**10]*(n+2)
    visit=[False]*(n+2)
    visit[0]=True
    h=[]
    for i,j in g[0]:
        h.append([j,i])
    heapify(h)
    while h:
        i,j=heappop(h)
        if visit[j]==True:
            continue
        visit[j]=True
        d[j]=i
        for k,l in g[j]:
            if visit[k]==False:
                heappush(h,[l+i,k])
    print(d[1])
main()

### FIXED CODE ###

def main():
    import heapq
    from sys import stdin
    input=stdin.readline
    xs,ys,xt,yt=map(int,input().split())
    n=int(input())
    xyr=[[xs,ys,0],[xt,yt,0]]+[list(map(int,input().split())) for _ in [0]*n]
    g=[[] for _ in [0]*(n+2)]
    for i in range(n+1):
        x1,y1,r1=xyr[i]
        for j in range(i+1,n+2):
            x2,y2,r2=xyr[j]
            d_temp=max(0,((x1-x2)**2+(y1-y2)**2)**0.5-r1-r2)
            g[i].append((j,d_temp))
            g[j].append((i,d_temp))
    d=[0]*(n+2)
    visit=[False]*(n+2)
    visit[0]=True
    h=[]
    for i,j in g[0]:
        h.append((j,i))
    heapq.heapify(h)
    while h:
        i,j=heapq.heappop(h)
        if visit[j]==True:
            continue
        visit[j]=True
        d[j]=i
        for k,l in g[j]:
            if visit[k]==False:
                heapq.heappush(h,(l+i,k))
    print(d[1])
main()
l = map(int,list(input()))
if(l[0]==l[1]):
  print("YES")
else:
  print("NO")

### FIXED CODE ###

l = input().split()

x = l.count("5")
y = l.count("7")

if(x==2 and y==1):
  print("YES")
else:
  print("NO")
n=int(input())

if n in 9:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

n=input()
if '9' in n:
  print('Yes')
else:
  print('No')
a = int(input())
b = map(int,input().split())
b = list(b)
k = 1
for i in range(a-1):
    maxim = max(a[:i+1])
    if maxim <= a[i+1]:
        k += 1
print(k)

### FIXED CODE ###

a = int(input())
b = map(int,input().split())
b = list(b)
k = 1
for i in range(a-1):
    maxim = max(b[:i+1])
    if maxim <= b[i+1]:
        k += 1
print(k)
NIL = -1


class Node:
    parent = NIL
    left = NIL
    right = NIL
    label = ""


def show_info(u):
    global T, D
    print('node {0}: parent = {1}, depth = {2}, {3}, {4}'.format(u, T[u].parent, D[u], T[u].label, getChildren(u)))


def setLabel(n):
    for i in range(n):
        if T[i].parent == NIL:
            T[i].label = "root"
        elif T[i].left == NIL:
            T[i].label = "leaf"
        else:
            T[i].label = "internal node"


def getChildren(u):
    global T
    c = T[u].left
    R =[]
    while c != NIL:
        R.append(c)
        c = T[c].right
    return R


def setDepth(u,p):
    global T, D
    D[u] = p
    if T[u].right != NIL:
        setDepth(T[u].right, p)
    if T[u].left != NIL:
        setDepth(T[u].left, p + 1)


if __name__ == "__main__":
    n = int(input())
    T = [None] * n
    D = [0] * n
    for i in range(n):
        T[i] = Node()
    for i in range(n):
        tmp = list(map(int, input().split()))
        id = tmp.pop(0)
        k = tmp.pop(0)
        C = tmp
        if k != 0:
            T[id].left = C[0]
            for j in range(len(C)):
                T[C[j]].parent = id
            for j in range(len(C) - 1):
                T[C[j]].right = C[j + 1]
    setLabel(n)
    for i in range(n):
        if T[i].label == "root":
            root = i
    # ??±????¨????
    setDepth(root, 0)
    for i in range(n):
        show_info(i)

### FIXED CODE ###

NIL = -1


class Node:
    parent = NIL
    left = NIL
    right = NIL


def getDepth(u):
    d = 0
    while T[u].parent != NIL:
        u = T[u].parent
        d += 1
    return d


def getChildren(u):
    c = T[u].left
    result = []
    while c != NIL:
        result.append(c)
        c = T[c].right
    return result


n = int(input())
T = [0] * n
for i in range(n):
    T[i] = Node()

for i in range(n):
    tmp = list(map(int, input().split()))
    id = tmp.pop(0)
    k = tmp.pop(0)
    c = tmp
    if k != 0:
        for j in range(len(c)):
            T[c[j]].parent = id
        T[id].left = c[0]
        for j in range(len(c) - 1):
            T[c[j]].right = c[j + 1]

for i in range(n):
    d = getDepth(i)
    c = getChildren(i)
    if d == 0:
        t = 'root'
    elif c == []:
        t = 'leaf'
    else:
        t = 'internal node'
    print('node ', i, ': ', 'parent = ', T[i].parent, ', depth = ', d, ', ', t, ', ', c, sep='')
s =input()
n = len(s)
a = [0]*(n+1)
hidari = [0] *(n+1)
for i in range(1,n+1):
    if s[i-1] == '<':
        res +=1
    else:res = 0
    hidari[i] = res
hidari[-1] = res
res = 0
migi = [0] *(n+1)
for i in range(n-1,-1,-1):
    if s[i] == '>':
        res+=1
    else:res = 0
    migi[i] = res
migi[0] = res
ans = 0
for i in range(n+1):
    ans += max(migi[i],hidari[i])
print(ans)

### FIXED CODE ###

s =input()
n = len(s)
a = [0]*(n+1)
res = 0
hidari = [0] *(n+1)
for i in range(1,n+1):
    if s[i-1] == '<':
        res +=1
    else:res = 0
    hidari[i] = res
hidari[-1] = res
res = 0
migi = [0] *(n+1)
for i in range(n-1,-1,-1):
    if s[i] == '>':
        res+=1
    else:res = 0
    migi[i] = res
migi[0] = res
ans = 0
for i in range(n+1):
    ans += max(migi[i],hidari[i])
print(ans)
N=int(input())
data=list(map(int,input().split()))

for i in range(N):
    mo2=data[i]%2
    mo6=data[i]%6
    mo10=data[i]%10
    if mo2==0:
        if mo6==0 or mo10==0:
            ans="APPROVED"
            continue
        else:
            ans="DENIED"
            break
    else:
        continue
print(ans)

### FIXED CODE ###

N=int(input())
data=list(map(int,input().split()))
ans="APPROVED"
for i in range(N):
    mo2=data[i]%2
    mo6=data[i]%6
    mo10=data[i]%10
    if mo2==0:
        if mo6==0 or mo10==0:
            ans="APPROVED"

        else:
            ans="DENIED"
            break
    else:
        continue
print(ans)
import itertools
N = int(input())
P = list(map(int,input().split()))
Q = list(map(int,input().split()))
num = 0
for v in list(itertools.permutations(range(1,N+1))):
    num += 1
    if list(v) == P:
        A = num
    elif list(v) == Q:
        B = num
    else:
        pass
print(abs(A-B))

### FIXED CODE ###

import itertools
N = int(input())
P = list(map(int,input().split()))
Q = list(map(int,input().split()))
num = 0
for v in list(itertools.permutations(range(1,N+1))):
    num += 1
    if list(v) == P:
        A = num
    elif list(v) == Q:
        B = num
    else:
        pass
try:
    print(abs(A-B))
except:
    print(0)
from math import gcd
n,k=map(int,input().split())
A=list(map(int,input().split()))
ans=""
if max(A)<k:
  ans="IMPOSSIBLE"
elif k in A:
  ans="POSSIBLE"
else:
  g=gcd(A[0], A[1])
  for i in range(2,n):
    g=gcd(g,A[i])
  if g!=0 and k%g==0:
    ans="POSSIBLE"
  else:
    ans="IMPOSSIBLE"
print(ans)

### FIXED CODE ###

from fractions import gcd
n,k=map(int,input().split())
A=list(map(int,input().split()))
ans=""
if max(A)<k:
  ans="IMPOSSIBLE"
elif k in A:
  ans="POSSIBLE"
else:
  g=gcd(A[0], A[1])
  for i in range(2,n):
    g=gcd(g,A[i])
  if g!=0 and k%g==0:
    ans="POSSIBLE"
  else:
    ans="IMPOSSIBLE"
print(ans)
s = input()
a = [i for i in s]
s = sorted(a)
b = 1
for i in range(len(s)-1):
  if s[i] == s[i+1]:
    b = 0
print("yes") if b = 1 else print("no")


  


### FIXED CODE ###

s = input()
a = [i for i in s]
s = sorted(a)
b = 1
for i in range(len(s)-1):
  if s[i] == s[i+1]:
    b = 0
print("yes") if b == 1 else print("no")
import math

a,b = map(int,input().split())

c = math.gcd(a,b)
print(int(a*b/c))

### FIXED CODE ###

aa,bb = map(int,input().split())
a = aa
b = bb
if aa>bb:
    a = bb
    b = aa
rx = a
ry = b

while 1:
    if rx == 0:
        break
    rx2 = ry%rx
    ry = rx
    rx = rx2

print(int(a*b/ry))
n,m = (int(i) for i in input().split())
x = [int(i) for i in input().split()]

if m == 1:
	print(0)
else:
	sorted_x = sorted(x)
 
	diff_x = []
	diff = 0
	result = 0
 
	for i in range(m-1):
		diff = sorted_x[i+1] - sorted_x[i]
		result += diff
		diff_x.append(diff)

	sorted_diff = sorted(diff_x, reverse=True)[:n-1]
 
	for i in range(n-1):
		result -= sorted_diff[i]
 
	print(result)

### FIXED CODE ###

n,m = (int(i) for i in input().split())
x = [int(i) for i in input().split()]

if n >= m:
	print(0)
else:
	sorted_x = sorted(x)
 
	diff_x = []
	diff = 0
	result = 0
 
	for i in range(m-1):
		diff = sorted_x[i+1] - sorted_x[i]
		result += diff
		diff_x.append(diff)

	sorted_diff = sorted(diff_x, reverse=True)[:n-1]
 
	for i in range(n-1):
		result -= sorted_diff[i]
	 
	print(result)
N,X=map(int,input().split())

a,p=[1],[1]

for i in range(N):
    a.append(a[i]*2+3)
    p.append(p[i]*2+1)

def solve(n,x): #n,x
    if n==0:
        if x<=0:
            return 0
        else:
            return 1
    elif x<=1+a[N-1]:
        return  solve(N-1,X-1)
    else:
        return p[N-1]+1+solve(N-1,X-2-a[N-1])

print(solve(N,X))




### FIXED CODE ###

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

a,p=[1],[1]

for i in range(N):
    a.append(a[i]*2+3)
    p.append(p[i]*2+1)

def solve(n,x): #n,x
    if n==0:
        if x<=0:
            return 0
        else:
            return 1
    elif x<=1+a[n-1]:
        return  solve(n-1,x-1)
    else:
        return p[n-1]+1+solve(n-1,x-2-a[n-1])

print(solve(N,X))
S = input()
K = int(input())

count = 0
l = len(S)
check = True
i = 0
while i < l - 1:
    if S[i] == S[i + 1]:
        count += 1
        i += 2
        if i + 1 == l:
            check = False
    else:
        i += 1

ff = 1
while S[ff] == S[0] and ff < l:
    ff += 1
ll = 1
while S[-ll] == S[-1] and ll < l:
    ll += 1

if S[0] == S[-1]:
    if not check:
        print(count * K)
    else:
        print(count + (K - 1) * (ff + ll) // 2)
else:
    print(count * K)


### FIXED CODE ###

S = input()
K = int(input())
SS = S[::-1]

count = 0
l = len(S)
check = True
ff = 1
while ff < l:
    if S[ff] == S[0]:
        ff += 1
    else:
        break
ll = 1
while ll < l:
    if SS[ll] == SS[0]:
        ll += 1
    else:
        break

if S[0] != SS[0]:
    ff = 0
    ll = 0

if ff == l:
    print(l * K // 2)
    exit()

i = ff
c = 1
while i < l - ll - 1:
    if S[i] == S[i + 1]:
        c += 1
    else:
        count += c // 2
        c = 1
    i += 1
count += c // 2

# print(count, ff, ll)

print(K * count + (K - 1) * ((ff + ll) // 2) + ff // 2 + ll // 2)
hoge = list(map(int, input().split()))
ret = sorted(hoge)
print(str(ret[0]+" "+str(ret[1])+" "+str(ret[2]))


### FIXED CODE ###

l = map(int, raw_input().split())
l.sort()
print l[0], l[1], l[2]
n = int(input())
l = [int(v) for v in input().split()]

l = sorted(l)
res = {}
count = 0
for i in range(len(l)-1):
    tmp_l = l
    a = l.pop(i)
    b = l.pop(i+1)
    count += len([1 for v in tmp_l if v > b - a and v < a + b])
    

print(count)


### FIXED CODE ###

import bisect


def triangles():
    n = int(input())
    l = [int(v) for v in input().split()]
    l.sort()

    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            c = l[i] + l[j]
            index = bisect.bisect_left(l, c)
            count += max(index - j - 1, 0)

    print(count)


if __name__ == '__main__':
    triangles()
a,b,c=map(int,input.split())
print(min(b//a,c))

### FIXED CODE ###

a,b,c=map(int,input().split())
print(min(b//a,c))
def _comb(N,M):
    count=1
    for i in range(0,M):
        count*=N-i
    for i in range(1,M+1):
        count/=i
    return(int(count))

N,M=list(map(int,input().split()))
A=[int(input()) for i in range(M)]
A.append(N)
if not 1 in A:
    A.append(0)
    A.sort()
count=1
for m in range(len(A)-1):

    count*=sum([_comb((A[m+1]-1)-A[m]-i,i) for i in range((A[m+1]-1)-A[m])])
    #print(sum([comb((A[m+1]-1)-A[m]-i,i,exact=True) for i in range((A[m+1]-1)-A[m])]),sum([_comb((A[m+1]-1)-A[m]-i,i) for i in range((A[m+1]-1)-A[m])]),count)
print(count%1000000007)


### FIXED CODE ###

N,M=map(int,input().split())
mod=10**9+7
A=set([int(input()) for i in range(M)])

data=[0 for i in range(N)]
if 1 not in A:
    data[0]=1
if N>=2:
    if 2 not in A:
        data[1]=1+data[0]


for i in range(2,N):
    if i+1 not in A:
        data[i]=data[i-1]+data[i-2]
        data[i]%=mod

#print(data)

print(data[-1])