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

import sys
sys.setrecursionlimit(10 ** 6)

n = int(input())
x = input()
z = '1' * n
o = '0' * n
X = int(x, 2)

if (z == x):
  u = n - 1
  d = n - 1
elif (o == x):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def toggle(i):
  if (i == '1'):
    return '0'
  else:
    return '1'


def solve(i, count):
  if (i <= 2 * 10**5 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= 2 * 10**5):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (2 * 10 ** 5 + 1)
for i in range(1, 2 * 10 ** 5 + 1):
  ans[i] = solve(i, 0)
for i in range(n):  
  if(x[i] == '0'):
    print(solve2(X + 2 ** (n-i-1), u))
  else:
    print(solve2(X - 2 ** (n-i-1), d))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

n = int(input())
x = input()
z = '1' * n
o = '0' * n
X = int(x, 2)

if (n == 1 and x == '1'):
  print(0)
  exit()

if (z == x):
  u = n - 1
  d = n - 1
elif (o == x):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def solve(i, count):
  if (i <= 2 * 10**5 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= 2 * 10**5):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (2 * 10 ** 5 + 4)
_u = (2 * 10 ** 5) // u
U = X % u + (u * _u) + u
if(d != 0):
  _d = (2 * 10 ** 5) // d
  D = X % d + (d * _d) * 2 + d * 2
Us = [0] * (2 * 10 ** 5)
Ds = [0] * (2 * 10 ** 5)
for i in range(1, 2 * 10 ** 5 + 4):
  ans[i] = solve(i, 0)
Us[0] = 1 % u
if(d != 0):
  Ds[0] = 1 % d
for i in range(1, 2 * 10 ** 5):
  Us[i] = (Us[i - 1] * 2) % u
  if(d != 0):
    Ds[i] = (Ds[i-1] * 2) % d

for i in range(n):
  if(x[i] == '0'):
    print(solve2(U + Us[n-i-1], u))
  else:
    if (d == 0):
      print(0)
    else:
      print(solve2(D - Ds[n-i-1], d))
### BUGGY CODE ###

n, k = map(int, input().split())
*p, = map(int, input().split())
p = [v - 1 for v in p]
*c, = map(int, input().split())
minc = min(c)

ans = minc
for i in range(n):
    score = minc
    cur_score = 0
    pos = i
    for j in range(1, k + 1):
        pos = p[pos]
        cur_score += c[pos]
        score = max(cur_score, score)
    ans = max(ans, score)
print(ans)




### FIXED CODE ###

n, k = map(int, input().split())
*p, = map(int, input().split())
p = [v - 1 for v in p]
*c, = map(int, input().split())
minc = float('-inf')

ans = minc


def get_loop(i):
    pos = i
    cnt = 0
    cur_score = 0
    while cnt == 0 or pos != i:
        pos = p[pos]
        cur_score = cur_score + c[pos]
        cnt += 1
    return cnt, cur_score

# print(get_loop(2))

