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

import sys
input = sys.stdin.readline

k = int(input())

if k%2 == 0:
    print(-1)
    exit()

if k == 7:
    print(1)
    exit()

if k == 1:
    print(1)
    exit()

seven = 7
d = 1
while seven != 0:
    seven += pow(7*pow(10,d,k),1,k)
    seven = pow(seven,1,k)
    d += 1

print(d)




### FIXED CODE ###

import sys
input = sys.stdin.readline

k = int(input())

if k%2 == 0:
    print(-1)
    exit()

if k == 7:
    print(1)
    exit()

if k == 1:
    print(1)
    exit()

if k % 5 == 0:
    print(-1)
    exit()

seven = 7
d = 1
while seven != 0:
    seven += pow(7*pow(10,d,k),1,k)
    seven = pow(seven,1,k)
    d += 1

print(d)
### BUGGY CODE ###

from collections import deque

h,w=map(int,input().split())
maplis=[input() for i in range(h)]

que=deque([(0,0,1)])
used={(0,0)}
bcount =sum(s.count("#") for s in maplis)


def check(x,y,c):
    if x<0 or x>w-1 or y<0 or y>h-1:
        return
    if maplis[y][x]=="#":
        return
    if  (x,y) in used:
        return
    que.append((x,y,c+1))

f=-1
while que:
    x,y,c=que.popleft()
    if x==w-1 and y==h-1:
        f=c
        break
    used.add((x,y))
    check(x-1,y,c)
    check(x+1,y,c)
    check(x,y-1,c)
    check(x,y+1,c)
print(f if f==-1 else(h*w-f-bcount))


### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
maplis=[input() for i in range(h)]

que=deque([(0,0,1)])
used={(0,0)}
bcount =sum(s.count("#") for s in maplis)


def check(x,y,c):
    if x<0 or x>w-1 or y<0 or y>h-1:
        return
    if maplis[y][x]=="#":
        return
    if  (x,y) in used:
        return
    que.append((x,y,c+1))
    used.add((x,y))

f=-1
while que:
    x,y,c=que.popleft()
    if x==w-1 and y==h-1:
        f=c
        break
    check(x-1,y,c)
    check(x+1,y,c)
    check(x,y-1,c)
    check(x,y+1,c)
print(f if f==-1 else(h*w-f-bcount))
### BUGGY CODE ###

