Harryxun/stf_run huggingface dataset:
N,M=map(int,input().split())
A=[input() for _ in range(N)]
B=[input() for _ in range(M)]
ans="No"
for i in range(N-M+1):
  for j in range(len(A[0])-len(B[0])+1):
    t = 0
    for k in range(len(B[0])):
      for l in range(M):
        if A[k+q][l+p] == B[q][p]:
          t += 1
    if t==len(B[0])*M:
      ans="Yes"
      exit()
print(ans)

### FIXED CODE ###

N,M=map(int,input().split())
A=[input() for _ in range(N)]
B=[input() for _ in range(M)]
ans="No"
for i in range(N-M+1):
  for j in range(N-M+1):
    if [a[j:j+M] for a in A[i:i+M]]==B:    
      ans="Yes"
print(ans)
N = int(input())
X = input()
S = []
for a in range(N):
    S.append(X[a])

for i in range(N-1):
  if S[i] != S[i+1] or S[i] == 'X':
    continue
  else:
    j = i+1
    while S[i] == S[j]:
      j += 1
    for l in range(i+1,j):
        S[l] = X
lista = [k for k in S if k != X]
print(''.join(lista))

### FIXED CODE ###

N = int(input())
X = input()
S = []
for a in range(N):
    S.append(X[a])

if N == 1:
    print(1)
else:
    for i in range(1,N):
        if S[i] != S[i-1]:
            continue
        else:
            S[i-1] = 'X'
    lista = [k for k in S if k != 'X']
    print(len(lista))
import math
n, init = map(int, input().split())
x = list(map(lambda a: int(a)-init, input().split()))
g = x[0]
for i in range(n-1):
    if g == 1:
        break
    elif x[i+1] % g != 0:
        g = math.gcd(g,x[i+1])
print(g)


### FIXED CODE ###

n, init = map(int,input().split())
x = list(map(lambda x: abs(int(x)-init), input().split()))
g = x[0]
def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x%y)
for i in range(1,n):
    g = gcd(g,x[i])
print(g)
#coding: UTF-8

def Rectangle(a,b):
    return a*b,2*(a+b)

if __name__=="__main__":
    a = input()
    b = input()
    area,length = Rectangle(int(a),int(b))
    print(area,length)

### FIXED CODE ###

#coding: UTF-8

def Rectangle(a,b):
    return a*b,2*(a+b)

if __name__=="__main__":
    a = input().split(" ")
    area,length = Rectangle(int(a[0]),int(a[1]))
    print(area,length)
