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

N,K = map(int,input().split())
N = list(map(int,input().split()))
if K != 0 and len(N) < K:
    print(0)
    exit()
for i in range(K):
    N.remove(max(N))
print(sum(N))

### FIXED CODE ###

import sys
NK = input().split()
N,K = int(NK[0]),int(NK[1])
H = list(map(int,input().split()))
if K != 0 and len(H) < K:
    print(0)
    exit()
H.sort()
for i in range(K):
    H.pop(-1)
print(sum(H))

def input():
    return sys.stdin.readline()[:-1]
### BUGGY CODE ###

import bisect
import sys
input = sys.stdin.readline

n,d,a= map(int, input().split())
x= [list(map(int, input().split())) for i in range(n)]

x.sort()
y=[]
for i in range(n):
    y.append(x[i][0])
    x[i][1]=-(-x[i][1]//a)

# どのモンスターまで倒したか管理しながら進める。
ans=0
for i in range(n):
    if x[i][1]>=1:
        w=x[i][1]
        ans+=w
        q=bisect.bisect_right(y,x[i][0]+2*d)
        for j in range(q-i):
            x[i+j][1]-=w
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect
import collections
from collections import deque
n,d,a= map(int, input().split())
x= [list(map(int, input().split())) for i in range(n)]

x.sort()
y=[]
for i in range(n):
    y.append(x[i][0])
    x[i][1]=-(-x[i][1]//a)

# どのモンスターまで倒したか管理しながら進める。
# 累積ダメージを管理
qq=deque([])
ans=0
atk=0
for i in range(n):
    w=x[i][1]
    # iがダメージの有効期限を超過している場合
    while len(qq)>0 and i > qq[0][0]:
        atk-=qq[0][1]
        qq.popleft()

    if w-atk>0:
        ans+=w-atk
        q=bisect.bisect_right(y,x[i][0]+2*d)-1
        # 有効期限　ダメージ
        qq.append([q,w-atk])
        atk += w - atk
print(ans)
### BUGGY CODE ###

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

ans = n
for x in set(a):
    if a.count(x) >= x:
        ans -= x

print(ans)

### FIXED CODE ###

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

b = set(a)

hoge = {}

for x in b:
    hoge[x] = 0

for x in a:
    hoge[x] += 1

ans = n
for x in b:
    if hoge[x] >= x:
        ans -= x

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

a, b = map(int, input().split())
f = a
for i in range(a + 1, b + 1):
    f ^= i
print(f)

### FIXED CODE ###

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

def xor(n):
    if n % 4 == 0:
        return 0 ^ n
    elif n % 4 == 1:
        return 1
    elif n % 4 == 2:
        return 1 ^ n
    else:
        return 0
fa = xor(a - 1)
fb = xor(b)
print(fa ^ fb)
### BUGGY CODE ###

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

#行ったことある町リスト
d=[1]
for _ in range(K):
  T=A[d[-1]-1]
  if T in d:
    break
  d.append(T)
F=d.index(T)
LOOP_TOWN=d[F:]
q=(K-F)%len(LOOP_TOWN)
print(LOOP_TOWN[q])

### FIXED CODE ###

def main():
  N,K=map(int,input().split())
  A=list(map(int,input().split()))
  n=[0]*N
  #行ったことある町リスト
  d=[1]
  for _ in range(K):
    T=A[d[-1]-1]
    if n[T-1]==1:
      break
    else:
      n[T-1]=1
    d.append(T)
  F=d.index(T)
  LOOP_TOWN=d[F:]
  q=(K-F)%len(LOOP_TOWN)
  print(LOOP_TOWN[q])

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

#! /usr/bin/env python3

n, k = map(int, input().split())
M = [[7*i+j-7 for j in range(1, 7+1)] for i in range(1, n+1)]
cnt = 0
f = lambda i, j : sum(M[i+y][j+x] for y in range(3) for x in range(3)) % 11 == k
for i in range(n-2):
    for j in range(7-2):
        if f(i, j) :
            cnt += 1
print(cnt)

### FIXED CODE ###

#! /usr/bin/env python3

n, k = map(int, input().split())
M = [[7*i+j-7 for j in range(1, 7+1)] for i in range(1, min(n+1, 14))]
cnt = 0
f = lambda i, j : sum(M[i+y][j+x] for y in range(3) for x in range(3)) % 11 == k
h = [0] * 11
for i in range(min(max(0, n-2), 11)):
    for j in range(7-2):
        if f(i, j) :
            h[i] += 1
cnt = sum(h) * ((n-2) // 11)
for i in range((n-2) % 11):
    cnt += h[i]
print(cnt)
### BUGGY CODE ###

N , K = map(int, input().split())
flag = "F"
while 1:
    if N>10000*K:
        N -10000*K
    a = N
    N = abs(N - K)
    

    if a<=K and N <= K:
        if a < N:
            result = a
            flag="T"
        else:
            result = N
            flag="T"
    if flag == "T":
        break
print(result)

### FIXED CODE ###

import math

N , K = map(int, input().split())
flag = "F"
if N !=0:
    while 1:
        lenN = int (math.log10(N) + 1)
        lenK = int (math.log10(K) + 1)
        N = abs(N-K*(10**abs(lenN-lenK-1)))
        lenN = int (math.log10(N) + 1)
        if abs(lenN-lenK)<2:
            break



        
while 1:
    
    
    a = N
    N = abs(N - K)
    

    if a<=K and N <= K:
        if a < N:
            result = a
            flag="T"
        else:
            result = N
            flag="T"
    if flag == "T":
        break
print(result)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
l=list(set(a))
ans=0
for i in range(len(l)):
    if a.count(l[i])<l[i]:
        ans+=a.count(l[i])
    else:
        ans+=a.count(l[i])-l[i]
print(ans)

### FIXED CODE ###

import collections
n=int(input())
a=list(map(int,input().split()))
l=list(set(a))
m=collections.Counter(a)
ans=0
for i in range(len(l)):
    if m[l[i]]<l[i]:
        ans+=m[l[i]]
    else:
        ans+=m[l[i]]-l[i]
print(ans)
### BUGGY CODE ###

args = int(input().rstrip())

def snuke(n):
    s = 0
    while n:
        s += n % 10
        n //= 10
    return s

def find_snuke(args):
    result = []
    i = 1
    while len(result) < args:
        push = True
        for power in range(0,len(str(i))):
            if((i+10**power)/snuke(i+10**power))<(i/snuke(i)):
                push = False
                break
        if push:
            result.append(i)
        i=i+1
            
    return result

arr = find_snuke(args)
for a in arr:
   print(a)

### FIXED CODE ###

args = int(input().rstrip())

def snuke(n):
    s = 0
    while n:
        s += n % 10
        n //= 10
    return s

def find_snuke(args):
    result = []
    i = 1
    while len(result) < args:
        push = True
        p = 0
        for power in range(0,len(str(i))):
            if((i+10**power)/snuke(i+10**power))<(i/snuke(i)):
                push = False
                p = power
                break
        if push:
            result.append(i)
        i=i+10**p
            
    return result

arr = find_snuke(args)
for a in arr:
   print(a)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def cost(l, r):
        if l + 2 == r:
            return aa[l] + aa[l + 1]
        if l + 1 == r:
            return 0
        if dp[l][r] != -1:
            return dp[l][r]
        res = 10 ** 10
        for m in range(l + 1, r):
            res = min(res, cost(l, m) + cost(m, r))
        res += cumsum_aa[r] - cumsum_aa[l]
        dp[l][r] = res
        return res

    n = int(input())
    aa = list(map(int, input().split()))
    dp = [[-1] * (n + 1) for _ in range(n + 1)]
    cumsum_aa = [0]
    for i, a in enumerate(aa):
        cumsum_aa.append(cumsum_aa[i] + a)
    print(cost(0, n))

main()


### FIXED CODE ###

def f(n, a):
    inf = float("inf")
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 2, -1, -1):
        s = a[i]
        dpi = dp[i]
        for j in range(i + 1, n):
            mn = inf
            s += a[j]
            for d in range(i, j):
                k = dpi[d] + dp[d + 1][j]
                if k < mn:
                    mn = k
            dpi[j] = mn + s
    return dp[0][-1]


n = int(input())
a = tuple(map(int, input().split()))
print(f(n, a))
### BUGGY CODE ###

from collections import deque

s = input()

grid = [0 if i == 'g' else 1 for i in s]


def biggest(grid):
    dist = [float('-inf')] * len(s)
    move = (0, 1)
    st = deque([[0, 0, 0, 0]])
    while st:
        g, p, idx, cur = st.popleft()
        if idx > len(s) - 1:
            continue
        for a in move:
            if a:
                if p + 1 > g:
                    continue
                tmpg, tmpp = g, p + 1
            else:
                tmpg, tmpp = g + 1, p
            if a > grid[idx]:
                tmp = cur + 1
            elif a < grid[idx]:
                tmp = cur - 1
            else:
                tmp = cur
            if dist[idx] < tmp:
                dist[idx] = tmp
            st.append([tmpg, tmpp, idx + 1, tmp])
    return dist[-1]


print(biggest(grid))


### FIXED CODE ###

s = input()
p = sum(1 for i in s if i == 'p')
l = len(s)
print(l // 2 - p)
### BUGGY CODE ###

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

h.append(9999)
dp = [[0]*(n+1) for _ in range(n)]

def do_dp():
  for i in range(1,n):
    for j in range(n-1):
      #print("i:{} j:{}".format(i, j))
      if dp[i][j+1] == 0:
        dp[i][j+1] = dp[i-1][j] + abs(h[j] - h[j+1])
      else:
        dp[i][j+1] = min(dp[i][j+1],dp[i-1][j] + abs(h[j] - h[j+1]))
      if dp[i][j+2] == 0:
        dp[i][j+2] = dp[i-1][j] + abs(h[j] - h[j+2])
      else:
        dp[i][j+2] = min(dp[i][j+2],dp[i-1][j] + abs(h[j] - h[j+2]))
      #print(dp)
  return dp[n-1][n-1]
  
r = do_dp()
print(r)

### FIXED CODE ###

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

dp=[0] * n
for i in range(1, n):
  if i - 2 < 0:
    dp[i] = dp[i-1] + abs(h[i] - h[i-1])
  else:
    dp[i] = min(dp[i-2]+abs(h[i] - h[i-2]) ,dp[i-1]+abs(h[i]-h[i-1]) )
  
print(dp[n-1])
### BUGGY CODE ###

n = int(input())

a = [int(input()) - 1 for _ in range(n)]

i = 0
count = 0

while(1):
  i = a[i]
  count += 1
  if i == 1:
    break
  elif i == 0:
    count = -1
    break
  
print(count)

### FIXED CODE ###

n = int(input())

a = [int(input()) - 1 for _ in range(n)]

i = 0
count = 0

for _ in range(n+1):
  i = a[i]
  count += 1
  if i == 1:
    break

if count == n + 1:
  count = -1
  
print(count)
### BUGGY CODE ###

N, K = map(int, input().split())
*A, = map(int, input().split())
ans = -float('inf')
for i in range(N - K + 1):
    ans = max(ans, max(sum(A[i: i+K]), 0) + sum([a for a in A[:i] + A[i+K:] if a > 0]))
print(ans)

### FIXED CODE ###

from itertools import accumulate

N, K = map(int, input().split())
*A, = map(int, input().split())
A_pos = list(map(lambda x: max(x, 0), A))
A_pos_cumsum = [0] + list(accumulate(A_pos))
ans = -float('inf')
S = sum(A[0: K])
for i in range(N - K + 1):
    ans = max(ans, max(S, 0) + A_pos_cumsum[i] + (A_pos_cumsum[-1] - A_pos_cumsum[i+K]))
    S = S - A[i] + A[i+K] if i < N - K else 0
print(ans)
### BUGGY CODE ###

def binomial(n, k):
    num = 1
    for i in range(1, min(k, n - k) + 1):
        num = ((num * n) // i) 
        n -= 1
    return num % (10**9 + 7)

x, y = [int(a) for a in input().split()]

n, rn = divmod(2 * x - y, 3)
m, rm = divmod(2 * y - x, 3)

if rn != 0 or rm != 0 or n < 0 or m < 0:
    ans = 0
else:
    a = (2 * x - y) // 3
    b = (2 * y - x) // 3
    ans = binomial(a + b, b)

print(ans)

### FIXED CODE ###

def binomial_p(n, k, p):
    '''
    Input: integers n, k such that n >= k >= 0, prime number p
    Output: n choose k mod p
    '''

    k = min(k, n-k)
    fct_n = 1  # factorial of n mod p = 1 * 2 * ... * n mod p
    inv = [0, 1] # inv[i] : inverse of i mod p
    invfct_k = 1 # factorial of inverse of k mod p = 1^(-1) * 2^(-1) * ... * k^(-1) mod p
    invfct_n_k = 1  # factorial of inverse of (n-k) mod p

    # Calculate inverse, factorial, factorial of inverse of i
    # all at the same time
    for i in range(2, n - k + 1):
        fct_n = (fct_n * i) % p
        inv.append(( inv[p % i] * (p - p//i) ) % p )
        invfct_n_k = invfct_n_k * inv[-1] % p
        if i == k:
            invfct_k = invfct_n_k

    for i in range(n - k + 1, n + 1):
        fct_n = (fct_n * i) % p

    return ((fct_n * invfct_k % p) * invfct_n_k) % p



x, y = [int(a) for a in input().split()]

n, rn = divmod(2 * x - y, 3)
m, rm = divmod(2 * y - x, 3)
p = 10**9 + 7

if rn != 0 or rm != 0 or n < 0 or m < 0:
    ans = 0
else:
    a = (2 * x - y) // 3
    b = (2 * y - x) // 3
    ans = binomial_p(a + b, b, p)

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

import sys
from functools import reduce
sys.setrecursionlimit(2000000001)

def solve(n,k,ar,dp,x):
	ab = abs; mn = min
	if x>=n-2: return dp[x]
	if not dp[x] is -1: return dp[x]
	t = (ab(ar[x]-ar[i])+solve(n,k,ar,dp,i) for i in range(x+1,mn(n,x+k+1)))
	dp[x] = reduce(lambda a,b : a if a < b else b,t)
	return dp[x]

def main():
	I = lambda:map(int,sys.stdin.readline().split())
	pr = lambda x:sys.stdout.write(f'{x}\n')
	n,k, ar = *I(), [*I()]
	dp = [-1]*(n-2) + [abs(ar[-2]-ar[-1]),0]
	pr(solve(n,k,ar,dp,0))

main()

### FIXED CODE ###

import sys
from functools import reduce
sys.setrecursionlimit(2000000001)

def solve(n,k,ar,dp,x):
	ab = abs; mn = min
	if x>=n-2: return dp[x]
	if not dp[x] is -1: return dp[x]
	# t = [ for i in range(x+1,mn(n,x+k+1))]
	t = map(lambda i:ab(ar[x]-ar[i])+solve(n,k,ar,dp,i), range(x+1,mn(n,x+k+1)))
	dp[x] = reduce(lambda a,b : a if a < b else b,t)
	return dp[x]

def main():
	I = lambda:map(int,sys.stdin.readline().split())
	pr = lambda x:sys.stdout.write(f'{x}\n')
	n,k, ar = *I(), [*I()]
	dp = [-1]*(n-2) + [abs(ar[-2]-ar[-1]),0]
	pr(solve(n,k,ar,dp,0))

main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
N = int(input())
edges = [[] for _ in range(N)]
cnt_edges = [0]*N
colors = [[0]*N for _ in range(N)]
A = []
K = 0
for i in range(N-1):
    a,b = [int(x) for x in input().split()]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

    cnt_edges[a-1]+=1
    cnt_edges[b-1]+=1
    A.append((a-1,b-1))
#%%
K = max(cnt_edges)

stk = [(0,0)]
seen = set()
while(stk):
    n,used_color = stk.pop()
    available_color = [i for i in range(1,K+1)]
    if(used_color!=0):
        available_color.remove(used_color)
    next_stk = []
    for next in edges[n]:
        if(next in seen):
            continue
        col = available_color.pop()
        next_stk.append((next,col))

        colors[next][n] = col
        colors[n][next] = col
    stk = next_stk + stk
    seen.add(n)

print(K)
for edge in A:
    a,b = edge
    col = colors[a][b]
    print(col)


### FIXED CODE ###

N = int(input())
edges = [[] for _ in range(N)]
cnt_edges = [0]*N
colors = [0]*(N-1)
di = {}
A = []
K = 0
for i in range(N-1):
    a,b = [int(x) for x in input().split()]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

    K=max(K,len(edges[a-1]),len(edges[b-1]))
    di[(a-1,b-1)] = i
    di[(b-1,a-1)] = i
    A.append((a-1,b-1))
#%%
#K = max(cnt_edges)

stk = [(0,0)]
seen = set()
while(stk):
    n,used_color = stk.pop()
    available_color = 1
    next_stk = []
    for next in edges[n]:
        if(next in seen):
            continue
        if(available_color == used_color):
            available_color += 1
        next_stk.append((next,available_color))
        i = di[(next,n)]
        colors[i] = available_color
        available_color += 1
    stk += next_stk
    seen.add(n)

print(K)
for col in colors:
    print(col)
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline

from collections import deque

def myinput():
    return map(int,readline().split())

h,w = myinput()
field = [ list(input()) for _ in range(h) ]

d = [ [float("inf")]*w for _ in range(h) ]
q = deque()

for j in range(h):
    for i in range(w):
        a = field[j][i]
        if a=="#":
            q.append([j,i])
            d[j][i] = 0
        else:
            pass

def bfs(d):
    m = 0
    while q:
        y,x = q.popleft()
        for j,i in ([1,0],[0,-1],[-1,0],[0,1]):
            ny = y + j
            nx = x + i
            if ny==-1 or nx==-1 or ny==h or nx==w:
                pass
            elif field[ny][nx]=="#":
                pass
            elif d[ny][nx]!=float("inf"):
                pass
            else:
                field[ny][nx] = "#"
                d[ny][nx] = d[y][x] + 1
                m = max(m,d[ny][nx])
                q.append([ny,nx])
    return m

m = bfs(d)
print(m)

### FIXED CODE ###

from collections import deque

h,w = map(int,input().split())
field = [ list(input()) for _ in range(h) ]

visited = [ [0]*w for _ in range(h) ]
q = deque()

for j in range(h):
    for i in range(w):
        a = field[j][i]
        if a=="#":
            q.append([j,i,0])
            visited[j][i] = 1
        else:
            pass

m = 0
while q:
    y,x,d = q.popleft()
    for j,i in ([1,0],[0,-1],[-1,0],[0,1]):
        ny = y + j
        nx = x + i
        if ny==-1 or nx==-1 or ny==h or nx==w:
            pass
        elif visited[ny][nx]==0:
            visited[ny][nx] = 1
            q.append([ny,nx,d+1])
            m = max(m,d+1)   
print(m)
### BUGGY CODE ###

n,P = map(int,input().split())
#i = 2
from collections import defaultdict
dic = defaultdict(int)
# 約数分解
i = 2
N = P
while i*i <= N:
    if N%i != 0:
        continue
    num = 0
    while N%i == 0:
        num += 1
        N//=i
    dic[i] = num
if N != 1:
    dic[N] = 1
ans = 1
if n == 1:
    print(P)
else:
    for k,v in dic.items():
        #print(k*(v//n))
        if v//n >= 1:
            ans *= k ** (v//n)
    print(ans)


### FIXED CODE ###

n,P = map(int,input().split())
#i = 2
from collections import defaultdict
dic = defaultdict(int)
# 約数分解
if n == 1:
    print(P)
    exit()
i = 2
N = P
while i*i <= N:
    #print(i,N)
    if N%i != 0:
        i += 1
        continue
    num = 0
    while N%i == 0:
        num += 1
        N//=i
    dic[i] = num
    i += 1
if N != 1:
    dic[N] = 1
ans = 1
for k,v in dic.items():
    if v//n >= 1:
        ans *= k ** (v//n)
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
mod = 10**9+7
base = [(2**i)%mod for i in range(63,-1,-1)]

count = [0 for i in range(64)]
for i in range(N):
  b = list(map(int, list(bin(A[i])[2:])))
  b = [0]*(64-len(b))+b
  for j in range(64):count[j]+=b[j]

print(sum([base[i]*count[i]*(N-count[i]) for i in range(64)])%mod)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
mod = 10**9+7
base = [(2**i)%mod for i in range(63,-1,-1)]

count = [0 for i in range(64)]
for i in range(N):
  b = list(map(int, list(bin(A[i])[2:])))
  b = [0]*(64-len(b))+b
  for j in range(64):count[j]+=b[j]

print(sum([base[i]*count[i]*(N-count[i]) for i in range(64)])%mod)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

def main():
    def _fibonacci(n):
        if n == 0:
            return 1
        elif n == 1:
            return 1
        else:
            return _fibonacci(n - 1) + _fibonacci(n - 2)

    N = int(raw_input())
    return _fibonacci(N)


print main()

### FIXED CODE ###

# -*- coding: utf-8 -*-

def main():
    def _fibonacci(n,cache):
        if n in cache:
            return cache[n]

        elif n == 0 or n == 1:
            ret = 1
            cache[n] = ret
            return ret
        else:
            ret = _fibonacci(n - 1, cache) + _fibonacci(n - 2, cache)
            cache[n] = ret
            return ret

    N = int(raw_input())
    cache = {}
    return _fibonacci(N,cache)

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

N=int(input())
li=list(map(int,input().split()))
Ans=True

for i in range(N):
    for j in range(N):
        if i<=j:
            pass
        else:
            if li[i]==li[j]:
                Ans=False
                break
            else:
                pass

if Ans==True:
    print("YES")
else:
    print("NO")


### FIXED CODE ###

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

for i in range(N-1):
    if A[i]!=A[i+1]:
        ans+=1
    else:
        break

if ans+1==N:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

N = int(input())
S = input()

A = [0]*1000 
ans = 0

for i in range(1000):
  if i < 10:
    s = '00' + str(i)
  elif i < 100:
    s = '0' + str(i)
  else:
    s = str(i)
    
  for j in range(N):
    if S[j] == s[0]:
      for k in range(j+1,N):
        if S[k] == s[1]:
          for l in range(k+1,N):
            if S[l] == s[2]:
              A[i] = 1
              break
        elif A[i] == 1:
          break
    elif A[i] == 1:
      break

print(A.count(1))

### FIXED CODE ###

N = int(input())
S = input()

A = [0]*1000 
ans = 0

for i in range(1000):
  if i < 10:
    s = '00' + str(i)
  elif i < 100:
    s = '0' + str(i)
  else:
    s = str(i)
    
  for j in range(N):
    if S[j] == s[0]:
      for k in range(j+1,N):
        if S[k] == s[1]:
          for l in range(k+1,N):
            if S[l] == s[2]:
              A[i] = 1
              break
          break
      break

print(A.count(1))
### BUGGY CODE ###

M=10**9+7;N,K=map(int,input().split())
def c(n,k,m=1,d=1):
 for i in range(k):m*=n-i;d*=i+1
 return(k<=n)*m%M*pow(d%M,M-2,M)%M
for i in range(K):print(c(K-1,i)*c(N-K+1,i+1)%M)

### FIXED CODE ###

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


def combmod(n, k):
    if k > n - k:
        k = n - k
    num, den = 1, 1
    for i in range(k):
        num = num * (n - i) % M
        den = den * (i + 1) % M
    inv_dev = pow(den, M - 2, M)
    return num * inv_dev % M


for i in range(1, K + 1):
    if i <= N - K + 1:
        print(combmod(K - 1, i - 1) * combmod(N - K + 1, i) % M)
    else:
        print(0)
### BUGGY CODE ###

from pprint import pprint
from collections import deque, defaultdict

n, q = list(map(int, input().strip().split(" ")))
edges = defaultdict(set)
for _ in range(n-1):
    a_i, b_i = list(map(int, input().strip().split(" ")))
    # edges[a_i-1].append(b_i-1)
    # edges[b_i-1].append(a_i-1)
    edges[a_i-1].add(b_i-1)
    edges[b_i-1].add(a_i-1)

# p = defaultdict(int)
p = [0] * n
x = []
for _ in range(q):
    p_i, x_i = list(map(int, input().strip().split(" ")))
    p[p_i-1] += x_i

# counter = defaultdict(int)
counter = [0] * n

parents = deque()
# parents.append(0)
# parents = []
parents.append(0)
visited = set()
while parents:
    parent = parents.popleft()
    # parent = parents.pop()
    if parent in visited:
        continue
    visited.add(parent)
    counter[parent] += p[parent]
    # print("parent")
    # print(parent, counter[parent])
    for child in edges[parent]:
        if child in visited:
            continue
        # if counter[child] != 0:
        #    continue
        counter[child] += counter[parent]
        # print("child")
        # print(child, counter[child])
        parents.append(child)
        # parents.add(child)

#print(" ".join(list(map(str, counter.values()))))
print(" ".join(list(map(str, counter))))

### FIXED CODE ###

from collections import deque


def solve(n, q, a, b, p, x):
    counter = [0] * n
    q_sum = [0] * n
    for i in range(q):
        q_sum[p[i]] += x[i]
    # pprint(q_sum)

    edges = {}
    for i in range(n-1):
        if a[i] not in edges:
            edges[a[i]] = []
        edges[a[i]].append(b[i])
    # pprint(edges)

    counter[0] = q_sum[0]
    children = deque()
    for child in edges[0]:
        counter[child] = q_sum[0]
        children.append(child)
    while children:
        child = children.popleft()
        counter[child] += q_sum[child]
        # print("child")
        # print(child, counter[child])
        if child in edges:
            for c in edges[child]:
                counter[c] = counter[child]
                # print("c")
                # print(c, counter[c])
                children.append(c)

    print(" ".join(list(map(str, counter))))

if __name__ == "__main__":
    n, q = list(map(int, input().strip().split(" ")))
    a = []
    b = []
    for _ in range(n-1):
        a_i, b_i = list(map(int, input().strip().split(" ")))
        a.append(a_i - 1)
        b.append(b_i - 1)

    p = []
    x = []
    for _ in range(q):
        p_i, x_i = list(map(int, input().strip().split(" ")))
        p.append(p_i-1)
        x.append(x_i)
    solve(n, q, a, b, p, x)
### BUGGY CODE ###

L = input()
p = 10 ** 9 + 7
ans = 0
b = 0
n = len(L)
while n > 0:
  ans += (3 ** (n - 1)) * (2 ** b)
  ans %= p
  n -= 1
  b += 1
  if n == 0:
    break
  while n and L[len(L) - n] == '0':
    n -= 1
ans += 2 ** b
ans %= p
print(ans)

### FIXED CODE ###

L = input()
p = 10 ** 9 + 7
l = len(L)
ones = 0
cnt = 1
two = [1] * l
three = [1] * l
for i in range(1, l):
  two[i] = two[i - 1] * 2 % p
  three[i] = three[i - 1] * 3 % p
for i, b in enumerate(L):
  if b == '1':
    left = two[ones]
    right = (three[l - 1 - i] + 1) % p
    cnt += left * right
    cnt %= p
    ones += 1
print(cnt)