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

import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
sys.setrecursionlimit(10**7)

def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

# def comb(n):
#     return int(n*(n-1)/2)

def main():
    N = I()
    A_list = LI()
    A_ctr = collections.Counter(A_list)
    for i in range(1,N+1):
        ans = 0
        for k,v in A_ctr.items():
            if A_list[i-1]==k:
                # ans += comb(v-1)
                n = v-1
                ans += int(n*(n-1)/2)
            else:
                n = v
                ans += int(n*(n-1)/2)
        else:
            print(ans)

main()


### FIXED CODE ###

import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
sys.setrecursionlimit(10**7)

def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

def comb(n):
    return int(n*(n-1)/2)

def main():
    N = I()
    A_list = LI()
    A_ctr = collections.Counter(A_list)
    base = 0
    for i in range(1,N+1):
        base += comb(A_ctr[i])
    for i in range(1,N+1):
        i_val = A_ctr[A_list[i-1]]
        before = comb(i_val)
        after = comb(i_val-1)
        print(int(base - before + after))
main()
### BUGGY CODE ###

s = str(input())
K = int(input())
stack = []
for i in range(len(s)):
    for j in range(i+1, min(i+1+K, len(s))+1):
        sub = s[i:j]
        if sub not in stack:
            stack.append(sub)
stack.sort()
print(stack[K-1])

### FIXED CODE ###

s = str(input())
K = int(input())
stack = []
for i in range(len(s)):
    for j in range(i+1, min(i+K, len(s))+1):
        sub = s[i:j]
        if sub not in stack:
            stack.append(sub)
stack.sort()
print(stack[K-1])
### BUGGY CODE ###

S = input()
N = len(S)
S = list(S)
Children = [0]*N
RL = []
LR = []

A = [0]*N
for i in range(N):
    if S[i] =='L':
        A[i] = 1
    elif S[i] == 'R':
        A[i] = 2

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

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

Child = [LR[0]]
for i in range(1,len(LR)):
    Child.append(LR[i]-LR[i-1])

Change = sorted(RL+LR)
dig = [0]*len(Change)
dig[0] = Change[0]
for i in range(1,len(Change)):
    dig[i] = Change[i] - Change[i-1]

Rtype = [0]*len(RL)
for i in range(len(RL)):
    if Child[i] % 2 == 0:
        Rtype[i] = 0
    else:
        if dig[2*i]%2==0:
            Rtype[i] = 1
        if dig[2*i+1]%2==0:
            Rtype[i] = -1

k=0
for i in range(N):
    if i+1 in RL: #Rの方
        if Rtype[k] == 0:
            Children[i] += Child[k]//2
        elif Rtype[k] == 1:
            Children[i] += Child[k]//2
        elif Rtype[k] == -1:
            Children[i] += Child[k]//2 + 1
    if i in RL: #Lの方
        if Rtype[k] == 0:
            Children[i] += Child[k]//2
        elif Rtype[k] == 1:
            Children[i] += Child[k]//2 + 1
        elif Rtype[k] == -1:
            Children[i] += Child[k]//2
        k += 1

print(*Children)


### FIXED CODE ###

def ranlength(A):
    num = list(A)
    count = 1
    result = ''
    table = []
    for i in range(len(num)):
        try:
            if num[i] == num[i+1]:
               count = count + 1
            else:
                result += str(num[i]) + str(count)
                table.append(count)
                count = 1
        except:
            result += str(num[i]) + str(count)
            table.append(count)
    return(table)
    
S = ranlength(input())
#RRLRLなら[2,1,1,1]で出る

def gather(x,y):
    ans = [0]*(x+y)
    if (x+y)%2 == 0:
        ans[x-1] = (x+y)//2
        ans[x] = (x+y)//2
    if x%2 == 0 and y%2 != 0:
        ans[x-1] = (x+y)//2
        ans[x] = (x+y)//2 + 1
    elif x%2 != 0 and y%2 == 0:
        ans[x-1] = (x+y)//2 + 1
        ans[x] = (x+y)//2
    return(ans)