import math
n = int(input())
nn = int(math.sqrt(n))
while n%i != 0: i-=1
print(len(str(n//i)))


### FIXED CODE ###

import math
n = int(input())
nn = int(math.sqrt(n))
while n%nn != 0: nn-=1
ans = len(str(n//nn))
print(ans)
import heapq
n,m = map(int,input().split())
x = list(map(int,input().split()))
x.sort()
x_range = []
cut = [0]
count = 0
for i in range(m-1):
    x_range.append(abs(x[i]-x[i+1]))
h = heapq.nlargest(n-1,x_range)
for i in h:
    cut.append(x_range.index(i)+1)
cut.append(len(x))
for i in range(len(cut)-1):
    sum_range = x[cut[i]:cut[i+1]]
    count += abs(sum_range[0]-sum_range[len(sum_range)-1])
print(count)


### FIXED CODE ###

n,m = map(int,input().split())
x = list(map(int,input().split()))
dist = []
x.sort()
if n > m:
    print(0)
else:
    for i in range(m-1):
        dist.append(x[i+1] -x[i])
    dist.sort()
    print(sum(dist[:m-n]))
N = int(input())
h = list(map(int, input().split())) #0-index

inf = float('inf')
dp = [inf]*(N+1)

def chmin(a,b):
    if a >= b:
        return b
    else:
        a

dp[0] = 0
for i in range(1,N):
    dp[i] = chmin(dp[i], dp[i-1] + abs(h[i] - h[i-1]))
    
    if i >= 2:
        dp[i] = chmin(dp[i], dp[i-2] + abs(h[i] - h[i-2]))
    
print(dp[N-1])

### FIXED CODE ###

import math

N = int(input())
h = list(map(int, input().split()))
dp = [float('INF')] * N

def chmin(a, b):
    if a >= b:
        return b
    else:
        return a

#初期値
dp[0] = 0

#Loop
for i in range(1, N):
    dp[i] = chmin(dp[i], dp[i-1] + abs(h[i] - h[i-1]))
    if i > 1:
        dp[i] = chmin(dp[i], dp[i-2] + abs(h[i] - h[i-2]))
print(dp[-1])
N = int(input())
H = list(map(int, input().split()))

cnt = [0] * N
for i in range(N):
    for j in range(i, N-i+2):
        if H[j] >= H[j+1]:
            cnt[i] +=1
        else:
            break

print(max(cnt))

### FIXED CODE ###

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

cnts = 0
cnt = [0] * N
for i in range(1, N):
    if H[i-1] >= H[i]:
        cnts +=1
    else :
        cnts = 0
    cnt[i] = cnts

print(max(cnt))
X, Y, A, B, C = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)

px = p[:X]
qy = q[:Y]
print(qy)
while r and min(px[-1], qy[1]) < r[0]:
  px.sort(reverse=True)
  qy.sort(reverse=True)
  if px[-1] < qy[-1]:
    px[-1] = r[0]
    r.pop(0)
  else:
    qy[-1] = r[0]
    r.pop(0)

print(sum(px) + sum(qy))

### FIXED CODE ###

X, Y, A, B, C = map(int, input().split())
p = sorted(list(map(int, input().split())), reverse=True)[:X]
q = sorted(list(map(int, input().split())), reverse=True)[:Y]
r = list(map(int, input().split()))
ans = sum(sorted(p + q + r, reverse=True)[:X + Y])
print(ans)
import functools

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

@functools.lru_cache(None)
def rec(i):
  if i == 0: return 0
  i1 = rec(i - 1) + abs(A[i - 1] - A[i])
  i2 = float("inf")
  if i >= 2:
      i2 = rec(i - 2) + abs(A[i - 2] - A[i])
  return min(i1, i2)

ans = rec(n - 1)
print(ans)


### FIXED CODE ###

def frog(H):
    n = len(H)
    cost = 0
    n_2 = 0
    n_1 = 0
    for i in range(n):
        if i >= 1:
            cost = abs(H[i] - H[i - 1]) + n_1
            if i >= 2:
                cost = min(cost, abs(H[i] - H[i - 2]) + n_2)
        n_2 = n_1
        n_1 = cost
    return cost

assert frog([10, 10, 10]) == 0
assert frog([10, 10]) == 0
assert frog([10, 30, 40, 20]) == 30
assert frog([30, 10, 60, 10, 60, 50]) == 40

n = int(input())
H = list(map(int, input().split()))
ans = frog(H)
print(ans)
import sys
import numpy as np
N = int(input())
D = list(map(int,input().split()))
M = max(D)
countlist=np.zeros(M+1)
ans=1

for i in D:
    countlist[i]+=1

if countlist[0]!=1 :
    print(0)
    sys.exit()
elif countlist[1]==0 and M==1:
    print(1)
    sys.exit()

for i in range(2,M+1):
    if countlist[i]>0:
        ans *= countlist[i-1]**countlist[i]
    elif i<M:
        ans=0
    else:
        break


print(int(ans)%998244353) 

### FIXED CODE ###

import sys
import numpy as np
N = int(input())
D = list(map(int,input().split()))
M = max(D)
countlist=list(map(int,np.zeros(M+1)))
ans=1

for i in D:
    countlist[i]+=1

if 0 in countlist or countlist[0]!=1 :
    print(0)
    sys.exit()
elif M<2:
    print(1)
    sys.exit()

if D[0]!=0 :
    print(0)
    sys.exit()

for i in range(2,M+1):
    if countlist[i]>0:
        ans *= countlist[i-1]**countlist[i]
    elif i<M:
        ans=0
    else:
        break


print(ans%998244353)
N = int(input())
A = int(input())
B = int(input())

if (N*A) < B:
    print(N*A)
else:
    print(B)

### FIXED CODE ###

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

N *= A

if (N) < B:
    print(N)
else:
    print(B)
s = str(input())

num = [int(s[-1])]
for i in range(1, len(s)):
    tmp = num[-1] + pow(10, i, 2019) * int(s[-i - 1])
    num.append(tmp % 2019)

mod = [1] + [0] * 2018
ans = 0
for i in num:
    ans += mod[m]
    mod[m] += 1
print(ans)


### FIXED CODE ###

s = str(input())

num = [int(s[-1])]
for i in range(1, len(s)):
    tmp = num[-1] + pow(10, i, 2019) * int(s[-i - 1])
    num.append(tmp % 2019)

mod = [1] + [0] * 2018
ans = 0
for i in num:
    m = i % 2019
    ans += mod[m]
    mod[m] += 1
print(ans)
from itertools import permutations

N, C = [int(elem) for elem in input().split(' ')]
D_matrix = [[int(elem) for elem in input().split(' ')] for _ in range(C)]
assert len(D_matrix) == C
assert len(D_matrix[0]) == C
c_matrix = [[int(elem) for elem in input().split(' ')] for _ in range(N)]
assert len(c_matrix) == N
assert len(c_matrix[0]) == N

# grouping
# O(N^2)
mod_list = [[] for _ in range(3)]
for i in range(N):
    for j in range(N):
        mod_list[(i + j) % 3].append((i, j))

# O(N^2)
mod_color_list = [[0] * C for _ in range(3)]
for k, mod in enumerate(mod_list):
    for i, j in mod:
        mod_color_list[k][c_matrix[i][j] - 1] += 1

# O(C^3 * N^2) -> O(C^4)
min_cost = float('inf')
for colors in permutations(range(C), 3):
    total_cost = 0
    for color, mod_color in zip(colors, mod_color_list):
        total_cost += sum([D_matrix[X][color] * mod_color[X] for X in range(C)])
    min_cost = min(min_cost, total_cost)

print(min_cost)


### FIXED CODE ###

N = int(input())

if N < 1000:
    print("ABC")
else:
    print("ABD")
from math import factorial
# 組み合わせ
def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

def main():
    num, k = map(int, input().split())

    max_num = combinations_count(num - 1, 2)

    if k > max_num:
        print('-1')
    else:
        edge = num - 1
        now_count = max_num
        data = [[num, i] for i in range(1, num)]
        for i in range(1, num):
            for j in range(i + 1, num):
                if now_count > k:
                    edge += 1
                    now_count -= 1
                    data.append([i, j])
                else:
                    pass

        print(edge)
        for i, j in data:
            print(i, j)

if __name__ == '__main__':
    main()



### FIXED CODE ###


from math import factorial
# 組み合わせ
def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

def main():
    num, k = map(int, input().split())

    if num == 2:
        max_num = 10
    else:
        max_num = combinations_count(num - 1, 2)
    # max_num = combinations_count(num - 1, 2)

    if k > max_num or num == 2:
        if num == 2 and k == 0:
            print(1)
            print(1, 2)
        else:
            print('-1')
    else:
        edge = num - 1
        now_count = max_num
        data = [[num, i] for i in range(1, num)]
        for i in range(1, num):
            for j in range(i + 1, num):
                if now_count > k:
                    edge += 1
                    now_count -= 1
                    data.append([i, j])
                else:
                    pass

        print(edge)
        for i, j in data:
            print(i, j)

if __name__ == '__main__':
    main()
import math

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

def calc_theta(a, b, x):
    if x >= 0.5 * a ** 2 * b:
        tmp = (a ** 3) / (2 * ((a **2) * b - x))
    else:
        tmp = (2 * x) / ((b ** 2) * a)

    return 90 - math.degrees(math.atan(tmp))

ans = calc_theta(a, b, x)

print('{:.10f}'.format(ans))






### FIXED CODE ###

import math

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

def calc_theta(a, b, x):
    if x >= 0.5 * a ** 2 * b:
        # tmp = (a ** 3) / (2 * ((a **2) * b - x)) これだと 0divになる
        tmp = (2/a)*(b-(x/a**2))
    else:
        tmp = (a * b * b) / (2 * x)
    return math.degrees(math.atan(tmp))

ans = calc_theta(a, b, x)

print('{:.10f}'.format(ans))
X, Y, A, B, C = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

eat = []

# 食べる
p.sort(reverse=True)
if X > A:
    eat.extend(p)
else:
    eat.extend(p[:X])

q.sort(reverse=True)
if Y > B:
    eat.extend(q)
else:
    eat.extend(q[:Y])
loss = X+Y - len(eat)

# 足りない分を補充する
while loss > 0:
    r.sort(reverse=True)
    eat.append(r.pop(0))    
    loss -= 1

# rの方が大きいものがあれば入れ替える
eat.sort()
for i in range(len(eat)):
    if len(r) != 0 and eat[i] < r[0]:
        eat[i] = r.pop(0)
    else:
        break

print(sum(eat))


### FIXED CODE ###

s = list(input())

ret = (s[2] == s[3]) and (s[4] == s[5])
if ret:
    print('Yes')
else:
    print('No')
n=int(input())
dat = list(map(int, input().split()))
dan = []
for e in dat:
    e = str(bin(e))
    e=e[2:]
       
#for i in range(n):
#      j = -1
#     while j > -len(dat[i]):
#          if dat[i][j]=='1':
 #              dan.append(-j-1)
#               break
#          else:
#               j = j - 1
           
print(min(len(dat))



### FIXED CODE ###

import sys

def main():
    N = int(input())
    A = [int(_) for _ in input().split()]

    t = 0
    while True:
        for i in range(N):
            if A[i] % 2 == 0:
                A[i] //= 2
            else:
                print(t)
                sys.exit()
        t += 1

main()
# coding: utf-8

import sys
input = sys.stdin.readline

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

AB = [list(map(int, input().split())) for __ in range(N)]
AB.sort(key=lambda x : x[0])

for k in AB:
    if M > k[1]:
        M -= k[1]
        ans += k[0] * k[1]
    else:
        ans += k[0] * M
        break

print(ans)



### FIXED CODE ###

# coding: utf-8

# import sys
# input = sys.stdin.readline

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

AB = [list(map(int, input().split())) for __ in range(N)]
AB.sort(key=lambda x : x[0])

k = 0
ans = 0
while M > 0:
    if M > AB[k][1]:
        M -= AB[k][1]
        ans += AB[k][0] * AB[k][1]
    else:
        ans += AB[k][0] * M
        break
    
    k += 1

print(ans)
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int n = scan.nextInt();
        int res = factorial(n);
        String str = Integer.toString(res);
        StringBuilder rev = new StringBuilder(str);
        String s = rev.reverse().toString();
        String[] st = s.split("");
        int count = 0;
        for (int i=0; i<st.length; i++){
            if (st[i].contains("0")) {
                count += 1;
            } else {
                break;
            }
        }
        System.out.println(s);
        System.out.println(count);

    }

    public static int factorial(int a){
        int res = 0;
        if (a<2) {
            res = 1;
        } else {
            res = a*factorial(a-2);
        }
        return res;
    }
}


### FIXED CODE ###

N = int(input())
l = len(str(N))
if N < 2:
    print(0)
elif N % 2 == 1:
    print(0)
else:
    ans = 0
 
    for i in range(1, 2*l):
        tmp = 0
        ans += (N // 10**i)
        tmp += (N // (10 * (5**i)))
        tmp -= N // (10 * (10**i))
        ans += max(tmp, 0)
 
    print(ans)
A,B = [int(i) for i in input().split()]
if A <＝ 8:
    print('Yay!')
elif B <＝ 8:
    print('Yay!')
else:
    print(':(')

### FIXED CODE ###

A,B = [int(i) for i in input().split()]
if A > 8:
    print(':(')
elif B > 8:
    print(':(')
else:
    print('Yay!')
n = int(input())
A = list(map(int,input().split()))

B = []

for i in range(n):
  if i %2:
    B = [A[i]] + B
  else:
    B = B.append(A[i])
    
if n%2:
  B = B[::-1]
print(*B)

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
from collections import deque

B = deque([])

for i in range(n):
  if i %2:
    B.appendleft(A[i])
  else:
    B.append(A[i])
B = list(B)
if n%2:
  B = B[::-1]
print(*B)
#途中まで
N = int(input())
A = list(map(int, input().split()))

DP = [[-1] * (N + 1) for _ in range(N + 1)]

R = {}
for i in range(5):
  a = A[i]
  if a in R:
    R[a] += 1
  else:
    R[a] = 1

Flag = 0
for i in R.keys():
  if R[i] >= 3:
    Flag = 1
    R[i] -= 3

L = []
for i in R.keys():
  if R[i] == 2:
    DP[i][i] = Flag
  elif R[i] == 1:
    L.append(R[i])

for i in range(len(L) - 1):
  for j in range(i + 1, len(L)):
    DP[L[i]][L[j]] = Flag

print(DP)

for i in range(5, N * 3, 3):
  R = {}
  for j in range(i, i + 3):
    pass


### FIXED CODE ###

def insertR(a, b):
  if a not in R: R[a] = {}
  if b not in R[a]: R[a][b] = 0

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

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

DP = [[-1] * (N + 1) for _ in range(N + 1)]
D = [-1] * (N + 1)
R = {}
for i in range(5):
  a = A[i]
  if a in R:
    R[a] += 1
  else:
    R[a] = 1

Flag = 0
for i in R.keys():
  if R[i] >= 3:
    Flag = 1
    R[i] -= 3

L = []
for i in R.keys():
  if R[i] == 2:
    L.append(i)
    DP[i][i] = Flag
    D[i] = Flag
  elif R[i] == 1:
    L.append(i)
    D[i] = Flag

for i in range(len(L) - 1):
  for j in range(i + 1, len(L)):
    DP[L[i]][L[j]] = Flag

common = 0
for i in range(5, N * 3 - 3, 3):
  L = []
  for j in range(i, i + 3):
    for k in range(len(L)):
      if L[k][1] == A[j]:
        L[k][0] += 1
        break
    else :
      L.append([1, A[j]])
  L.sort()
  R = {}
  # 3
  if len(L) == 1:
    common += 1
  # 1:2
  elif len(L) == 2:
    a = L[0][1]
    b = L[1][1]
    # 1個のほうを揃える場合
    if DP[a][a] != -1:
      insertR(b, b)
      R[b][b] = max([R[b][b], DP[b][b], DP[a][a] + 1])
    # 2個のほうを揃える場合
    for j in range(N + 1):
      n = max(DP[b][j], DP[j][b])
      if n == -1: continue
      insertR(a, j)
      R[a][j] = max([R[a][j], DP[a][j], n + 1])
    # 揃えない場合
    for j in range(N + 1):
      n = D[j]
      if n == -1: continue
      insertR(a, j)
      R[a][j] = max(R[a][j], n)
      insertR(b, j)
      R[b][j] = max(R[b][j], n)
    n = max(D)
    insertR(a, b)
    R[a][b] = max(R[a][b], n)
    insertR(b, b)
    R[b][b] = max(R[b][b], n)
  # 1:1:1
  elif len(L) == 3:
    a = L[0][1]
    b = L[1][1]
    c = L[2][1]
    insertR(b, c)
    insertR(a, c)
    insertR(a, b)
    #揃える場合
    if DP[a][a] != -1:  
      R[b][c] = max(R[b][c], DP[a][a] + 1)
    if DP[b][b] != -1:      
      R[a][c] = max(R[a][c], DP[b][b] + 1)
    if DP[c][c] != -1:
      R[a][b] = max(R[a][b], DP[c][c] + 1)
    #揃えない場合
    for j in range(N + 1):
      n = D[j]
      if n == -1: continue
      insertR(a, j)
      R[a][j] = max(R[a][j], n)
      insertR(b, j)
      R[b][j] = max(R[b][j], n)
      insertR(c, j)
      R[c][j] = max(R[c][j], n)
    n = max(D)
    R[a][b] = max(R[a][b], n)
    R[b][c] = max(R[b][c], n)
    R[a][c] = max(R[a][c], n)

  for k in R.keys():
    for kk in R[k].keys():
      n = R[k][kk]
      DP[k][kk] = max(DP[k][kk], n)
      DP[kk][k] = max(DP[kk][k], n)
      D[k] = max(D[k], n)
      D[kk] = max(D[kk], n)

a = A[-1]
if DP[a][a] != -1:
  DP[a][a] += 1

ans = 0
for i in DP:
  for j in i:
    ans = max(ans, j)

ans += common

print(ans)
def judge(board):
    for i in range(0, 3):
        if board[i][0] == board[i][1] == board[i][2] :
            return True
        if board[0][i] == board[1][i] == board[2][i]:
            return True
    
    if board[0][0] == board[1][1] == board[2][2]:
        return True
    if board[0][2] == board[1][1] == borad[2][0]:
        return True
    
    return False


upper  = list(map(int, input().split(" ")))
middle = list(map(int, input().split(" ")))
lower  = list(map(int, input().split(" ")))

board = (upper,middle,lower)

N = int(input())
bingos = list()

for i in range(0, N):
    bingos.append(int(input()))

for i in range(0, len(bingos)):
    for j in range(0, 3):
        if upper[j] == bingos[i]:
            board[0][j] = 0
            break
        elif middle[j] == bingos[i]:
            board[1][j] = 0
            break
        elif lower[j] == bingos[i]:
            board[2][j] = 0
            break
        else:
            pass

if judge(board):
    print('Yes')
else:
    print('No')


### FIXED CODE ###

def judge(board):
    for i in range(0, 3):
        if board[i][0] == board[i][1] == board[i][2] == 0 :
            return True
        if board[0][i] == board[1][i] == board[2][i] == 0:
            return True
    
    if board[0][0] == board[1][1] == board[2][2] == 0:
        return True
    if board[0][2] == board[1][1] == board[2][0] == 0:
        return True
    
    return False


upper  = list(map(int, input().split(" ")))
middle = list(map(int, input().split(" ")))
lower  = list(map(int, input().split(" ")))

board = (upper,middle,lower)

N = int(input())
bingos = list()

for i in range(0, N):
    bingos.append(int(input()))


"""
print(upper)
print(middle)
print(lower)
print(bingos)

for i in range(3):
    for j in range(3):
        print(f'board[', i, '][', j, '] =', board[i][j])
"""

for i in range(0, len(bingos)):
    for j in range(0, 3):
#        print('bingos[i] : j = ', bingos[i], j)
        if upper[j] == bingos[i]:
            board[0][j] = 0
#            print('find in upper')
            break
        elif middle[j] == bingos[i]:
            board[1][j] = 0
#            print('find in middle')
            break
        elif lower[j] == bingos[i]:
            board[2][j] = 0
#            print('find in lower')
            break
        else:
            pass
#    print('')

if judge(board):
    print('Yes')
else:
    print('No')
import sys
N,M = map(int, input().split())
A = list(map(int, input().split()))
sorted_A = sorted(A, reverse=True) 
all_A = sum(A)

rule = (1/(4*M))

ans = 0

for i in A:
    if (i / all_A) > rule:
        ans = ans + 1
    else:
        pass

if ans >= M:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

X,Y,Z = map(int, input().split())

print(str(Z) + " " + str(X) + " " + str(Y))
, S = map(int, input().split())

all = []
for x in range(0,K+1):
	if S-x < 0:
		break
	for y in range(0, min(K,S-x)+1):
		z = S-x-y
		if z>-1:
			if z < K+1:
				all.append(str(x)+str(y)+str(z))
		else:
			break

print(len(set(all)))

### FIXED CODE ###

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

cnt = 0
for x in range(0,K+1):
	if S-x < 0:
		break
	for y in range(0, min(K,S-x)+1):
		z = S-x-y
		if z>-1:
			if z < K+1:
				cnt += 1
		else:
			break

print(cnt)
L=input()
N=len(L)
dp=[[0,0]for _ in range(N)]
dp[0][0]=1 #以下が確定（0）
dp[0][1]=2 #以下が確定してない（1,0）と逆
mod=10**9+7
for i in range(1,N):
  dp[i][0]+=3*dp[i-1][0]
  dp[i][0]%=mod
  if L[i]=='0':
    dp[i][1]+=dp[i-1][1]
  else:
    dp[i][0]+=dp[i-1][1]　#(両方0)を配給する1パターン
    dp[i][1]+=dp[i-1][1]*2　#（1,0）とその逆
  dp[i][0]%=mod
  dp[i][1]%=mod
print(sum(dp[-1])%mod)

### FIXED CODE ###

L=input()
N=len(L)
dp=[[0,0]for _ in range(N)]
dp[0][0]=1
dp[0][1]=2
mod=10**9+7
for i in range(1,N):
  dp[i][0]+=3*dp[i-1][0]
  dp[i][0]%=mod
  if L[i]=='0':
    dp[i][1]+=dp[i-1][1]
  else:
    dp[i][0]+=dp[i-1][1]
    dp[i][1]+=dp[i-1][1]*2
  dp[i][0]%=mod
  dp[i][1]%=mod
print(sum(dp[-1])%mod)
while True :
    (x,y) = int(i) for i in input().split()
    if 0 = x and 0 = y:
        break
    else if x <= y:
        print(x,y)
    else :
        print(y,x)

### FIXED CODE ###

while True:
    (x, y) = [int(i) for i in input().split()]
    
    if x == y == 0 :
        break

    if x <= y :
        print(x, y)
    else :
        print(y, x)
a,b,c,d,e,f = [int(i) for i in input().split()]
#print(a,b,c,d,e,f)

nod=0
for i in range(30+1):
  for j in range(30-i+1):
    for k in range(100+1):
      for l in range(100-k+1):
        if 0 < 100*(a*i+b*j)+c*k+d*l <= f and c*k+d*l <= e*(i+j):
          tmp=(c*k+d*l)/(100*(a*i+b*j)+c*k+d*l)
          if nod < tmp:
            nod=tmp
            ans1=100*(a*i+b*j)+c*k+d*l
            ans2=c*k+d*l
                        
print(ans1,ans2)


### FIXED CODE ###

a, b, c, d, e, f= (int(i) for i in input().split()) 

waterlist=[]
for i in range(0,f+100*a,100*a):
  for j in range(0,f+100*b,100*b):
    if i+j <=f:
      waterlist+=[i+j]
waterlist=list(set(waterlist))
#print(x)

sugarlist=[]
for i in range(int(f/c)+1):
  for j in range(int(f/d)+1):
    if c*i+d*j <=f:
      sugarlist+=[c*i+d*j]
sugarlist=list(set(sugarlist))
#print(y)

density=0

for i in range(len(waterlist)):
  for j in range(len(sugarlist)):
    if 0 < waterlist[i]+sugarlist[j] <= f and sugarlist[j]<=waterlist[i]/100*e:
      tmp=sugarlist[j]/(waterlist[i]+sugarlist[j])
      if density <= tmp:
        density = tmp
        ans1=waterlist[i]+sugarlist[j]
        ans2=sugarlist[j]
        
print(ans1,ans2)
n=int(input())
h=list(map(int,input().split()))
c=1
if h[0]<=h[1]:
  c=2
for i in range(2,n):
  if h[i]>=max(h[0:i-1]):
    c+=1
print(c)

### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
c=1
if len(h)>1 and h[0]<=h[1]:
  c=2
for i in range(2,n):
  if h[i]>=max(h[0:i]):
    c+=1
print(c)