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

#import sympy
#import random

def get_ans():
    N = int(input())
    A_list = [int(e) for e in input().split()]

    #テスト用乱数生成
    
    #N = 10**6
    #A_list = [random.randrange(1,10**6) for _ in range(N)]

    #約数を列挙
    def make_divisors(n):
        lower_divisors , upper_divisors = [], []
        i = 1
        while i*i <= n:
            if n % i == 0:
                lower_divisors.append(i)
                if i != n // i:
                    upper_divisors.append(n//i)
            i += 1
        return lower_divisors + upper_divisors[::-1]
        
    divisors_dict = dict()

    for A in set(A_list):
        divisors_dict[A] = set(make_divisors(A))

    all_divisors = set()
    common_divisors = set()
    common_divisors |= divisors_dict[A_list[0]]
    all_divisors |= divisors_dict[A_list[0]]
    is_pairwise = True

    for i in range(1,len(A_list)):
        A_divisors = divisors_dict[A_list[i]]
        common_divisors &= A_divisors 
        
        if is_pairwise and len(all_divisors&A_divisors)!=1:
            is_pairwise = False
        else:
            all_divisors |= A_divisors
        
    #約数を全部積み重ねて、共通のものが1以外に全くなかったらpaiwise
    #全部に含まれる約数が、1以外になければ、setwise

    if is_pairwise:
        print("pairwise coprime")
    elif len(common_divisors) == 1:
        print("setwise coprime")
    else:
        print("not coprime")

get_ans()

### FIXED CODE ###

import math
import sys
from functools import lru_cache
sys.setrecursionlimit(10000000)

N = int(input())
A_list = [int(e) for e in input().split()]

#pairwise coprime …… 素因数分解したとき、共通のものが1個もない
#setwise coprime　…… 素因数分解したとき、全てで共通のものがない

#試し割の結果の辞書を求める
def make_trial_division_dict(n):
    #import math
    td_dict = dict()
    for i in range(2,n+1):
        if i not in td_dict:
            td_dict[i] = i
            for j in range(2,1+n//i):
                if j*i not in td_dict:
                    td_dict[j*i] = i
    td_dict[1] = 1
    return td_dict

#試し割結果の辞書を利用して素因数分解する
@lru_cache(maxsize=None)
def high_speed_prime_factorization(n):
    pf_list = list()
    pf_list.append(td_dict[n])
    
    if n//td_dict[n] == 1:
        if n!=1:
            pf_list.append(1)
        return pf_list
    else:
        pf_list.extend(high_speed_prime_factorization(n//td_dict[n]))
        return pf_list

td_dict = make_trial_division_dict(max(A_list))

all_pf = set()    #含まれる素因数がすべて集約される
common_pf = set() #共通する素因数が集約される
all_pf |= set(high_speed_prime_factorization(A_list[0]))
common_pf |= set(high_speed_prime_factorization(A_list[0]))
is_pairwise = True

#print(A_list[0],set(high_speed_prime_factorization(A_list[0])))

for i in range(1,len(A_list)):
    A_pf = set(high_speed_prime_factorization(A_list[i]))
    common_pf &= A_pf 
    
    #print(A_list[i],set(high_speed_prime_factorization(A_list[i])))
    
    if is_pairwise and len(all_pf&A_pf)!=1: #1は共通で含まれる
        is_pairwise = False
    else:
        all_pf |= A_pf

if is_pairwise:
    print("pairwise coprime")
elif len(common_pf) == 1: #1は共通で含まれる
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

import sys
from itertools import combinations

input = sys.stdin.readline

N = int(input())
A = list(map(int,input().split()))
B = list(combinations(A,2))
sum = 0
for i in range(len(B)):
    sum += B[i][0]*B[i][1]

print(sum%1000000007)



### FIXED CODE ###

import sys
input = sys.stdin.readline

def multipleSum(A, n):
    sum = 0
    for i in range(n):
        sum += A[i]
    mulsum = sum*sum
    insum = 0
    for i in range(n):
        insum+=A[i]*A[i]
    return (mulsum-insum)//2

N = int(input())
A = list(map(int,input().split()))
n = len(A)
print(multipleSum(A,n)%1000000007)
### BUGGY CODE ###

import sys

lines = sys.stdin.readlines()

X = lines[0].split(' ')
N = int(X[0])
M = int(X[1])

H = []
Y = []

for i in range(N):
    H=lines[1].split(' ')

for j in range(M):
    A = int(lines[j+2].split(' ')[0])
    B = int(lines[j+2].split(' ')[1])
    if int(H[A-1]) <= int(H[B-1]):      
      Y.append(A-1)
    if int(H[B-1]) <= int(H[A-1]):
      Y.append(B-1)
Z = len(set(Y))
print(N-Z)


### FIXED CODE ###

import sys

lines = sys.stdin.readlines()

X = lines[0].split(' ')
N = int(X[0])
M = int(X[1])

H = []
Y = []

H=lines[1].split(' ')

for j in range(M):
    A = int(lines[j+2].split(' ')[0])
    B = int(lines[j+2].split(' ')[1])
    if int(H[A-1]) <= int(H[B-1]):      
      Y.append(A-1)
    if int(H[B-1]) <= int(H[A-1]):
      Y.append(B-1)
Z = len(set(Y))
print(N-Z)
### BUGGY CODE ###

N = int(input())
a = [int(i) for i in input().split()]
b =[]

for i in range(1,N+1):
    b.append(a.index(i) + 1)

print(*b)

### FIXED CODE ###

N = int(input())
a = [int(i) for i in input().split()]
b = sorted(a)
c = []

dic = dict(zip(a , b))

for i in range(1,N+1):
    c.append(dic[i])

print(*c)
### BUGGY CODE ###

n, c = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [[0]*(c+1) for i in range(n+1)]
dp[0][0] = 1

# forループを更に一つ潰す必要あり
for i in range(n):
    for x in range(a[i], b[i] + 1):
        for all_num in range(c+1):
            for j in range(all_num + 1):
                # i番目の子供に、j個の飴を配る
                dp[i+1][all_num] += x**j * dp[i][all_num - j]
                dp[i+1][all_num] %= MOD
print(dp[-1][-1])

### FIXED CODE ###

n, c = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [[0]*(c+1) for i in range(n+1)]
dp[0][0] = 1

ruiseki = [[0] * (410) for _ in range(c+1)]
for i in range(c + 1):
    for j in range(409):
        ruiseki[i][j + 1] = ruiseki[i][j] + pow(j, i, MOD)
        ruiseki[i][j + 1] %= MOD
  
for i in range(n):
    for all_num in range(c + 1):
        for j in range(all_num + 1):
            # i番目の子供に、j個の飴を配る
            dp[i+1][all_num] += (ruiseki[j][b[i]+1] - ruiseki[j][a[i]]) * dp[i][all_num - j]
            dp[i+1][all_num] %= MOD
print(dp[-1][-1])
### BUGGY CODE ###

import numpy as np

n, k = map(int, input().split())
a = list(map(int, input().split()))
dp = np.zeros((k + 1, n + 1))

for i in range(n + 1):
    dp[0][i] = 1
for i in range(a[0] + 1):
    dp[i][1] = 1

for i in range(1, k + 1):
    for j in range(2, n + 1):
        dp[i][j] = sum(dp[max(0, i - a[j - 1]):i + 1, j - 1]) % (10 ** 9 + 7)
print(int(dp[k][n]))

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
dp = [[0] * (k + 1) for _ in range(n + 1)]

for i in range(n + 1):
    dp[i][0] = 1
for i in range(a[0] + 1):
    dp[1][i] = 1

for i in range(2, n + 1):
    for j in range(1, k + 1):
        dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod
        if j > a[i - 1]:
            dp[i][j] -= (dp[i - 1][j - a[i - 1] - 1]) % mod
        dp[i][j] %= mod
print(dp[n][k])
### BUGGY CODE ###

def main():
    from collections import deque
    n, m, *ab = map(int, open(0).read().split())
    job = [[] for _ in range(1 + max(ab))]
    for i, j in zip(*[iter(ab)] * 2):
        job[i].append(j)

    ans = 0
    t = []
    for i in range(1, m + 1):
        t += job[i]
        if len(t) == 0:
            continue
        else:
            m = max(t)
            t.remove(m)
            ans += m

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import heapq
    n, m, *ab = map(int, open(0).read().split())
    l = [[] for _ in range(m + 1)]
    for i, j in zip(*[iter(ab)] * 2):
        if i <= m:
            l[i].append(-j)

    ans = 0
    h = []
    for i in range(1, m + 1):
        g = l[i]
        for j in g:
            heapq.heappush(h, j)
        if len(h) > 0:
            x = heapq.heappop(h)
            ans += x

    print(-ans)


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

import sys
sys.setrecursionlimit(300000)
from fractions import gcd
from collections import defaultdict

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N = I()
d = defaultdict(int)
zero = 0
for i in range(N):
    a, b = MI()
    if a == 0 and b == 0:
        zero += 1
        continue
    g = gcd(a, b)
    a, b = a // g, b // g
    minus = (-1) ** ((a < 0) + (b < 0))
    d[(minus * abs(a), abs(b))] += 1

ans = 1
seen = set()
for a, b in d:
    if (a, b) not in seen:
        if (a, b) in [(1, 0), (0, 1)]:
            ainv, binv = b, a
        else:
            ainv, binv = b * (1 if a < 0 else -1), abs(a)
        lans = (2 ** d[(a, b)] - 1)
        lans += (2 ** d[(ainv, binv)] - 1) if d.get((ainv, binv)) is not None else 0
        lans += 1
        ans = ans * lans % MOD
        seen.add((a, b))
        seen.add((ainv, binv))
ans = (ans + zero) % MOD
print((ans + MOD - 1) % MOD)

### FIXED CODE ###

import sys
sys.setrecursionlimit(300000)
from fractions import gcd
from collections import defaultdict

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N = I()
d = defaultdict(int)
zero = 0
for i in range(N):
    a, b = MI()
    if a == 0 and b == 0:
        zero += 1
        continue
    g = gcd(a, b)
    a, b = a // g, b // g
    minus = (-1) ** ((a < 0) + (b < 0))
    d[(minus * abs(a), abs(b))] += 1

ans = 1
seen = set()
for a, b in d:
    if (a, b) not in seen:
        if (a, b) in [(1, 0), (0, 1)]:
            ainv, binv = b, a
        else:
            ainv, binv = b * (1 if a < 0 else -1), abs(a)
        lans = (2 ** d[(a, b)] - 1)
        lans += (2 ** d[(ainv, binv)] - 1) if d.get((ainv, binv)) is not None else 0
        lans += 1
        ans = ans * lans % MOD
        seen.add((a, b))
        seen.add((ainv, binv))
ans = (ans + zero) % MOD
print((ans + MOD - 1) % MOD)
### BUGGY CODE ###

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

L =[(v,i) for i,v in enumerate(_L)]
L = sorted(L,key = lambda x:-x[0])

dp = [[0]*(N+1) for _ in range(N+1)]

for i in range(N):#i番目の数字まで見た
    for k in range(N):#k回(i-pi)のパターン
        if k>i:
            continue
        val,ind = L[i]
        dp[i+1][k+1] = max(dp[i+1][k+1],dp[i][k] + val * abs(ind-k))#先頭からk番目に動かす
        dp[i+1][k] = max(dp[i+1][k],dp[i][k]+val * abs(N-1-(i-k)-ind))#すでに後ろからi-k個は使ってる=>後ろからN- (i-k)+1番目に動かす
print(max(dp[-1]))




### FIXED CODE ###

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

L =[(v,i) for i,v in enumerate(_L)]
L = sorted(L,key = lambda x:-x[0])

dp = [[0]*(N+1) for _ in range(N+1)]

for i in range(N):#i番目の数字まで見た
    for k in range(N):#k回(i-pi)のパターン
        if k>i:
            continue
        val,ind = L[i]
        dp[i+1][k+1] = max(dp[i+1][k+1],dp[i][k] + val * abs(ind-k))#先頭からk番目に動かす
        dp[i+1][k] = max(dp[i+1][k],dp[i][k]+val * abs(N-1-(i-k)-ind))#すでに後ろからi-k個は使ってる=>後ろからN- (i-k)+1番目に動かす
print(max(dp[-1]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
n, q = map(int,input().split())
ab = [[0 for i in range(n)] for j in range(n)]
d = [[] for i in range(n)]
for i in range(n-1):
    ai, bi = map(int,input().split())
    ab[ai-1][bi-1] = 1
    ab[bi-1][ai-1] = 1
    d[ai-1].append(bi-1)
    d[bi-1].append(ai-1)

#parentを返す
p = [0 for i in range(n)]
#訪問済
x = [0 for i in range(n)]
def f(v):
    x[v] = 1
    for di in d[v]:
        if x[di] == 0:
            p[di] = v
            f(di)
f(0)

#point
px = [0 for i in range(n)]

for i in range(q):
    pi,xi = map(int,input().split())
    px[pi-1] +=xi

#sumpoint
sp = [float("inf") for i in range(n)]
sp[0] = px[0]

def g(v):
    if v == 0:
        return px[v]
    else:
        if sp[v] == float("inf"):
            point = px[v]+g(p[v])
            sp[v] = point
            return point
        else:
            return sp[v]
for i in range(n):
    if i ==0:
        print(px[0])
    else:
        print(g(i))


### FIXED CODE ###

from collections import deque
n, q = map(int,input().split())
d = [[] for i in range(n)]
for i in range(n-1):
    ai, bi = map(int,input().split())
    d[ai-1].append(bi-1)
    d[bi-1].append(ai-1)
#point
px = [0 for i in range(n)]
for i in range(q):
    pi,xi = map(int,input().split())
    px[pi-1] += xi
sp = [0 for i in range(n)]
s = deque()
s.append(0)
visited = [False for i in range(n)]
while len(s) > 0:
    x = s.popleft()
    visited[x] = True
    sp[x] += px[x]
    for xc in d[x]:
        if not visited[xc]:
            s.append(xc)
            sp[xc] += sp[x]
for i in range(n):
    print(sp[i])
### BUGGY CODE ###

n=int(input())
ans=0
for i in range(n):
    ans+=i
print(ans)

### FIXED CODE ###

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

import collections as cc
n=int(input())
l=list(map(int,input().split()))
ff=cc.Counter(l)
ff=dict(ff)
ans=[]
for i in range(n):
    f=ff.copy()
    f[l[i]]=max(0,f[l[i]]-1)
    t=0
    for i in f:
        x=f[i]
        t+=(x*(x-1))//2
    ans.append(t)
for i in ans:
    print(i)
    
    

### FIXED CODE ###

import collections as cc
n=int(input())
l=list(map(int,input().split()))
ff=cc.Counter(l)
ff=dict(ff)
ans=0
for i in ff:
    x=ff[i]
    ans+=(x*(x-1))//2
v={}
for i in set(l):
    vv=max(ff[i]-1,0)
    te=ans-(ff[i]*(ff[i]-1))//2+(vv*(vv-1))//2
    v[i]=te
for i in l:
    print(v[i])
### BUGGY CODE ###

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

cards = sorted(list(map(int, input().split())), reverse=True)

for i in range(M):
    B, C = map(int, input().split())
    cards.extend([C]*B)
    cards = sorted(cards, reverse=True)
    cards = cards[:N]

total = 0
for card in cards:
    total += card
print(total)

### FIXED CODE ###

import heapq
from collections import defaultdict

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

As = map(int, input().split())
counts = defaultdict(int)
for A in As:
    counts[A] += 1
h = sorted(counts.keys())

for i in range(M):
    B, C = map(int, input().split())

    if C not in counts:
        heapq.heappush(h, C)
    counts[C] += B
    if len(h) > N:
        v = heapq.heappop(h)
        del counts[v]

total_count = 0
total = 0
for k in sorted(h, reverse=True):
    c = counts[k]
    c = min(c, N - total_count)
    total += k * c
    total_count += c
    if total_count > N:
        break
print(total)
### BUGGY CODE ###

import sys
def rec(N,dp,i,j,k):
    if dp[i][j][k]>=0:return dp[i][j][k]
    if all([i==0,j==0,k==0]):return 0.0
    res=0.0
    if i>0:res+=rec(N,dp,i-1,j,k)*i
    if j>0:res+=rec(N,dp,i+1,j-1,k)*j
    if k>0:res+=rec(N,dp,i,j+1,k-1)*k
    res+=N
    res*=1.0/(i+j+k)
    dp[i][j][k]=res
    return dp[i][j][k]
def main():
    N=int(sys.stdin.readline())
    a=tuple(map(int,sys.stdin.readline().split()))
    n1,n2,n3=a.count(1),a.count(2),a.count(3)
    dp=[[[-1 for _ in range(N+1)] for _ in range(N+1)] for _ in range(N+1)]
    print(rec(N,dp,n1,n2,n3))
if __name__=='__main__':main()

### FIXED CODE ###

import sys
def rec(N,dp,i,j,k):
    if dp[i][j][k]>=0.0:return dp[i][j][k]
    if all([i==0,j==0,k==0]):return 0.0
    res=0.0
    if i>0:res+=rec(N,dp,i-1,j,k)*i
    if j>0:res+=rec(N,dp,i+1,j-1,k)*j
    if k>0:res+=rec(N,dp,i,j+1,k-1)*k
    res=(res+N)*1.0/(i+j+k)
    dp[i][j][k]=res
    return dp[i][j][k]
def main():
    N=int(sys.stdin.readline())
    a=tuple(map(int,sys.stdin.readline().split()))
    n1,n2,n3=a.count(1),a.count(2),a.count(3)
    dp=[[[-1.0 for _ in range(n3+1)] for _ in range(n2+n3+1)] for _ in range(n1+n2+n3+1)]
    print(rec(N,dp,n1,n2,n3))
if __name__=='__main__':main()
### BUGGY CODE ###

import bisect

N, M = map(int, input().split())
task = []
for i in range(N):
    a, b = map(int, input().split())
    task.append((a, b))

task.sort()

wa = []
ans = 0
j = 0
for i in range(M):
    while j < N and task[j][0] == i + 1:
        bisect.insort_right(wa, task[j][1])
        j += 1
    if wa:
        ls = wa[-1]
        ans += ls
        del (wa[-1])

print(ans)


### FIXED CODE ###

import bisect
import heapq

N, M = map(int, input().split())
task = []
for i in range(N):
    a, b = map(int, input().split())
    task.append((a, b))

task.sort()

wa = []
ans = 0
j = 0
for i in range(M):
    while j < N and task[j][0] == i + 1:
        heapq.heappush(wa,-task[j][1])
        j += 1
    if wa:
        ans -= heapq.heappop(wa)

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

A = str(input())
B = str(input())
C = str(input())

n = "a"
while 1:
  if n == "a":
    n = A[0]
    A = A[1:]
    if len(A) == 0:
      print("A")
      quit()
    elif n == "b":
      n = B[0]
      B = B[1:]
      if len(B) == 0:
        print("B")
        quit()
    elif n == "c":
      n = C[0]
      C = C[1:]
      if len(C) == 0:
        print("C")
        quit()

### FIXED CODE ###

A = str(input())
B = str(input())
C = str(input())

n = "a"
while 1:
  if n == "a":
    if len(A) == 0:
      print("A")
      quit()
    n = A[0]
    A = A[1:]
  elif n == "b":
    if len(B) == 0:
      print("B")
      quit()
    n = B[0]
    B = B[1:]
  elif n == "c":
    if len(C) == 0:
      print("C")
      quit()
    n = C[0]
    C = C[1:]
### BUGGY CODE ###

from collections import deque

def bfs(grid, costs, queue, wall):
    ans = 0
    dxy = [(1,0), (-1,0), (0,1), (0,-1)]
    while queue:
        y,x = queue.popleft()
        for dy, dx in dxy:
            y_,x_ = y+dy,x+dx
            if grid[y_][x_] == wall:
                continue
            queue.append([y_,x_])
            grid[y_][x_] = wall
            costs[y_][x_] = costs[y][x] + 1
            ans = max(ans, costs[y_][x_])
    return ans

import sys
input = sys.stdin.readline
H,W = map(int, input().split())
wall = '#'
queue = deque([])
edges = [wall for _ in range(W+2)]
grid = [edges]
costs = [[0 for _ in range(W+2)]]

for i in range(1,H+1):
    S = [wall]+list(input().strip())+[wall]
    for j in range(1,W+1):
        if S[j] == wall:
            queue.append([i,j])
    grid.append(S)
    costs.append([0 for _ in range(W+2)])
grid.append(edges)
print(bfs(grid, costs, queue, wall))


### FIXED CODE ###

from collections import deque

def bfs(grid, queue, wall):
    ans = 0
    dxy = [(1,0), (-1,0), (0,1), (0,-1)]
    while queue:
        cnt,y,x = queue.popleft()
        for dy, dx in dxy:
            y_,x_ = y+dy,x+dx
            if grid[y_][x_] == wall:
                continue
            queue.append([cnt+1,y_,x_])
            grid[y_][x_] = wall
            ans = max(ans, cnt+1)
    return ans

H,W = map(int, input().split())
wall = '#'
queue = deque([])
edges = [wall for i in range(W+2)]
grid = [edges]

for i in range(1,H+1):
    S = [wall]+list(input().strip())+[wall]
    for j in range(1,W+1):
        if S[j] == wall:
            queue.append([0,i,j])
    grid.append(S)
grid.append(edges)
print(bfs(grid, queue, wall))
### BUGGY CODE ###

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

res=0
for i in range(n):
    print(a.count(i+1))


### FIXED CODE ###

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

b=collections.Counter(a)
for i in range(1,n+1):
    print(b[i])
### BUGGY CODE ###

import sys


n, x, y = map(int, sys.stdin.readline().split())
dist = []
for i in range(n):
    dist.append([])
    for j in range(n):
        dist[i].append(abs(j - i))

dist[x-1][y-1] = 1
def get_dist(a,b):
    if a < b:
        return dist[a][b]
    else:
        return dist[b][a]
x -= 1
y -= 1
# update the x
# first, range (x,y) 
for i in range(x+2, y):
    dist[x][i] = min(dist[x][i], dist[i][y] + 1)
# them, range(y,n)
for i in range(y+1, n):
    dist[x][i] = dist[y][i] + 1
# range[0,x) 
for i in range(x):
    # to (x, y)
    for j in range(x+1, y):
        dist[i][j] = min(dist[i][j], dist[j][y] + dist[i][x] + 1)
    # to [y, n)
    for j in range(y,n):
        dist[i][j] = dist[i][x] + 1 + dist[y][j]

# range(x, y)
for i in range(x+1, y):
    # to (i,y)
    for j in range(i+1, y):
        dist[i][j] = min(dist[i][j], dist[x][i] + dist[j][y] + 1)

    # to [y, n)
    for j in range(y, n):
        dist[i][j] = min(dist[i][j], dist[x][i] + dist[y][j] + 1)
final = [0]*(n-1)
for i in range(n-1):
    for j in range(i+1, n):
        final[dist[i][j]-1] += 1
 
for one in final:
    print(one)

### FIXED CODE ###

import sys
n, x, y = map(int, sys.stdin.readline().split())

x -= 1
y -= 1
    
final = [0]*(n-1)


for i in range(n-1):
    for j in range(i+2, n):
        if j < x or i > y:
            dist = j-i
        else:
            dist = min([j - i, abs(x-i) + 1 + abs(y-j), abs(y-i) + 1 + abs(x-j)])
        final[dist-1] += 1 
final[0] = n
res = [str(one) for one in final]
print ("\n".join(res))
### BUGGY CODE ###

def solve(s, t):
    ok=1
    while True:
        if t*ok not in s:
            ng = ok
            ok = ng>>1
            break
        ok <<= 1
    if ng == 1:
        return 0
    while ok+1 < ng:
        c = (ok+ng)>>1
        if t*c in s:
            ok = c
        else:
            ng = c
    return ok

S = input()
T = input()
nS = len(S)
nT = len(T)
S = S*((nT//nS)*3+4)
ans = solve(S, T)
if T*(ans+1) in S*2:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)


import sys
import numpy as np

def z_algo(S):  # [z_algo, "i8[:](i8[:])"],
    # Z-algoirhm  O(n)
    # Z[i] := S と S[i:] で prefix が何文字一致しているか
    # 検証1: https://atcoder.jp/contests/abc150/submissions/15829530
    # 検証2: https://atcoder.jp/contests/abc141/submissions/15855247
    i, j, n = 1, 0, len(S)
    Z = np.zeros(S.shape, dtype=np.int64)
    Z[0] = n
    while i < n:
        while i+j < n and S[j] == S[i+j]:
            j += 1
        if j == 0:
            i += 1
            continue
        Z[i] = j
        d = 1
        while i+d < n and d+Z[d] < j:
            Z[i+d] = Z[d]
            d += 1
        i += d
        j -= d
    return Z

def solve(s, t):
    ns = len(s)
    nt = len(t)
    n = max(ns, nt) * 2
    ts = np.empty(n*4, dtype=np.int64)
    ts[:n*2] = t[np.arange(2*n, dtype=np.int64) % nt]
    ts[n*2:] = s[np.arange(2*n, dtype=np.int64) % ns]
    Z = z_algo(ts)
    ma = Z[n*2:].max()
    if ma > n:
        return -1
    else:
        return ma // nt

numba_compile([
    [z_algo, "i8[:](i8[:])"],
    [solve, "i8(i1[:],i1[:])"],
])

def main():
    s = np.frombuffer(sys.stdin.buffer.readline()[:-1], dtype=np.int8).copy()
    t = np.frombuffer(sys.stdin.buffer.readline()[:-1], dtype=np.int8).copy()
    ans = solve(s, t)
    print(ans)

main()
### BUGGY CODE ###

mod = 998244353
s = list(map(int, list(input())))
n = len(s)
dp = [[0]*(sum(s)+1) for _ in range(2*n+1)]
dp[0][0] = 1
curr = curb = 0
for i in range(2*n):
  if i < n:
    curb += s[i]
    curr += 2 - s[i]
  for j in range(min(i, curb)+1):
    if dp[i][j]:
      dp[i][j] %= mod
      if i - j < curr:
        dp[i+1][j] += dp[i][j]
      if j < curb:
        dp[i+1][j+1] += dp[i][j]
print(dp[2*n][curb])   

### FIXED CODE ###

mod = 998244353
s = list(map(int, list(input())))
n = len(s)
dp = [[0]*(sum(s)+1) for _ in range(2*n+1)]
dp[0][0] = 1
curr = curb = 0
for i in range(2*n):
  if i < n:
    curb += s[i]
    curr += 2 - s[i]
  for j in range(min(i, curb)+1):
    if dp[i][j]:
      dp[i][j] %= mod
      if i - j < curr:
        dp[i+1][j] += dp[i][j]
      if j < curb:
        dp[i+1][j+1] += dp[i][j]
print(dp[2*n][curb] % mod)