children = []
for i in range(len(S)//2):
    children += gather(S[2*i],S[2*i+1])

print(*children)
### BUGGY CODE ###

import math
num,query = (int(n) for n in input().split(' '))
table = [2**31 - 1 for n in range(num)]
sqrttable = []
sqrtnum = math.floor(math.sqrt(num))
tempmin = float("inf")
for t in range(num):
    if t % sqrtnum == sqrtnum - 1:
        tempmin = min(table[t],tempmin)
        sqrttable.append(tempmin)
    elif t == num - 1:
        tempmin = min(table[t],tempmin)
        sqrttable.append(tempmin)
    else:
        tempmin = min(table[t],tempmin)

for q in range(query):
    #print(sqrtnum,table,sqrttable)
    temp = [int(n) for n in input().split(' ')]
    if temp[0] == 0:
        table[temp[1]] = temp[2]
        tempmin = float("inf")
        for tm in range(sqrtnum*(temp[1]//sqrtnum),min(num,sqrtnum*(temp[1]//sqrtnum + 1))):
            tempmin = min(table[tm],tempmin)
        sqrttable[temp[1]//sqrtnum] = tempmin
    else:
        tempmin = float("inf")
        if temp[1] % sqrtnum != 0:
            for ini in range(temp[1],min(temp[2]+1,sqrtnum * math.ceil(temp[1] / sqrtnum))):
                tempmin = min(tempmin,table[ini])
        newtemp2 = temp[2] + 1
        for sqt in range(math.ceil(temp[1] / sqrtnum),newtemp2 // sqrtnum):
            tempmin = min(sqrttable[sqt],tempmin)
        if temp[2] % sqrtnum != sqrtnum -1:
            for end in range(max(temp[1],sqrtnum * (temp[2]//sqrtnum)),temp[2]+1):
                tempmin = min(tempmin,table[end])
        #print(tempmin,sqrtnum,temp[1],temp[2],table,sqrttable)
        print(tempmin)

### FIXED CODE ###

class RMQ:
    def __init__(self, length, ini_num = float("inf")):
        self.length = 1
        self.ini_num = ini_num
        while self.length < length:
            self.length <<= 1
        self.segtree = [ini_num] * (2 * self.length - 1)

    def update(self, index, n):
        leaf_index = index + self.length - 1
        self.segtree[leaf_index] = n
        while leaf_index > 0:
            leaf_index = (leaf_index - 1) // 2
            self.segtree[leaf_index] = min(self.segtree[leaf_index * 2 + 1], self.segtree[leaf_index * 2 + 2])

    def find(self, a, b, index, l, r):
        if a <= l <= r <= b:
            return self.segtree[index]
        elif b < l or r < a:
            return self.ini_num
        else:
            return min(self.find(a, b, index * 2 + 1, l, (l + r) // 2), self.find(a, b, index * 2 + 2, (l + r) // 2 + 1, r))

v_num, query = map(int, input().split(" "))
rmq = RMQ(v_num, 2147483647)
for _ in [0] * query:
    com, i, n = map(int, input().split(" "))
    if com == 0:
        rmq.update(i, n)
    else:
        print(rmq.find(i, n, 0, 0, rmq.length - 1))
### BUGGY CODE ###

from collections import Counter
import sys
input = sys.stdin.readline

n = int(input())
s = input()
c = Counter(s)
cnt = c['R'] * c['G'] * c['B']

for i in range(n-2):
    for j in range(i+1, n-1):
        if s[i] == s[j]:
            continue
        w = j - i
        if j+w >= n:
            continue
        if s[i] == s[j+w] or s[j+w] == s[j]:
            continue
        if s[i] != s[j+w] != s[j]:
            cnt -= 1

print(cnt)


### FIXED CODE ###

from collections import Counter

n = int(input())
s = input()
c = Counter(s)
cnt = c['R'] * c['G'] * c['B']

for i in range(n-2):
    for j in range(i+1, n-1):
        w = j - i
        if j+w >= n:
            continue
        if s[i] != s[j] and s[j+w] != s[j] and s[j+w] != s[i]:
            cnt -= 1

print(cnt)
### BUGGY CODE ###

import collections
def main():

    N = int(input())
    S = input()
    d = collections.defaultdict(list)
    for l in range(1, N+1):
        for i in range(N-l+1):
            d[S[i:i+l]].append([i, i+l-1])

    ans = 0
    for s in d:
        if len(d[s]) > 1:
            i, j = d[s][0]
            k, l = d[s][-1]
            if j < k:
                ans = max(ans, j-i+1)

    return ans

if __name__ == '__main__':
    print(main())

### FIXED CODE ###

def main():

    N = int(input())
    S = input()
    dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
    ans = 0

    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if S[i-1] == S[j-1] and dp[i-1][j-1] < (j-i):
                dp[i][j] = dp[i-1][j-1] + 1
                ans = max(ans, dp[i][j])
            else:
                dp[i][j] == 0
    return ans

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

n,k=map(int,input().split())
a=[[0]*n for _ in range(100)]
A=list(map(int,input().split()))
for i,j in enumerate(A):
    a[0][i]=j-1
i=1
while 2**i<k:
    for x,y in enumerate(a[i-1]):
        a[i][x]=a[i-1][y]
    i+=1
x=0
for j in range(i):
    if k>>j&1:
        x=a[j][x]
print(x+1)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
chk=[False]*n
x=0
visit=[0]
chk[x]=True
while chk:
    x=a[x]-1
    if chk[x]:
        break
    else:
        visit.append(x)
        chk[x]=True
l1=0
while visit[l1]!=x:
    l1+=1
l2=len(visit)-l1
if k>=l1:
    print(visit[l1+((k-l1)%l2)]+1)
else:
    print(visit[k]+1)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x, y = 0, 0
ans = 1
if len(set(a)) < n or len(set(b)) < m:
    exit(print(0))
for i in range(n * m, 0, -1):
    if i in a and i in b:
        x += 1
        y += 1
    elif i in a:
        ans *= x
        y += 1
    elif i in b:
        ans *= y
        x += 1
    else:
        ans *= x * y - n * m + i
    ans %= 10 ** 9 + 7
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x, y = 0, 0
ans = 1
if len(set(a)) < n or len(set(b)) < m:
    exit(print(0))
for i in range(n * m, 0, -1):
    if i in a and i in b:
        x += 1
        y += 1
    elif i in a:
        ans *= x
        y += 1
    elif i in b:
        ans *= y
        x += 1
    else:
        ans *= x * y - n * m + i
    ans %= 10 ** 9 + 7
print(ans)
### BUGGY CODE ###

n = int(input())

ans = set()


for i in range(n):
    s = input()
    if s in ans:
        ans = ans - {s}
    else:
        ans = ans | {s}

print(len(ans))


### FIXED CODE ###

n = int(input())

ans = [input() for i in range(n)]

ans.sort()

s = sorted(set(ans))
t = 0
cnt = 0

result = 0
for i in range(n):
    temp = s[t]
    if ans[i] == temp:
        cnt += 1
    else:
        if cnt % 2 == 1:
            result += 1
        cnt = 1
        t += 1
else:
    if cnt % 2 == 1:
        result += 1
        
    
    

print(result)
### BUGGY CODE ###

A, B, C, K = map(int, input().split())
result = 0

if A >= K:
    print(K)
else:
    for i in range(K):
        if A > (i + 1):
            result += 1
            continue
        elif A == (i + 1):
            result += 1
            continue

        if B > (i + 1 - A):
            result += 0
            continue
        elif B == (i + 1 - A):
            result += 0
            continue

        if C > (i + 1 - A - B):
            result -= 1
            continue
        elif C == (i + 1 - A - B):
            result -= 1
            break
        else:
            break
    print(result)

### FIXED CODE ###

A, B, C, K = map(int, input().split())
if A >= K:
    print(K)
elif (A + B) >= K:
    print(A)
elif (A + B + C) > K:
    print(A - (K - A - B))
elif (A + B + C) == K:
    print(A - C)
### BUGGY CODE ###

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

fl = True
check = []
while True:
    tmp = len(check)
    for i in range(1,N):
        if H[i]-H[i-1]<0 and not i-1 in check:
            H[i-1] -= 1
            check.append(i-1)
    if len(check)==tmp:
        break

for i in range(1,N):
    if H[i]-H[i-1]<0:
        fl = False
        break

print('Yes') if fl else print('No')


### FIXED CODE ###

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

fl = True
for i in range(1,N):
    if H[i]-H[i-1]>0:
        H[i] -= 1

for i in range(1,N):
    if H[i]-H[i-1]<0:
        fl = False
        break

print('Yes') if fl else print('No')
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)] + [0]
ans = [max(a[1:])]

for i in range(1, n):
    if a[i] in a[:i] or a[i] in a[i+1:]:
        ans.append(ans[i-1])
    else:
        max_l = max(a[:i])
        max_r = max(a[i+1:])
        ans.append(max(max_l, max_r))

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

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)] + [0]

sorted_a = sorted(a)
a_first = sorted_a[-1]
a_second = sorted_a[-2]

for i in range(n):
    if a[i] == a_first:
        print(a_second)
    else:
        print(a_first)
### BUGGY CODE ###

n,m = map(int,input().split())
a = [k for k in range(1,10**5+1)]
s = set(a)
for i in range(m):
  l,r = map(int,input().split())
  ml = []
  for j in range(l,r+1):
    ml.append(j)
  newset = set(ml)
  s = s&newset
print(len(s))

### FIXED CODE ###

n,m = map(int,input().split())
L = []
R = []
for i in range(m):
  l,r = map(int,input().split())
  L.append(l)
  R.append(r)

ans = min(R)-max(L)+1
print(ans if ans >0 else "0")
### BUGGY CODE ###

n=int(input())
s= []
for _ in range(n):
    s.append(input())
S=[]
S.append(s[0])
for i in range(1,n):
    for j in range(len(S)):
        if s[i]==S[j]:
            break
    else:
      S.append(s[i])
print(len(S))

### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]
print(len(set(s)))
### BUGGY CODE ###

from collections import defaultdict,deque
N,Q = map(int,input().split())
c = [-1]+list(map(int,input().split()))
lastAppeared = defaultdict(lambda:-1)
ans = [0]*Q
queries = []
for i in range(Q):
    l,r = map(int,input().split())
    queries.append((l,r,i))
queries.sort(key = lambda x:x[1])
curR = 0
#A1 ... AnのBIT(1-indexed)
BIT = [0]*(N+1)

#A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return
for j in range(Q):
    l,r,i = queries[j]
    while curR < r:
        curR += 1
        if lastAppeared[c[curR]] != -1:
            last = lastAppeared[c[curR]]
            BIT_update(last,-1)
        lastAppeared[c[curR]] = curR
        BIT_update(curR,1)
    ans[i] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])

### FIXED CODE ###

N,Q = map(int,input().split())
BIT = [0]*(N+1)

def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

c = [-1]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for q in range(Q):
    l,r = map(int,input().split())
    queries.append((l,r,q))
queries.sort(key = lambda x:x[1])

curR = 0
for i in range(Q):
    l,r,q = queries[i]
    while curR < r:
        curR += 1
        new = c[curR]
        last = lastAppeared[new]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[new] = curR
        BIT_update(curR,1)
    ans[q] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])
### BUGGY CODE ###

n=input()
s=list(map(int,input().split()))
ans=1
for i in s:
   ans=ans*i
if ans>10**18:
       print(-1)
else:
       print(ans)
       


### FIXED CODE ###

n=int(input())
x=list(map(int,input().split()))
ans=1
for i in x:
  if i==0:
    print(0)
    exit()

for i in x:
    ans=ans*i
    if ans>10**18:
      ans=-1
      break
print(ans)
### BUGGY CODE ###

n = int(input())
DifMax = -999999999

R = [int(input())]
for i in range(1, n):
  RMin = min(R)
  R.append(int(input()))
  if DifMax < R[i] - RMin:
    DifMax = R[i] - RMin

print(DifMax)

### FIXED CODE ###

n = int(input())
DifMax = -9999999999999

R = [int(input())]
RMin = R[0]
for i in range(1, n):
  if RMin > R[i-1]:
      RMin = R[i-1]
  R.append(int(input()))
  if DifMax < R[i] - RMin:
    DifMax = R[i] - RMin

print(DifMax)
### BUGGY CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                if l1*l2<k:
                    break
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)
### BUGGY CODE ###

import numpy as np
S = input()

mod=13
mod2=10**9+7
def pow_mod(x,n):
    if n==0:
        return 1
    
    K = 1
    while n>1:
        if n%2 != 0:
            K *= x
            K %= mod
        x *= x
        x %= mod
        n //= 2

    return (K*x)%mod

dp = np.zeros((10**5+1,13),dtype="int")
S=S[::-1]
if S[0]=="?":
    for j in range(10):
        dp[1][j] = 1
else:
    dp[1][int(S[0])] = 1

for i in range(1,len(S)):
    amari = pow_mod(10,i)
    if S[i]=="?":
        for j in range(13):
            for k in range(10):
                dp[i+1][j] += dp[i][(j-amari*k)%mod]
            dp[i+1][j] %= mod2
    else:
        for j in range(13):
            dp[i+1][j] += dp[i][(j-amari*int(S[i]))%mod]
            dp[i+1][j] %= mod2

print(dp[len(S)][5])

### FIXED CODE ###

#import numpy as np
S = input()
N = len(S)
mod=13
mod2=10**9+7
def pow_mod(x,n):
    if n==0:
        return 1
    
    K = 1
    while n>1:
        if n%2 != 0:
            K *= x
            K %= mod
        x *= x
        x %= mod
        n //= 2

    return (K*x)%mod

#dp = np.zeros((N+1,13),dtype="int")
dp = [[0] * 13 for i in range(N+1)]
S=S[::-1]
if S[0]=="?":
    for j in range(10):
        dp[1][j] = 1
else:
    dp[1][int(S[0])] = 1

for i in range(1,N):
    amari = pow_mod(10,i)
    if S[i]=="?":
        for j in range(13):
            for k in range(10):
                dp[i+1][j] += dp[i][(j-amari*k)%mod]
            dp[i+1][j] %= mod2
    else:
        for j in range(13):
            dp[i+1][j] += dp[i][(j-amari*int(S[i]))%mod]
            dp[i+1][j] %= mod2

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

def main():
    N, K  = [int(i) for i in input().split()]
    A  = [int(i) for i in input().split()]
    r = 0
    for i in range(N):
        t = 0
        for c, a in enumerate(A[i:], 1):
            t = (t + a) % K
            if t == c:
                r += 1
    return(r)


print(main())


### FIXED CODE ###

def main():
    N, K  = [int(i) for i in input().split()]
    A  = [int(i) for i in input().split()]
    v = {0: 1}
    n = [0]
    r = 0
    t = 0
    for i, a in enumerate(A, 1):
        if i >= K:
            v[n[i - K]] -= 1
        t += a
        j = (t - i) % K
        r += v.get(j, 0)
        v[j] = v.get(j, 0) + 1
        n.append(j)

    return r


print(main())
### BUGGY CODE ###

import math

n, d, a = map(int,input().split())
xh = []
for i in range(n):
    x,h = map(int,input().split())
    xh.append([x,h])

num = 0
xh.sort(key=lambda xh:xh[0])

while len(xh) > 0.5:
    nat = math.ceil((xh[0][1])/a)
    num += nat
    dam = nat*a
    for i in range(len(xh)):
        if xh[i][0] <= xh[0][0]+2*d:
            xh[i][1] -= dam
        else:
            break
    xh = [i for i in xh if i[1] > 0]

print(num)


### FIXED CODE ###

import math

n, d, a = map(int,input().split())
xh = [[0 for i in range(2)] for j in range(n)]
left = [i for i in range(n)]
for i in range(n):
    x,h = map(int,input().split())
    xh[i] = [x,h]

num = 0
xh.sort(key=lambda xh:xh[0])

for i in range(n):
    for j in range(left[i-1],i):
        if xh[j][0]+d >= xh[i][0]-d:
            left[i] = j
            break

dam = [0]*n

def dsum(k):
    if k == 0:
        return 0
    elif left[k] == 0:
        return dam[k-1]
    else:
        return dam[k-1]-dam[left[k]-1]

for i in range(n):
    res = xh[i][1]-dsum(i)
    nat = max([math.ceil(res/a),0])
    dam[i] = dam[i-1]+a*nat
    if res > 0:
        num += nat

print(num)
### BUGGY CODE ###

N, K = map(int, input().split())
p = input().split()
p = [((int(i)+1)/2) for i in p]
SUM_P = []
for i in range(N-K+1):
    SUM_P.append(sum(p[i:i+K]))
print(max(SUM_P))

### FIXED CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
SUM_P=sum(p[0:K])
all_sum_p=[SUM_P]
for i in range(N-K):
    SUM_P=SUM_P-p[i]+p[i+K]
    all_sum_p.append(SUM_P)
print((max(all_sum_p)+K)/2)
### BUGGY CODE ###

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

if B > N:
    ans = int(A*N/B)
    print(ans)
else:
    t = int(A*N/B)- A*int(N/B)
    ans = 0
    x = (N//B)*B - 1
    while True:
        temp = int(A*x/B) - A*int(x/B)
        # if ans > temp:
        #     break
        # ans = temp
        ans = max(ans, temp)
        x -= B
        if x < 0:
            break
    print(max(ans, t))

### FIXED CODE ###

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

if B > N:
    print(int((A*N)/B)-A*int(N/B))
else:
    print(int((A*(B-1))/B)-A*int((B-1)/B))

# if B > N:
#     ans = floor(A*N/B)
#     print(ans)
# else:
#     ans = floor(A*N/B) - A*floor(N/B)
#     ans_2nd = 0
#     x = (N//B)*B - 1
#     temp = floor((A*x)/B) - A*floor(x/B)
#     # while ans <= temp and x >= 0:
#     #     ans = temp
#     #     temp = floor(A*x/B) - A*floor(x/B)
#     #     x -= B
#     # while ans_2nd <= temp and x >= 0:
#     #     ans_2nd = temp
#     #     temp = floor(A*x/B) - A*floor(x/B)
#     #     x -= B
#     # prfloor(max(ans, ans_2nd))
#     print(max(temp, ans))
### BUGGY CODE ###

def main():
  s=input()
  n=len(s)
  a,b,M=0,1,10**9+7
  p=[1]
  for i in range(n-1):
    p.append(p[i]*3%M)
  for i,t in enumerate(map(int,s)):
    if t:
      a=(a+b*p[~i])%M
      b*=2
  print((a+b)%M)
main()

### FIXED CODE ###

def main():
  s=input()
  n=len(s)
  a,b,M=0,1,10**9+7
  p=[1]
  for i in range(n-1):
    p.append(p[i]*3%M)
  for i,t in enumerate(map(int,s)):
    if t:
      a=(a+b*p[~i])%M
      b=b*2%M
  print((a+b)%M)
main()