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

import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

S = input()
T = input()
ls = len(S)+1
lt = len(T)+1

dp = dp2(0, ls, lt)

moji = [['']*ls for i in range(lt)]
#print(moji)

for i in range(1, lt):
    for j in range(1, ls):
        if S[j-1]==T[i-1]:
            dp[i][j] = dp[i-1][j-1]+1
            moji[i][j] = moji[i-1][j-1] + S[j-1]
        else:
            #print(i, j)
            if dp[i-1][j] >= dp[i][j-1]:
                dp[i][j] = dp[i-1][j]
                moji[i][j] = moji[i-1][j]
            else:
                dp[i][j] = dp[i][j-1]
                moji[i][j] = moji[i][j-1]

print(moji[lt-1][ls-1])

### FIXED CODE ###

import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

S = input()
T = input()
ls = len(S)+1
lt = len(T)+1

dp = dp2(0, ls, lt)

#moji = [['']*ls for i in range(lt)]
#print(moji)
for i in range(1, lt):
    for j in range(1, ls):
        if S[j-1]==T[i-1]:
            dp[i][j] = dp[i-1][j-1]+1
            #moji[i][j] = moji[i-1][j-1] + S[j-1]
        else:
            if dp[i-1][j] >= dp[i][j-1]:
                dp[i][j] = dp[i-1][j]
                #moji[i][j] = moji[i-1][j]
            else:
                dp[i][j] = dp[i][j-1]
                #moji[i][j] = moji[i][j-1]
#print(moji)
#print(moji[lt-1][ls-1])
ans = ''
i = lt-1
j = ls-1
while i > 0 and j > 0:
    if dp[i][j] > dp[i-1][j-1] and S[j-1]==T[i-1]:
        ans += S[j-1]
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        j -= 1

print(ans[::-1])
### BUGGY CODE ###

import bisect
q=int(input())
P=[2]
for i in range(3,10**5+2):
  for j in range(len(P)):
    if i%P[j]==0:
      break
    if j==len(P)-1:
      P.append(i)
p=set(P)
A=[]
for i in range(len(P)):
  if (P[i]+1)//2 in p:
    A.append(P[i])
for i in range(q):
  a,b=map(int,input().split())
  print(bisect.bisect_right(A,b+1,lo=0,hi=len(A))-bisect.bisect_right(A,a-1,lo=0,hi=len(A)))

### FIXED CODE ###

import bisect
q=int(input())
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
P=primes(10**5+3)
p=set(P)
A=[]
for i in range(len(P)):
  if (P[i]+1)//2 in p:
    A.append(P[i])
for i in range(q):
  a,b=map(int,input().split())
  print(bisect.bisect_right(A,b+1,lo=0,hi=len(A))-bisect.bisect_right(A,a-1,lo=0,hi=len(A)))
### BUGGY CODE ###

import random
def score(D,c,s,t):
    v=list()
    last=[0]*26
    legacy=0
    for i in range(D):
        minus=0
        v.append(legacy)
        v[i]+=s[i][t[i]-1]
        last[t[i]-1]=i+1
        for j in range(26):
            minus+=c[j]*(i+1-last[j])
        v[i]-=minus
        legacy=v[i]
    return v[D-1]
s=list()
t=list()
D=int(input())
c=list(map(int,input().split()))
for i in range(D):
    s.append(list(map(int,input().split())))
t=[random.randint(1,26)]*D
for i in range(1000):
    d=random.randint(1,D)
    q=random.randint(1,26)
    old=t[d-1]
    oldscore=score(D,c,s,t)
    t[d-1]=q
    if score(D,c,s,t)<oldscore:
        t[d-1]=old
print(score(D,c,s,t))

### FIXED CODE ###

import random
def score(D,c,s,t):
    v=list()
    last=[0]*26
    legacy=0
    for i in range(D):
        minus=0
        v.append(legacy)
        v[i]+=s[i][t[i]-1]
        last[t[i]-1]=i+1
        for j in range(26):
            minus+=c[j]*(i+1-last[j])
        v[i]-=minus
        legacy=v[i]
    return v[D-1]
s=list()
t=list()
D=int(input())
c=list(map(int,input().split()))
for i in range(D):
    s.append(list(map(int,input().split())))