def solve(pos, k):
    score = minc
    cur_score = 0
    loop_length, loop_score = get_loop(pos)
    if k >= 2 * loop_length and loop_score > 0:
        # print("%s: %s // %s, %s, %s" % (i, k, loop_length, cur_score, max_loop_score))
        cur_score = loop_score * ((k - loop_length) // loop_length)
        score = max(cur_score, score)
        k = k % loop_length + loop_length
    else:
        k = min(k, 2 * loop_length)
    for _ in range(k):
        pos = p[pos]
        cur_score += c[pos]
        score = max(cur_score, score)
    # print("%s: %s" % (i, score))
    return score

for i in range(n):
    ans = max(ans, solve(i, k))
print(ans)
### BUGGY CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
a = li()
a.sort()

s = sum(a)

q = ii()

from bisect import bisect_left, bisect_right
def bisect_find(a, x):
    i = bisect_left(a, x)
    if i == len(a):
        return -1
    elif a[i] != x:
        return -1
    return i

def bisect_r_find(a, x):
    i = bisect_right(a, x)
    # if i == len(a):
    #     return -1
    return i

for i in range(q):
    b,c = mi()


    # 左を探す
    l = bisect_find(a,b)
    # 右を探す
    if l != -1:
        r = bisect_r_find(a[l:],b) + l
        # 個数をカウント
        count = r-l
        # 前回の合計との差を求める
        s = s + (c-b)*count

        # 配列を上書き
        a[l:r] = [c]*count
        a.sort()
    # print('-------------ans----------------',s)
    print(s)



    

### FIXED CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
a = li()
q = ii()

s = sum(a)

m = [0] * (10**5 + 1)
for i in range(n):
    m[a[i]] += 1

for i in range(q):
    b,c = mi()

    if m[b] == 0:
        print(s)
    else:
        count = m[b]

        s = s + (c-b)*count
        print(s)

        m[c] += count
        m[b] = 0
### BUGGY CODE ###

#!/usr/bin/env python3
from itertools import combinations
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
MOD = 10**9 + 7

n = int(input())
cost = []
for i in range(n):
    cost.append([int(item) for item in input().split()])
score = [0] * 2**n
for i in range(1, 2**n):
    lsb = i & -i
    index = lsb.bit_length() - 1
    other = i ^ lsb
    diff = 0
    for j in range(n):
        if other & 1 << j:
            diff += cost[index][j]
    score[i] = score[other] + diff

memo = [-1] * 2**n
memo[0] = 0
for i in range(n):
    memo[1<<i] = 0

def dfs(st):
    if memo[st] != -1:
        return memo[st]
    sst = st
    val = score[st] 
    while True:
        sst = (sst - 1) & st
        if sst == 0:
            break
        val = max(val, dfs(sst) + dfs(sst ^ st))
    memo[st] = val
    return val

ret = dfs(2**n - 1)
print(ret)

### FIXED CODE ###

#!/usr/bin/env python3
from itertools import combinations
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
MOD = 10**9 + 7

n = int(input())
cost = []
for i in range(n):
    cost.append([int(item) for item in input().split()])
score = [0] * 2**n
for i in range(1, 2**n):
    lsb = i & -i
    index = lsb.bit_length() - 1
    other = i ^ lsb
    diff = 0
    for j in range(n):
        if other & 1 << j:
            diff += cost[index][j]
    score[i] = score[other] + diff

memo = [-1] * 2**n
memo[0] = 0
for i in range(n):
    memo[1<<i] = 0

def dfs(st):
    if memo[st] != -1:
        return memo[st]
    sst = st
    val = score[st] 
    while True:
        sst = (sst - 1) & st
        if sst == 0:
            break
        val = max(val, dfs(sst) + dfs(sst ^ st))
    memo[st] = val
    return val

ret = dfs(2**n - 1)
print(ret)
### BUGGY CODE ###

import math
N = int(input())
my_list = [None] * N
for i in range(N):
    s_i = input()
    my_dict = {}
    for j in range(10):
        if s_i[j] in my_dict:
            my_dict[s_i[j]] += 1
        else:
            my_dict[s_i[j]] = 1
    my_list[i] = my_dict
sum = 0
trash = []
for i in range(N - 1):
    if i in trash:
        continue
    num = 0
    a = 0
    for j in range(i + 1, N):
        if my_list[i] == my_list[j]:
            num += 1
            trash.append(j)
    for j in range(1, num + 1):
        a += j
    sum += a
print(sum)


### FIXED CODE ###

n = int(input())
dict = {}
ans = 0

for i in range(n):
    s = str(sorted(input()))
    if s in dict.keys():
        ans += dict[s]
        dict[s] += 1
    else:
        dict[s] = 1
print(ans)
### BUGGY CODE ###

num=int(input())
word=str(input())
n_th = 3*10^5
for i in range(num):
	n=0
	for a in word[:i]:
		if a == 'W':
			n += 1
	for a in word[i+1:]:
		if a == 'E':
			n +=1
	if n_th > n:
		n_th = n
print ( n_th)

### FIXED CODE ###

num=int(input())
word=str(input())
w=[0]
e=[0]
if word[0]=='W':
	w=[1]
	e=[0]
else:
	w=[0]
	e=[1]
for i in range(1,num):
	if word[i]=='W':
		w.append(w[i-1]+1)
		e.append(e[i-1])
	else:
		w.append(w[i-1])
		e.append(e[i-1]+1)
n_th=e[num-1]
for i in range(1,num):
	n=w[i-1]+e[num-1]-e[i]
	if n_th>n:
		n_th=n

print (n_th)
### BUGGY CODE ###

n,k=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))
m=min(C)
score_max=m
for L in range(n):
  score=0
  d=[0]*n
  r=0
  d[L]=1
  for i in range(k):
    r+=1
    L=P[L]-1
    score+=C[L]
    score_max=max(score,score_max)
    if d[L]==0:
      d[L]=1
    elif score<0:
      break
    else:
      roop=k//r
      score = score*roop
      score_max=max(score,score_max)
      h=k%r
      for j in range(h):
        L=P[L]-1
        score+=C[L]
        score_max=max(score,score_max)
      break