M=998244353
d=[0]*90301
d[0]=1
e=[0]*90301
e[0]=1
z=1
s=0
exec'''a=input();s+=a;i=s;z*=3
while~i:d[i]+=d[i]+d[i-a]%M;e[i]+=e[i-a]%M;i-=1
'''*input()
i=s
while i*2>=s:z=(z-d[i]*3)%M;i-=1
z+=~s%2*e[s//2]*3
print z%M

### FIXED CODE ###

M=998244353
N=int(input())
d=[0]*90001
d[0]=1
e=[0]*90001
e[0]=1
z=1
s=0
for _ in range(N):
	a=int(input())
	i=s
	while i>=0:
		d[i+a]+=d[i]%M
		d[i]*=2
		e[i+a]+=e[i]%M
		i-=1
	s+=a
	z=z*3%M
for i in range(s+1>>1,s+1):
	z-=d[i]*3
	z%=M
print([(z+e[s//2]*3)%M,z][s%2])
### BUGGY CODE ###

job = list()
salary = list()
n,m = map(int,input().split())

for i in range(n):
    a,b = map(int,input().split())
    job.append((a,b))

job.sort(reverse = True)

for x in job:
    s,t = x
    salary.append(t)

    if s - m > 0:
        salary.sort()
        salary.pop(0)
    else:
        m -= 1

print(sum(salary))


### FIXED CODE ###

import heapq
job = list()
salary = list()
n,m = map(int,input().split())

for i in range(n):
    a,b = map(int,input().split())
    job.append((a,b))

job.sort(reverse = True)

for x in job:
    s,t = x
    heapq.heappush(salary,t)
    if s - m > 0:
        heapq.heappop(salary)
    else:
        m -= 1

print(sum(salary))
### BUGGY CODE ###

import functools
import operator


def prod(arr):
    return functools.reduce(operator.mul, arr)


def main():
    N, K = (int(x) for x in input().split(" "))
    A = [int(x) for x in input().split(" ")]
    lastest_score = prod(A[0:K])
    result = [None] * (N-K+1)
    for i in range(1, N-K+1):
        current_score = lastest_score - A[i-1] + A[i + K-1]
        if lastest_score < current_score:
            result[i] = "Yes"
        else:
            result[i] = "No"
        lastest_score = current_score
    [print(x) for x in result[1:]]


if __name__ == '__main__':
    main()


### FIXED CODE ###

def prod(arr):
    s = 0
    for x in arr:
        s += x
    return s


def main():
    N, K = (int(x) for x in input().split(" "))
    A = [int(x) for x in input().split(" ")]
    lastest_score = prod(A[0:K])
    result = ["No"] * (N-K+1)
    for i in range(1, N-K+1):
        current_score = lastest_score - A[i-1] + A[i + K-1]
        if lastest_score < current_score:
            result[i] = "Yes"
        lastest_score = current_score
    [print(x) for x in result[1:]]


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

s=input()
l=len(s)
mod = pow(10,9)+7

dp = [[0 for i in range(13)] for j in range(l+1)]
dp[0][0] = 1

for i in range(1,l+1):
	num = s[-i]
	keta = pow(10,i-1)  % 13
	if num == '?':
		for j in range(10):
			for k in range(13):
				dp[i][(j * keta + k) % 13] += dp[i-1][k] % mod
	else:
		for k in range(13):
			dp[i][(int(num) * keta + k) % 13] += dp[i-1][k] % mod
print(dp[l][5] % mod)

### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])
### BUGGY CODE ###

N, Q = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
X.sort(key = lambda x: x[2])
X.append([-1, 1, X[-1][2] + 1])

def quitConst(t):
  nextx = [x for x in X if x[1] > t or x[0] == -1]
  return nextx

for _ in range(Q):
  current = 0
  start = int(input())
  X = quitConst(start)
  for x in X:
    current = x[2]
    if x[0] <= current + start < x[1]:
      break
  if current == X[-1][2]:
    print(-1)
  else:
    print(current)

### FIXED CODE ###

from bisect import bisect_left as bl
N, Q = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
X.sort(key = lambda x: x[2])
Y = [int(input()) for _ in range(Q)]
res = [-1] * Q
jump = [-1] * Q
for s,t,x in X:
  l=bl(Y,s - x)
  r=bl(Y,t - x)
  while l < r:
    s = jump[l]
    if s == -1:
      res[l] = x
      jump[l] = r
      l += 1
    else:
      l = s
print(*res,sep = '\n')
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

for i in range(N):
    ans*= A[i]

if ans > 10**18:
    ans = -1



print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
if 0 in A:
    print(0)
    exit()
ans = 1

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

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

import fractions
import functools
 
def main():
    n = int(input())
    a = [int(t)for t in input().split()]
 
    a_gcd = functools.reduce(fractions.gcd,a)
  
    a = [x//a_gcd for x in a]
    gcdlist = []
 
    for i in range(n):
        t = [x for x in a]
        del t[i]
        t_gcd = functools.reduce(fractions.gcd,t)
        gcdlist.append(t_gcd)
 
    print(a_gcd*max(gcdlist))
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import fractions
import functools

def main():
    n = int(input())
    a = [int(t)for t in input().split()]

    a_gcd = functools.reduce(fractions.gcd,a)
    a = [x//a_gcd for x in a]
    
    a_rev = a[::-1]

    lgcd = [0]
    rgcd = [0]
    for i in range(n):
        l = fractions.gcd(a[i],lgcd[i])
        r = fractions.gcd(a_rev[i],rgcd[i])
        lgcd.append(l)
        rgcd.append(r)

    rgcd = rgcd[::-1]
    g = [fractions.gcd(lgcd[i],rgcd[i+1]) for i in range(n)]
    
    print(max(g)*a_gcd)
    
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

N = int(input())
L = list(map(int, input().split()))
M = [0] *(N+1)
cnt = [0] *(N+1)

for i in L:
    cnt[i] += 1
    C = cnt[i]
    if C == 2:
        M[i] = 2
    elif C > 2:
        M[i] *= C
        M[i] //= (C-2)
ans = sum(M)//2

for i in range(N):
    A = L[i]
    B = cnt[A]
    if B == 2:
        print(ans - 1)
    elif B > 2:
        print(ans -combinations_count(B,2) +combinations_count(B-1,2))
    else:
        print(ans)

### FIXED CODE ###

N = int(input())
L = [int(i) for i in input().split()]
C = [0 for i in range(N)]
for i in L:
    C[i-1] += 1
res = 0

for i in range(N):
    res += C[i]*(C[i]-1)//2
# 合計最初に出す
for i in range(N):
    j = L[i]-1
    print(res - C[j]*(C[j]-1)//2 + (C[j]-1)*(C[j]-2)//2)
### BUGGY CODE ###

R, C, K = map(int, input().split())
item = [[0]*C for _ in range(R)]
for _ in range(K):
    r, c, v = map(int, input().split())
    item[r-1][c-1] = v

DP = [[[0, 0, 0, 0] for _ in range(C)] for _ in range(R)]

DP[0][0][1] = item[0][0]

for i in range(R):
    for j in range(C):
        for k in range(4):
            if i > 0:  # 前の行から
                DP[i][j][0] = max(DP[i][j][0], max(DP[i-1][j]))  # 取らない
                DP[i][j][1] = max(DP[i][j][1], max(DP[i-1][j])+item[i][j])  # 取る

            if j > 0:  # 前の列から
                DP[i][j][k] = max(DP[i][j][k], DP[i][j-1][k])  # 取らない
                if k >= 1:
                    DP[i][j][k] = max(DP[i][j][k], DP[i][j-1][k-1]+item[i][j])  # 取る

print(max(DP[R-1][C-1]))

### FIXED CODE ###

import sys

R, C, K = map(int, input().split())
item = [[0] * (C + 1) for _ in range(R + 1)]  # dp配列と合わせるために, 0行目, 0列目を追加している.
for s in sys.stdin.readlines():
    r, c, v = map(int, s.split())
    item[r][c] = v

dp = [[[0] * (C + 1) for _ in range(R + 1)] for _ in range(4)]
for i in range(R + 1):
    for j in range(C + 1):
        for k in range(4):
            here = dp[k][i][j]
            # 次の行に移動する場合
            if i + 1 <= R:
                # 移動先のアイテムを取らない場合
                dp[0][i + 1][j] = max(dp[0][i + 1][j], here)
                # 移動先のアイテムを取る場合
                dp[1][i + 1][j] = max(dp[1][i + 1][j], here + item[i + 1][j])
            # 次の列に移動する場合
            if j + 1 <= C:
                # 移動先のアイテムを取らない場合
                dp[k][i][j + 1] = max(dp[k][i][j + 1], here)
                # 現在のkが3未満のときのみ, 移動先のアイテムを取ることが可能
                if k < 3:
                    dp[k + 1][i][j + 1] = max(dp[k + 1][i][j + 1], here + item[i][j + 1])
ans = 0
for k in range(4):
    ans = max(ans, dp[k][-1][-1])
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
lst = [list(map(int,input().split())) for _ in range(M)]

L1,R1 = lst[0]
common = 0
for i in range(L1,R1+1):

    count = 0
    for j in range(1,M):
        Lj,Rj = lst[j]   
        if i < Lj or i > Rj:
            break
        else:
            count += 1

    if count == M-1:
        common += 1

print(common)

### FIXED CODE ###

N,M = map(int,input().split())
maxL = 1
minR = 100000
for i in range(M):
    Li,Ri = map(int,input().split())
    maxL = max(maxL,Li)
    minR = min(minR,Ri)
        
if minR - maxL >= 0:
    print(minR-maxL+1)
else:
    print(0)
### BUGGY CODE ###

N, K = [int(x) for x in input().split()]
P = [int(x) for x in input().split()]

#初期 
SUM = sum(P[0:K])
M=0

for i in range(N - K + 1):
    if SUM < sum(P[i:i + K]):
        SUM = sum(P[i:i + K])
        M = i

EXP_V = (K + SUM)/2
print(EXP_V)

### FIXED CODE ###

N, K = [int(x) for x in input().split()]
P = [int(x) for x in input().split()]

#初期
SUM = [0]*N
SUM[0] = sum(P[0:K])

for i in range(N - K):
    SUM[i+1] = SUM[i]-P[i] + P[i+K]

EXP_V = (K + max(SUM))/2
print(EXP_V)
### BUGGY CODE ###

n, p = [int(i) for i in input().split()]
max_x = int(p**(1/n))+1
ans = 1
for i in range(max_x, 1, -1):
    if p >= pow(i,n) and p % pow(i,n) == 0:
        ans = i
        break
print(ans)

### FIXED CODE ###

n, p = [int(i) for i in input().split()]
tmp = p**(1/n)
if tmp - int(tmp) > 0.999:
    max_x = int(tmp) + 1
else:
    max_x = int(tmp)
ans = 1
for i in range(max_x, 1, -1):
    if p % pow(i,n) == 0:
        ans = i
        break
print(ans)
### BUGGY CODE ###

s = int(input())
l = [s]

while 1:
  if s %2 == 0:
    l.append(s/2)
    s = s/2
  else:
    l.append(3*s + 1)
    s = 3*s+1
  
  if any(l.count(i) >= 2 for i in range(1000001)):
    print(len(l))
    break

### FIXED CODE ###

s = int(input())
l = [s]
max=s

while 1:
  if s %2 == 0:
    l.append(s/2)
    s = int(s/2)
  else:
    l.append(3*s + 1)
    s = 3*s+1
    max = s
  
  if any(l.count(i) >= 2 for i in range(s+1)):
    print(len(l))
    break
### BUGGY CODE ###

def search(ind):
    for i in range(ind):
        if p_ls[i] < p_ls[ind]:
            return 0
    return 1

n = int(input())
p_ls = list(map(int, input().split()))
sub_cnt = 0
for i in range(n):
    sub_cnt += search(i)
print(sub_cnt)


### FIXED CODE ###

n = int(input())
p_ls = list(map(int, input().split()))
mini = p_ls[0]
cnt = 0
for i in range(n):
    if mini >= p_ls[i]:
        cnt+=1
        mini= p_ls[i]
print(cnt)
### BUGGY CODE ###

d_list = []

times = int(input())
for i in range(times):
    elm = input().split()
    code = elm[1].replace("A","1")
    code = code.replace("C","2")
    code = code.replace("G","3")
    code = code.replace("T","4")
    if elm[0] == "insert":
        d_list.append(code)
        d_list = sorted(d_list)

    elif elm[0] == "find":
        lower_bound = 0
        upper_bound = len(d_list)-1
        found = False

        while lower_bound <= upper_bound and not found:
            mid = (lower_bound + upper_bound)//2
            if d_list[mid] < code:
                lower_bound = mid + 1
            elif d_list[mid] > code:
                upper_bound = mid - 1
            else:
                found = True
        if found:
            print("yes")
        else:
            print("no")

### FIXED CODE ###

n = int(input())

d = set()
for i in range(n):
    com = input().split()
    if com[0] == 'insert':
        d.add(com[1])
    else:
        print('yes' if com[1] in d else 'no')
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
w = max(a) - min(a) + 3
abucket = [0] * w
for i in range(n):
  abucket[a[i] - min(a)] += 1
  abucket[a[i] - 1 - min(a)] += 1
  abucket[a[i] + 1 - min(a)] += 1
print(max(abucket))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mina = min(a)
maxa = max(a)
w = maxa - mina + 3
abucket = [0] * w
for i in range(n):
  abucket[a[i] - mina] += 1
  abucket[a[i] - 1 - mina] += 1
  abucket[a[i] + 1 - mina] += 1
print(max(abucket))
### BUGGY CODE ###

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

L = []

if a < b: a,b = b,a
while b!=0:
    r = a%b
    a,b = b,r

G = a

for i in range(2,G+1):
    if G%i==0:
        for j in L:
            if i%j==0:
                break
        else:
            L.append(i)

print(len(L)+1)   


### FIXED CODE ###

from math import sqrt

a,b = map(int,input().split())
 
L = []
 
if a < b: a,b = b,a
while b!=0:
    r = a%b
    a,b = b,r
 
G = a
 
for i in range(2,int(sqrt(G))+1):
    if G%i==0:
        L.append(i)
        while G%i==0:
            G/=i

if G!=1:
    L.append(G)

print(len(L)+1)
### BUGGY CODE ###

N = int(input())
A = []
count=0
for i in range(N):
    a=int(input())
    if a not in A:
        A.append(a)
        count += 1
    else:
        A.remove(a)
        count-=1
print(count)
    

### FIXED CODE ###

N = int(input())
A={}
for _ in range(N):
    a = int(input())
    if a in A:
        A.pop(a)
    else:
        A[a]=1
print(len(A))
### BUGGY CODE ###

n, k = map(int,input().split(" "))
l = []
for i in range(n):
    a, b = map(int, input().split(" "))
    l.extend([a] * b)
l.sort()
print(l[k - 1])


### FIXED CODE ###

n, k = map(int,input().split(" "))
num_count = dict()
for i in range(n):
    a, b = map(int, input().split(" "))
    if a not in num_count:
        num_count[a] = 0

    num_count[a] += b

temp = 0
for key in sorted(num_count.keys()):
    temp += num_count[key]
    if temp >= k:
        print(key)
        break
### BUGGY CODE ###

import math

n, m=map(int, input().split())
t = {}
a = int(math.sqrt(m))

s=0

line = [2, 3] + [i%2*2 + i//2 * 6 + 5 for i in range(a//3)]
while s==0:
    for i in line:
        cnt = 0
        while m%i==0:
            m=m//i
            cnt += 1

        if cnt>0:
            t[i]=cnt

        if m==1:
            s=1
            break

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

out=1
for tk in t.keys():
    out *= combi(t[tk]+n-1, n-1)
print(out%(1000000007))

### FIXED CODE ###

import math

n, m=map(int, input().split())
t = {}
a = int(math.sqrt(m))

s=0

line = [2, 3] + [i%2*2 + i//2 * 6 + 5 for i in range(a)]
# line = [2] + list(range(3, m+2, 2))

for i in line:
# for i in range(2, m+2, 2):
#     print(i)
    cnt = 0
    while m%i==0:
        m=m//i
        cnt += 1

    if cnt>0:
        t[i]=cnt

    if m==1:
        break

if m!=1:
    t[m]=1

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

out=1
for tk in t.keys():
    out *= combi(t[tk]+n-1, n-1)
#     out = out%(1000000007)
print(out%(1000000007))
### BUGGY CODE ###

from collections import deque
import numpy as np
 
 
H,W= [int(x) for x in input().split()]
n=[]
T=np.zeros((H,W),dtype=int)

for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
B=T.copy()    
d=0
for i in range(H):
    for j in range(W):
         
        if T[i][j] ==1:continue

        c=deque()    
        s=0
        c+=[i,j]
        
        t=len(c)//2
        while t>0:
                s+=1
                t=len(c)//2
                for k in range(t):
                        m = c.popleft()
                        n = c.popleft()
                        T[m][n]=s
                        if m != H-1:
                                if T[m+1][n]==0:
                                        c.append(m+1)
                                        c.append(n)
                        if m != 0:
                                if T[m-1][n]==0:
                                        c.append(m-1)
                                        c.append(n)
 
                        if n != W-1:
                                if T[m][n+1]==0:
                                        c.append(m)
                                        c.append(n+1)
                                        
                        if n != 0:
                                if T[m][n-1]==0:
                                        c.append(m)
                                        c.append(n-1)

        #print(T)
        d = max(d,s)
        T=B.copy()
        
print(d-2)

### FIXED CODE ###

from collections import deque
import numpy as np
 
 
H,W= [int(x) for x in input().split()]
n=[]
T=np.zeros((H,W),dtype=int)
#T=[]
S=np.zeros_like(T,dtype=int) 
for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
#B=T.copy()    
d=0
c=deque()  
for i in range(H):
    for j in range(W):
         
        if T[i][j] ==1:continue
 
          
        c.append((i,j))
        S[i][j] = 1
        #c.append(j)
        
        #t=len(c)
        while True:

                try:
                  m,n = c.popleft()
                except IndexError: break
                
                
                for kk in [(m+1,n),(m-1,n),(m,n+1),(m,n-1)]:
                  if not (0<=kk[0]<H and 0<= kk[1] <W): continue
                  if T[kk]==1:continue
                  if S[kk] == 0:
                    c.append(kk)
                    S[kk] = S[m][n]+1        
                        
 
        #print(T)
        d = max(d,np.max(S))
        S=np.zeros_like(T,dtype=int)
        
print(d-1)
### BUGGY CODE ###

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

"""
atuple = tuple(alist)

acount = collections.Counter(atuple)
print(acount,q,k)
tlist = []
for key,v in acount.items():
    if q - v < k:
        tlist.append(key)
"""

for i in range(1,n+1):
    if q - alist.count(i) < k:
        print("Yes")
    else:
        print("No")
        

### FIXED CODE ###

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

atuple = tuple(alist)

acount = collections.Counter(atuple)
#print(acount,q,k)

for i in range(1,n+1):
    if q - acount[i] < k:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###


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


possibles = []
for x in xs:
    possibles.append(x - 1)
    possibles.append(x)
    possibles.append(x + 1)

possibles = set(possibles)

ds = []
for p in possibles:
    d = 0
    for x in xs:
        c = abs(x - p)
        if c <= 1: d += 1
    ds.append(d)

print(max(ds))







### FIXED CODE ###


from collections import Counter


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


c = Counter(xs)


res = 0
for i in range(100000):
    res = max(res, c[i] + c[i - 1] + c[i + 1])

print(res)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7


def f(index, l):
    if index == len(l):
        return 1
    if l[index] == '1':
        return ( 3 ** (len(l)-1-index) + 2 * f(index+1, l) ) % MOD
    else:
        return f(index+1, l) % MOD


def main():
    l = input()
    n = len(l)
    one = 0
    ans = 0
    for i in range(n):
        if l[i] == '1':
            ans += 2**one * 3**(n-1-i)
            ans %= MOD
            one += 1
    ans += 2**one
    ans %= MOD
    print(ans)

main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7


def f(index, l):
    if index == len(l):
        return 1
    if l[index] == '1':
        return ( 3 ** (len(l)-1-index) + 2 * f(index+1, l) ) % MOD
    else:
        return f(index+1, l) % MOD


def main():
    l = input()
    n = len(l)
    one = 0
    ans = 0
    for i in range(n):
        if l[i] == '1':
            ans += pow(2, one, MOD) * pow(3, n-1-i, MOD)
            ans %= MOD
            one += 1
    ans += pow(2, one, MOD)
    ans %= MOD
    print(ans)

main()
### BUGGY CODE ###

from copy import copy
n = int(input())
a_ls = list(map(int, input().split()))
c_bin = [[0]*60 for _ in range(n)]
a_bin_ls = [[0]*60 for _ in range(n)]
now_bin = [0] * 60
for i in range(n-1,-1,-1):
    a = a_ls[i]
    j = 0
    while True:
        if a == 1:
            now_bin[j] += 1
            a_bin_ls[i][j] = 1
            break
        elif a == 0:
            break
        a,r = divmod(a,2)
        now_bin[j] += r 
        a_bin_ls[i][j] = r
        j += 1
    c_bin[i] = copy(now_bin)
ans_bin = [0]*60
for i in range(n-1):
    a_bin = a_bin_ls[i]
    for j in range(60):
        if a_bin[j] == 0:
            times = c_bin[i+1][j]
        else:
            times = n - (i+1) - c_bin[i+1][j]
        ans_bin[j] += times
ans = 0
mod = 10**9+7
for i in range(60):
    ans += 2**i * (ans_bin[i]%mod)
    ans %= mod
print(ans)




### FIXED CODE ###

from copy import copy
n = int(input())
a_ls = list(map(int, input().split()))
c_bin = [[0]*60 for _ in range(n)]
a_bin_ls = [[0]*60 for _ in range(n)]
now_bin = [0] * 60
for i in range(n-1,-1,-1):
    a = a_ls[i]
    j = 0
    while True:
        if a == 1:
            now_bin[j] += 1
            a_bin_ls[i][j] = 1
            break
        elif a == 0:
            break
        a,r = divmod(a,2)
        now_bin[j] += r 
        a_bin_ls[i][j] = r
        j += 1
    c_bin[i] = copy(now_bin)
ans_bin = [0]*60
for i in range(n-1):
    a_bin = a_bin_ls[i]
    for j in range(60):
        if a_bin[j] == 0:
            times = c_bin[i+1][j]
        else:
            times = n - (i+1) - c_bin[i+1][j]
        ans_bin[j] += times
ans = 0
mod = 10**9+7
for i in range(60):
    ans += 2**i * (ans_bin[i]%mod)
    ans %= mod
print(ans)