t=[random.randint(1,26)]*D
for i in range(100):
    d=random.randint(1,D)
    q=random.randint(1,26)
    old=t[d-1]
    oldscore=score(D,c,s,t)
    t[d-1]=q
    if score(D,c,s,t)<oldscore:
        t[d-1]=old
for i in range(D):
    print(t[i])
### BUGGY CODE ###

import numpy as np

#def f(x,a):
#  return np.array([ c^x for c in a ],dtype=np.int64).sum()

def g(y,s):
  return np.array([s[m,y[m]] for m in range(M)]).sum()

(N,K) = map(int,input().split())
A = np.array(list(map(int,input().split())),dtype=np.int64)
M=40

B = np.empty((M,N),dtype=np.int)
Y = np.empty(M,dtype=np.int)

for n in range(N):
  for m in range(M):
    B[m,n] = (A[n] >> m) & 1

S = np.empty((M,2),dtype=np.int64)
for m in range(M):
  s = B[m].sum()
  S[m] = [s<<m,(N-s)<<m]
  if 2*s < N:
    Y[m] = 1
  else:
    Y[m] = 0

Kb = np.array([ (K >> m) & 1 for m in range(M)],dtype=np.int)

ans = S[:,0].sum()
for m in range(M):
  if Kb[m] == 0:
    continue
  else:
    Z = np.concatenate((Y[:m],np.array([0],dtype=np.int),Kb[m+1:]))
    ans = max(ans,g(Z,S))

print(ans)

### FIXED CODE ###

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

L = K+1
M = len(bin(L))-2
MM = max(M, len(bin(max(A)))-2)
best = []
ones_num = []
zeros_num = []
for m in range(MM):
    ones = sum([ (A[i]>>m)&1 for i in range(N) ])
    zeros = N - ones
    ones_num.append(ones)
    zeros_num.append(zeros)
    if ones >= zeros:
        best.append(0)
    else:
        best.append(1)
cur = sum([ (N-ones_num[m] if (best[m] and m < M-1) else ones_num[m])<<m for m in range(MM)])
ans = cur
m = M - 1
while m > 0:
    cur += (zeros_num[m]-ones_num[m])<<m
    m -= 1
    while (L >> m)&1 == 0:
        if best[m] == 1:
            cur += (ones_num[m]-zeros_num[m])<<m
        m -= 1
        if m < 0:
            break
    else:
        if best[m] == 1:
            cur += (ones_num[m]-zeros_num[m])<<m
        if cur > ans:
            ans = cur
print(ans)
### BUGGY CODE ###

N = int(input())

a = [int(input()) for i in range(N)]

tmp = 0
count = 1
tmp = a[0]

while tmp != 2 and tmp != 1:
    count += 1
    tmp = a[tmp-1]

if tmp == 2:
    print(count)
else:
    print(-1)

### FIXED CODE ###

N = int(input())

a = [int(input())-1 for i in range(N)]
owari = [0]*N

tmp = 0
count = 0

while owari[tmp] == 0 and tmp != 1:
    count += 1
    owari[tmp]=1
    tmp = a[tmp]

if tmp == 1:
    print(count)
else:
    print(-1)
### BUGGY CODE ###

S=input()
mem_mod = [0 for i in range(0,2019,1)]
N = len(S)
counter = 0
S_num_tmp = list(S)
S_num = list(map(int, S_num_tmp))
tmp=10
for i in range(1,N,1):
    S_num[N-i-1] = S_num[N-i] + (tmp)*S_num[N-i-1]
    tmp=tmp*10
for i in range(0,N,1):
    X = S_num[N-i-1] % 2019
    if X==0:
        counter+=1
    counter += mem_mod[X]
    mem_mod[X] += 1
print(counter)


### FIXED CODE ###

import collections
p = 2019
s=input()
n=len(s)
arr=[int(s[i]) for i in range(len(s))] #文字列の各文字をそれぞれ数字に変換しておく
if p==2 or p==5: #P=2,5のときは10を割り切るので連続部分列の右端のみを見ればよい
 ans=0
 for i in range(n):
   if arr[i]%p==0:
     ans+=i+1
 print(ans)