print(score_max)


### FIXED CODE ###

n,k=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))
score_max=max(C)
#スタート地点＝L
for L in range(n):
  score=0
  d=[0]*n
  r=0
  d[L]=1
  #k回移動する
  for _ in range(k):
    r+=1#移動回数をカウント
    L=P[L]-1#移動先の位置
    score+=C[L]
    score_max=max(score,score_max)
    #もしも移動した場所に未到達なら...
    if d[L]==0:
      d[L]=1
    #Cの最小値未満ならスコアは減り続けるのでbreak
    elif score<0:
      break
    else:
      roop=(k//r)-1
      #最後の1周と端数は一個ずつ見る
      h=(k%r)+r
      score*=roop
      score_max=max(score,score_max)

      #あまりの移動回数の処理
      for _ in range(h):
        L=P[L]-1
        score+=C[L]
        score_max=max(score,score_max)
      break
print(score_max)
### BUGGY CODE ###

k = int(input())
q = []
for i in range(1, 10):
    q.append(i)
for i in range(k):
    x = q.pop(0)
    if x % 10 != 0:
        q.append(10 * x + x % 10 - 1)
    q.append(10 * x + x % 10)
    if x % 10 != 9:
        q.append(10 * x + x % 10 + 1)

print(x)


### FIXED CODE ###

from collections import deque


k = int(input())
q = deque(range(1, 10))

for i in range(k):
    x = q.popleft()
    if x % 10 != 0:
        q.append(10 * x + x % 10 - 1)
    q.append(10 * x + x % 10)
    if x % 10 != 9:
        q.append(10 * x + x % 10 + 1)

print(x)
### BUGGY CODE ###

n, k = map(int, input().strip().split())
p = list(map(int, input().strip().split()))

def calc_exp(n):
    exp=1+(n-1)*0.5
    return exp

mx=0
for i in range(n-k+1):
    tmp=sum(p[i:i+k])
    if mx<tmp:
        ind=i
        mx=tmp
        
ans=0
for i in range(k):
    ans+=calc_exp(p[ind+i])
    
print(ans)


### FIXED CODE ###

n, k = map(int, input().strip().split())
p = list(map(int, input().strip().split()))

def calc_exp(n):
    exp=1+(n-1)*0.5
    return exp

tmp=sum(p[:k])
mx=tmp
ind=0
for i in range(1,n-k+1):
    # tmp=sum(p[i:i+k])
    tmp-=p[i-1]
    tmp+=p[i+k-1]
    if mx<tmp:
        ind=i
        mx=tmp
        
ans=0
for i in range(k):
    ans+=1+(p[ind+i]-1)*0.5
    
print(ans)
### BUGGY CODE ###



global N,K
global ws

def check(max_p):
    track=0
    now=0
    for i in range (N):
        if(ws[i]>max_p):return False
        if(now+ws[i]>max_p):
            track+=1
            now=ws[i]
        else:
            now+=ws[i]
    if now>0:
        track+=1
    if(track>K):
        return False
    else:
        return True

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

ans=0
now=0
ws=[]
for i in range(N):
    w=int(input())
    ws.append(w)

amin=0
amax=int(1E100)

while amin+1!=amax:
    amid=(amin+amax)//2
    if(check(amid)):
        amax=amid
    else:
        amin=amid
print(amax)
   

### FIXED CODE ###



global N,K
global ws

def check(max_p):
    track=0
    now=0
    for i in range (N):
        if(ws[i]>max_p):return False
        if(now+ws[i]>max_p):
            track+=1
            now=ws[i]
        else:
            now+=ws[i]
    if now>0:
        track+=1
    if(track>K):
        return False
    else:
        return True

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

ans=0
now=0
ws=[]
for i in range(N):
    w=int(input())
    ws.append(w)

amin=0
amax=int(1E48)

while amin+1!=amax:
    amid=(amin+amax)//2
    if(check(amid)):
        amax=amid
    else:
        amin=amid
print(amax)
### BUGGY CODE ###

import math

n = int(input())

for i in range(1, n + 1):
    cnt = 0
    
    for x in range(1, i+1):
        if x ** 2 > i:
            break
        for y in range(1, i+1):
            if y ** 2 > i:
                break
            
            try:
                z = (math.sqrt(4 * i - 3 * y ** 2 - 2 * x * y - 3 * x ** 2) - x - y) / 2
            
            except:
                continue

            if z > 0 and z.is_integer():
                cnt += 1

    print(cnt)

### FIXED CODE ###

#!/usr/bin/env python3
import math

n = int(input())
arr = [0] * n

for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            ans = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
            if ans <= n:
                arr[ans - 1] += 1

for i in range(n):
    print(arr[i])
### BUGGY CODE ###

import collections

n = int(input())
graph = [[] for i in range(n + 1)]
edge = []
for i in range(n - 1):
    a, b = map(int, input().split())
    edge.append((a, b))
    graph[a].append(b)
    graph[b].append(a)
color = [None for i in range(n - 1)]
queue = collections.deque([[1, 0]])
while queue:
    temp = queue.popleft()
    num = temp[0]
    prev = temp[1]
    if prev:
        col = color[edge.index((min(num, prev), max(num, prev)))]
    else:
        col = 0
    count = 1
    for i in graph[num]:
        a, b = min(i, num), max(i, num)
        temp = edge.index((a, b))
        if color[temp] != None:
            continue
        else:
            if count == col:
                color[temp] = count + 1
                count += 2
            else:
                color[temp] = count
                count += 1
            queue.append([i, num])
print(max(color))
for i in range(n - 1):
    print(color[i])

### FIXED CODE ###

import collections

n = int(input())
graph = [[] for i in range(n + 1)]
edge = []
for i in range(n - 1):
    a, b = map(int, input().split())
    edge.append((a, b))
    graph[a].append(b)
    graph[b].append(a)
color = {}
queue = collections.deque([(1, 0)])
while queue:
    temp = queue.popleft()
    num = temp[0]
    prev = temp[1]
    if prev:
        col = color[(prev, num)]
    else:
        col = 0
    count = 1
    for i in graph[num]:
        a, b = min(i, num), max(i, num)
        if (a, b) in color.keys():
            continue
        else:
            if count == col:
                color[(a, b)] = count + 1
                count += 2
            else:
                color[(a, b)] = count
                count += 1
            queue.append((i, num))
print(max([len(graph[i]) for i in range(n + 1)]))
for i, j in edge:
    print(color[(i, j)])
### BUGGY CODE ###

N=int(input());tt=0
while(N):
    tt+=(N%10);N//=10
    if tt>999999999:break
print("No" if tt%9 else "Yes")

### FIXED CODE ###

print("No"if int(input())%9 else "Yes")
### BUGGY CODE ###

s = input()
k = int(input())

d = set()

for i in range(len(s)):
    for j in range(len(s)):
        d.add(s[i:j + 1])
l = list(d)
l.sort()
# print(l)
if l[0] == '':
    l = l[1:]

print(l[k-1])


### FIXED CODE ###

s = input()

d = ["z"*5010]*5

k = int(input())
for i in range(len(s)):
    for j in range(i, i+k):
        x = s[i:j+1]
        if x in d or x == '':
            continue
        l = 0
        while l < 5 and x > d[l]:
            l += 1
        # print(k, d[0:k], x, d[k:])
        if l < 5:
            d = d[0:l] + [x] + d[l:]
            d = d[0:5]
        # print(f"->{d}")
# l = list(d)
# l.sort()
# print(l)
# if l[0] == '':
    # l = l[1:]

print(d[k-1])
### BUGGY CODE ###

from time import time
stime = time()

from copy import copy
from random import randint

def get_fav_contest(s, t):
    s = copy(s)
    t = copy(t)
    dc = 0
    d = len(t)
    for i in range(1, d):
        dc += s[i][t[i]]
        ca[t[i]] = i
        dc -= sum([c[i2] * (i - ca[i2]) for i2 in range(1, 27)])
    return dc

d = int(input())
c = [0] + list(map(int, input().split(' ')))

s = [[]] + [[0] + list(map(int, input().split(' '))) for _ in range(d)]

t = 0 # 算出結果
tl = [0]

ca = [0] * (1 + 26) # 放置された不満の数々
cat = [] # 不満度の最適な算出のための一時配列
cat2 = []

for i in range(1, d + 1):
    cat = [0]
    for i2 in range(1, 27):
        cat2 = copy(ca)
        cat2[i2] = i
        cat.append(s[i][i2] + sum(c[i3] * (i - ca[i3]) for i3 in range(1, 27)))
    t = cat.index(max(cat))
    ca[t] = i
    tl.append(t)

default_t = get_fav_contest(s, tl)

ch = 0 # 適当に選んだ日
temp1 = 0 # 一時的に保存する場所
while time() - stime < 2:
    ch = randint(1, 365)
    temp1 = tl[ch]
    tl[ch] = randint(1, 26)
    if get_fav_contest(s, tl) < default_t:
        tl[ch] = temp1
print('\n'.join(map(str, tl[1:])))

### FIXED CODE ###

d = int(input())
c = [0] + list(map(int, input().split(' ')))

s = [[]] + [[0] + list(map(int, input().split(' '))) for _ in range(d)]

t = 0 # 算出結果

ca = [0] * (1 + 26) # 放置された不満の数々
cat = [] # 不満度の最適な算出のための一時配列
dc = 0 # カレントな満足度
#dl = [] # 満足度のログ

for i in range(1, d + 1):
    cat = [c[i2] * (i - ca[i2]) for i2 in range(1, 27)]
    t = cat.index(min(cat)) + 1
    dc += s[i][t]
    ca[t] = i
    dc -= sum(cat)
    print(t)
### BUGGY CODE ###

import bisect
import sys
input = sys.stdin.readline


N = int(input())
alist = list(map(int, input().split()))
Q = int(input())
BC = [list(map(int, input().split())) for _ in range(Q)]


alist.sort()
sumA = sum(alist)
for b, c in BC:
    idx_bl = bisect.bisect_left(alist, b)
    idx_br = bisect.bisect_right(alist, b)

    alist = alist[:idx_bl] + alist[idx_br:]
    idx_cl = bisect.bisect_left(alist, c)
    alist = alist[:idx_cl] + [c] * (idx_br - idx_bl) + alist[idx_cl:]

    sumA -= (idx_br - idx_bl) * (b - c)
    print(sumA)


### FIXED CODE ###

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


N = int(input())
alist = list(map(int, input().split()))
Q = int(input())


sumA = sum(alist)
adict = Counter(alist)

for _ in range(Q):
    b, c = map(int, input().split())

    if b not in adict:
        print(sumA)
        continue

    bnum = adict.pop(b)
    if c in adict:
        adict[c] += bnum
    else:
        adict[c] = bnum

    sumA -= bnum * (b - c)
    print(sumA)
### BUGGY CODE ###

N = int(input())
X = input()
def popcount(k):
    return bin(k).count('1')

K = int(X, 2)
one = popcount(K)
if one == 0:
    K_MOD = K
elif one == 1:
    K_MOD   = 0
    K_MOD_M = K
else:
    K_MOD   = K % one
    K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)
#memo = [-1] * (N+1)
#print('k_mod_m=', K_MOD_M)
#print('k_mod_p=', K_MOD_P)
T = 2**(N-1)
for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T
    else:
        pop = one + 1
        k = K_MOD_P + T
    T //= 2

    if pop == 0:
        print(0)
    else:
        k %= pop
        pop = popcount(k)
        #key = k
        cnt = 1
        while k > 0:
            #print('  ', k, pop, cnt)
            #if memo[key] > 0:
            #    cnt += memo[k]
            #    break
            #else:
            k %= pop
            pop = popcount(k)
            cnt += 1
        #memo[key] = cnt
        print(cnt)


### FIXED CODE ###

N = int(input())
X = input()
memo = [-1] * (N+1)
memo[0] = 0

def popcount(k):
    return bin(k).count('1')

def calc(k):
    pop = popcount(k)
    #print('  ', k, pop)
    key = k
    if memo[key] < 0:
        k %= pop
        if k == 0:
            memo[key] = 1
        else:
            memo[key] = calc(k) + 1
    return memo[key]

K = int(X, 2)
one = popcount(K)
if one == 0:
    K_MOD = K
elif one == 1:
    K_MOD   = 0
    K_MOD_M = K
else:
    K_MOD   = K % one
    K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)