else: #Pが2でも5でもないとき
 dic=collections.defaultdict(int)
 tmp=0
 for i in range(n-1,-1,-1): #右端の要素を右端とする連続部分列のあまりを順に求める
   tmp+=arr[i]*pow(10,n-1-i,p)
   tmp%=p
   dic[tmp]+=1
 ans=0
 rem=0 #調べるあまりの値(初期値は0)
 for i in range(n-1,-1,-1):
   ans+=dic[rem]
   rem+=arr[i]*pow(10,n-1-i,p) #調べるあまりの値に(i番目の要素)*10^(n-1-i)を加える
   rem%=p
   dic[rem]-=1 #右端の要素が右端、i番目の要素が左端となる連続部分列のあまりの個数を1減らす
 print(ans)
### BUGGY CODE ###

import sys
from functools import reduce
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))

def gcd(a, b):
	while (b):
		a, b = b, a % b
	return a

def gcd_list(numbers):
    return reduce(gcd, numbers)

ans = 0
for i in range(n):
    ans = max(ans, gcd_list(A[0:i] + A[i + 1:]))

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from functools import reduce
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))

def gcd(a, b):
	while (b):
		a, b = b, a % b
	return a


L = [0] + [None] * (n - 1)
R = [0] + [None] * (n - 1)
for i in range(1, n):
	L[i] = gcd(L[i - 1], A[i - 1])
	R[i] = gcd(R[i - 1], A[-i])

M = [None] * n
R = R[::-1]
for i in range(n):
	M[i] = gcd(L[i], R[i])

print(max(M))
### BUGGY CODE ###

from statistics import mean, median,variance,stdev
import sys
import math
import fractions

def j(q):
    if q==1: print("YES")
    else:print("NO")
    exit(0)


def ct(x,y):
    if (x>y):print("")
    elif (x<y): print("")
    else: print("")

def ip():
    return int(input())

#n = ip()                              #入力整数1つ
#n,k= (int(i) for i in input().split())      #入力整数横2つ
x,y,z = (int(i) for i in input().split())    #入力整数横3つ
#n,m,x,y= (int(i) for i in input().split())  #入力整数横4つ
#a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列

#jの変数はしようできないので注意

a = [i for i in range(x,y+1)]
l = len(a)
b = a[:z]
b.extend(a[l-z:])
c = set(b)
b = list(c)
b.sort()
for i in range(len(b)):
    print(b[i])

### FIXED CODE ###

from statistics import mean, median,variance,stdev
import sys
import math
import fractions

def j(q):
    if q==1: print("AC")
    else:print("WA")
    exit(0)


def ct(x,y):
    if (x>y):print("")
    elif (x<y): print("")
    else: print("")

def ip():
    return int(input())

#n = ip()                              #入力整数1つ
#x,y= (int(i) for i in input().split())      #入力整数横2つ
a,b,k = (int(i) for i in input().split())    #入力整数横3つ
#n,m,x,y= (int(i) for i in input().split())  #入力整数横4つ
#a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列

#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
c = [ i for i in range(a,min(b,a+k))]
d = [ i for i in range(max(b-k+1,a),b+1)]
e = set()
for i in range(len(c)):
    e.add(c[i])
for i in range(len(d)):
    e.add(d[i])
e = list(e)
e.sort()
for i in range(len(e)):
    print(e[i])
### BUGGY CODE ###

N,M = list(map(int,input().split()))
p = list(map(int,input().split()))
p = [i-1 for i in p]
alr = [True for i in range(N)]
xy = [[] for i in range(N)]
for i in range(M):
    x,y = list(map(int,input().split()))
    x -= 1
    y -= 1
    xy[x].append((y,p.index(y)))
    xy[y].append((x,p.index(x)))
    alr[x] = False
    alr[y] = False
count = 0
for i in range(N):
    if alr[i] and p[i] == i:
        count += 1
for i in range(N):
    if (not alr[i]) and (xy[i]):
        alr[i] = True
        stack = [j for j in xy[i]]
        indlist = set()
        indlist.add(p.index(i))
        numlist = set()
        numlist.add(i)
        while stack:
            num,ind = stack.pop()
            alr[num] = True
            numlist.add(num)
            indlist.add(ind)
            for j in xy[num]:
                if not alr[j[0]]:
                    alr[j[0]] = True
                    stack.append(j)
        count += len(numlist & indlist)
print(count)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
N,M = list(map(int,input().split()))
p = [i-1 for i in map(int,input().split())]
alr = [False for i in range(N)]
xy = [[] for i in range(N)]
for i in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    xy[x].append(y)
    xy[y].append(x)
count = 0