T_M = [1]*(N+1)
T_P = [1]*(N+1)
for i in range(1,N+1):
    if one > 1:
        T_M[i] = (T_M[i-1]*2) % (one-1)
    T_P[i] = (T_P[i-1]*2) % (one+1)

for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T_M[N-i-1]
    else:
        pop = one + 1
        k = K_MOD_P + T_P[N-i-1]

    if pop == 0:
        print(0)
    else:
        k %= pop
        print(calc(k)+1)
### BUGGY CODE ###

n = int(input())
print(sum((range(1,n))))

### FIXED CODE ###

n = int(input())
print(n*(n-1)//2)
### BUGGY CODE ###

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

for _ in range(Q):
  B, C = map(int, input().split())
  for i in range(N):
    if A[i] == B:
      A[i] = C
  print(sum(A))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
cnt = [0]*(10**5+1)

s = sum(A)
for i in A:
  cnt[i] += 1

for _ in range(Q):
  B, C = map(int, input().split())
  s += (C-B)*cnt[B]
  print(s)
  cnt[C] += cnt[B]
  cnt[B] = 0
### BUGGY CODE ###

l=list(input())
n=len(l)
p=10**9+7
ans=0
d=0
for i in range(n):
    if l[i]=="1":
        x=n-i-1
        k=x//p
        m=x%p
        K=d//p
        M=d%p
        ans+=((3**(k+m))%p)*((2**(K+M))%p)
        d+=1
    else:
        continue
ans+=2**d
print(ans%p)



### FIXED CODE ###

l=list(input())
n=len(l)
p=10**9+7
dp1=[0]*n
dp2=[0]*n
dp1[0]=1
dp2[0]=2
for i in range(1,n):
    if l[i]=="1":
        dp1[i]=(3*dp1[i-1]+dp2[i-1])%p
        dp2[i]=(dp2[i-1]*2)%p
    else:
        dp1[i]=(3*dp1[i-1])%p
        dp2[i]=dp2[i-1]
print((dp1[n-1]+dp2[n-1])%p)
### BUGGY CODE ###

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

def gcd(a,b):
    if a>b:
        a,b = b,a
    if b%a == 0:
        return a
    return gcd(a,b%a)

n = gcd(a,b)
m = n
x = 2
ans = 1

while m!=1:
    if m%x !=0:
        if x==2:
            x += 1
        else:
            x += 2
        continue
    ans += 1
    while m%x == 0:
        m /= x
    if x==2:
        x += 1
    else:
        x += 2

print(ans)

### FIXED CODE ###

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

def gcd(a,b):
    if a>b:
        a,b = b,a
    if b%a == 0:
        return a
    return gcd(a,b%a)

n = gcd(a,b)
m = n
ans = 1

if m%2==0:
    ans += 1
    while m%2==0:
        m //= 2
f = 3

while f*f <= n:
    if m%f==0:
        ans += 1
        while m%f==0:
            m //= f
    f+=2

if m!=1:
    ans += 1

print(ans)