for i in range(N):
    if (not alr[i]) and (xy[i]):
        alr[i] = True
        stack = [i]
        numlist = set()
        numlist.add(i)
        while stack:
            j = stack.pop()
            for k in xy[j]:
                if not alr[k]:
                    alr[k] = True
                    stack.append(k)
                    numlist.add(k)
        indlist = set([p[i] for i in numlist])
        count += len(numlist & indlist)
    else:
        if (not alr[i]) and p[i] == i:
            count += 1
print(count)
### BUGGY CODE ###

import bisect

N = int(input())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))
D = len(C)

ans = 0
for i in A:
    for k in B[bisect.bisect_right(B,i):]:
        ans += D - bisect.bisect_right(C,k)
print(ans)

### FIXED CODE ###

import bisect

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

ans = 0
for i in B:
    ans += bisect.bisect_left(A,i)*(N - bisect.bisect_right(C,i))
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
alst = list(map(int, input().split()))
plus = []
zero = []
minus = []
for a in alst:
    if a > 0:
        plus.append(a)
    elif a == 0:
        zero.append(a)
    else:
        minus.append(-1 * a)
p = len(plus)
z = len(zero)
m = len(minus)
p_cnt = p * (p - 1) // 2 + m * (m - 1) // 2
z_cnt = p * z + m * z + z * (z - 1) // 2
m_cnt = p * m
minus.sort()
plus.sort()
if m_cnt >= k: # 答えがマイナス
    l = 0
    r = 10 ** 20
    while r - l > 1:
        num = (r + l) // 2
        p_pos = p - 1
        cnt = 0
        for m_pos in range(m):
            while minus[m_pos] * plus[p_pos] >= num and p_pos >= 0:
                p_pos -= 1
            cnt += p - p_pos - 1
        if cnt >= k:
            l = num
        else:
            r = num
    ans = l * -1
elif m_cnt + z_cnt >= k: # 答えがゼロ
    ans = 0

else: # 答えがプラス
    k -= (z_cnt + m_cnt)
    l = 0
    r = 10 ** 20
    while r - l > 1:
        num = (r + l) // 2
        m_r = m - 1
        cnt = 0
        cnt_sub = 0
        for m_l in range(m):
            while minus[m_l] * minus[m_r] > num and m_r >= 0:
                m_r -= 1
            cnt += m_r + 1
            if minus[m_l] * minus[m_l] <= num:
                cnt -= 1
        p_r = p - 1
        for p_l in range(p):
            while plus[p_l] * plus[p_r] > num and p_r >= 0:
                p_r -= 1
            cnt += p_r + 1
            if plus[p_l] * plus[p_l] <= num:
                cnt -= 1
        cnt //= 2
        if cnt >= k:
            r = num
        else:
            l = num
    ans = r
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
alst = list(map(int, input().split()))
plus = []
zero = []
minus = []
for a in alst:
    if a > 0:
        plus.append(a)
    elif a == 0:
        zero.append(a)
    else:
        minus.append(-1 * a)
p = len(plus)
z = len(zero)
m = len(minus)
p_cnt = p * (p - 1) // 2 + m * (m - 1) // 2
z_cnt = p * z + m * z + z * (z - 1) // 2
m_cnt = p * m
minus.sort()
plus.sort()
if m_cnt >= k: # 答えがマイナス
    l = 0
    r = 10 ** 20
    while r - l > 1:
        num = (r + l) // 2
        p_pos = p - 1
        cnt = 0
        for m_pos in range(m):
            while minus[m_pos] * plus[p_pos] >= num and p_pos >= 0:
                p_pos -= 1
            cnt += p - p_pos - 1
        if cnt >= k:
            l = num
        else:
            r = num
    ans = l * -1
elif m_cnt + z_cnt >= k: # 答えがゼロ
    ans = 0

else: # 答えがプラス
    k -= (z_cnt + m_cnt)
    l = 0
    r = 10 ** 20
    while r - l > 1:
        num = (r + l) // 2
        m_r = m - 1
        cnt = 0
        cnt_sub = 0
        for m_l in range(m):
            while minus[m_l] * minus[m_r] > num and m_r >= 0:
                m_r -= 1
            cnt += m_r + 1
            if minus[m_l] * minus[m_l] <= num:
                cnt -= 1
        p_r = p - 1
        for p_l in range(p):
            while plus[p_l] * plus[p_r] > num and p_r >= 0:
                p_r -= 1
            cnt += p_r + 1
            if plus[p_l] * plus[p_l] <= num:
                cnt -= 1
        cnt //= 2
        if cnt >= k:
            r = num
        else:
            l = num
    ans = r
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]*N
dp[0] = 0
dp[1] = abs(h[1]-h[0])

for i in range(2,N):
  cost = []
  for j in range(1,min(K,i)+1):
    cost.append(dp[i-j] + abs(h[i]-h[i-j]))
  dp[i] = min(cost)
print(dp[-1])

### FIXED CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
inf = float("inf")
dp = [0]*N
dp[0] = 0
dp[1] = abs(h[1]-h[0])

for i in range(2,N):
  cost = []
  for j in range(1,min(K,i)+1):
    cost.append(dp[i-j] + abs(h[i]-h[i-j]))
  dp[i] = min(cost)
print(dp[-1])
### BUGGY CODE ###

from collections import Counter
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ca=Counter(a)
cb=Counter(b)
for k in cb:
    if k in ca:
        if cb[k]+ca[k]>n:
            print('No')
            exit()
ans=b[n//2:]+b[:n//2]
ng=set(())
ok=[]
for i in range(n):
    if a[i]==ans[i]:
        ng.add(i)
    else:
        ok.append(i)
from random import randint
while ng:
    k=len(ng)
    nng=set(())
    l=len(ok)
    i=0
    for x in ng:
        i+=1
        y=ok[randint(0,l-1)]
        ans[x],ans[y]=ans[y],ans[x]
        if ans[x]==a[x] or ans[y]==a[y]:
            ans[x],ans[y]=ans[y],ans[x]
            nng.add(x)
        else:
            ok.append(x)
    ng=nng

print('Yes')
print(*ans,sep=' ')



### FIXED CODE ###

from collections import Counter
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ca=Counter(a)
cb=Counter(b)
for k in cb:
    if k in ca:
        if cb[k]+ca[k]>n:
            print('No')
            exit()
tmpc=0
tmpd=0
c=[0]
d=[0]
for i in range(1,n+1):
    if i in ca:tmpc+=ca[i]
    if i in cb:tmpd+=cb[i]
    c.append(tmpc)
    d.append(tmpd)
x=0
for i in range(n+1):
    x=max(x,c[i]-d[i-1])
ans=b[-x:]+b[:-x]
print('Yes')
print(*ans,sep=' ')
exit()
print(c)
print(d)
### BUGGY CODE ###

import numpy as np
def main():
    S=input()
    dp=np.zeros((len(S)+1,13),dtype=int)
    dp[0][0]=1
    mod=10**9+7
    for i in range(1,len(S)+1):
        for a in range(13):
            if S[i-1]=="?":
                if a*10%13<(a*10+10)%13:
                    dp[i][a*10%13:(a*10+10)%13]+=dp[i-1][a]
                    dp[i][a*10%13:(a*10+10)%13]%=mod
                else:
                    dp[i][a*10%13:]+=dp[i-1][a]
                    dp[i][a*10%13:]%=mod
                    dp[i][:(a*10+10)%13]+=dp[i-1][a]
                    dp[i][:(a*10+10)%13]%=mod
            else:
                dp[i][(a*10+int(S[i-1]))%13]+=dp[i-1][a]
                dp[i][(a*10+int(S[i-1]))%13]%=mod
    print(dp[len(S)][5])
"""
    for i in range(1,len(S)+1):
        for a in range(13):
            if S[i-1]=="?":
                for n in range(10):
                    dp[i][(a*10+n)%13]+=dp[i-1][a]
            else:
                dp[i][(a*10+int(S[i-1]))%13]+=dp[i-1][a]
"""
if __name__=="__main__":
    main()

### FIXED CODE ###

#import numpy as np
def main():
    S=input()
    #dp=np.zeros((len(S)+1,13),dtype=int)
    dp=[[0]*13 for _ in range(len(S)+1)]
    dp[0][0]=1
    mod=10**9+7
    """
    for i in range(1,len(S)+1):
        for a in range(13):
            if S[i-1]=="?":
                if a*10%13<(a*10+10)%13:
                    dp[i][a*10%13:(a*10+10)%13]+=dp[i-1][a]
                    dp[i][a*10%13:(a*10+10)%13]%=mod
                else:
                    dp[i][a*10%13:]+=dp[i-1][a]
                    dp[i][a*10%13:]%=mod
                    dp[i][:(a*10+10)%13]+=dp[i-1][a]
                    dp[i][:(a*10+10)%13]%=mod
            else:
                dp[i][(a*10+int(S[i-1]))%13]+=dp[i-1][a]
                dp[i][(a*10+int(S[i-1]))%13]%=mod
    print(dp[len(S)][5])
"""
    for i in range(1,len(S)+1):
        for a in range(13):
            if S[i-1]=="?":
                for n in range(10):
                    dp[i][(a*10+n)%13]+=dp[i-1][a]
                    dp[i][(a*10+n)%13]%=mod
            else:
                dp[i][(a*10+int(S[i-1]))%13]+=dp[i-1][a]
                dp[i][(a*10+int(S[i-1]))%13]%=mod
    print(dp[len(S)][5])
if __name__=="__main__":
    main()
### BUGGY CODE ###

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

def parent(i):
    return i // 2


def left(i):
    return 2 * i


def right(i):
    return 2 * i + 1

class MaxHeap(list):
    def __init__(self, H=0):
        list.__init__(self)
        self.H = H
        self[:] = [None]

    def insert(self, key):
        self.H += 1
        self.append(-float("inf"))
        self.heapIncreaseKey(self.H, key)

    def heapIncreaseKey(self, i, key):
        if key < self[i]:
            return
        self[i] = key
        while i > 1 and self[parent(i)] < self[i]:
            pi = parent(i)
            self[i], self[pi] = self[pi], self[i]
            i = pi

    def heapExtract(self):
        if self.H < 1:
            raise "underflow"
        maximum = self[1]
        self[1] = self.pop()
        self.H -= 1
        self.maxHeapify(1)

        return maximum

    def maxHeapify(self, i):
        l = left(i)
        r = right(i)
        if l <= self.H and self[l] > self[i]:
            largest = l
        else:
            largest = i
        if r <= self.H and self[r] > self[largest]:
            largest = r

        if largest != i:
            self[i], self[largest] = self[largest], self[i]
            self.maxHeapify(largest)


if __name__ == '__main__':

    A = MaxHeap()
    while True:
        c = input().split(" ")
        if c[0] == "insert":
            A.insert(int(c[1]))
        elif c[0] == "extract":
            print(A.heapExtract())
        else:
            break




### FIXED CODE ###

# -*- coding: utf-8 -*-
from heapq import heappush, heappop

if __name__ == '__main__':

    q = []
    while True:
        c = input().split(" ")
        if c[0]=='end':
            break
        if c[0]=='insert':
            heappush(q, -int(c[1]))
        else:
            print(-heappop(q))
### BUGGY CODE ###

L = input()
n = len(L)
mod = 10**9 + 7
if L[-1] == '1':
    ans = 3
else:
    ans = 1
for i in range(2,n+1):
    if L[-i] == '1':
        ans = ans*2 % mod
        ans = (ans + 3**(i-1))%mod
print(ans)


### FIXED CODE ###

L = input()
n = len(L)
mod = 10**9+7
pow3 = [1]
for i in range(1,n):
    x = (3*pow3[i-1])%mod
    pow3.append(x)
ans = 0
for i in range(1,n+1):
    if L[-i] == '1':
        if i == 1:
            ans = 3
        else:
            ans = ans*2 % mod
            ans = (ans + pow3[i-1])%mod
    else:
        if i == 1:
            ans = 1
print(ans)
### BUGGY CODE ###

N = int(input())

sum = 0
for i in range(N):
    sum += i
print(sum)


### FIXED CODE ###

N = int(input())

if(N%2==1):
    print(N*(N-1)//2)
else:
    print(N*(N//2-1)+N//2)
### BUGGY CODE ###

a, b, c, k = list(map(int, input().split()))

cnt = 0
ret = 0

while(cnt < k):
  if(a > 0):
    ret += 1
    a -= 1
    cnt += 1
  elif(b > 0):
    b -= 1
    cnt += 1
  else:
    ret -= 1
    c -= 1
    cnt += 1

print(ret)

### FIXED CODE ###

a, b, c, k = list(map(int, input().split()))

cnt = 0
ret = 0

cnt += a
ret += a
if(cnt > k):
  ret -= cnt-k
if(cnt < k):
  cnt += b
if(cnt < k):
  cnt += c
  ret -= c
  if(cnt > k):
    ret += cnt-k

print(ret)