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

import copy
n=int(input())
x=list(input())
b=[]
for i in range(2**19):
  b.append(format(i,'0'+str(19)+'b'))
ct=[0]*(n+1)
for i in range(1,n):
  ct1=0
  for j in range(len(b[i])):
    if b[i][j]=='1':
      ct1+=1
  ct[i]=i%ct1

CT=0
for i in range(n):
  if x[i]=='1':
    CT+=1

moda=[1]
modb=[1]
modc=[1]
for i in range(n-1):
  if CT>=2:
    moda.append(moda[-1]*2%(CT-1))
  if CT>=1:
    modb.append(modb[-1]*2%CT)
  modc.append(modc[-1]*2%(CT+1))


x.reverse()
za=0
zb=0
zc=0
for i in range(n):
  if x[i]=='1':
    if CT>=2:
      za+=moda[i]
      za%=(CT-1)
    if CT>=1:
      zb+=modb[i]
      zb%=CT
    zc+=modc[i]
    zc%=(CT+1)
x.reverse()
moda.reverse()
modc.reverse()

for i in range(n):
  y=copy.copy(x)
  y2=y[i]
  y[i]=str(1-int(y[i]))
  ct1=0
  for j in range(n):
    if y[j]=='1':
      ct1+=1
  if ct1==0:
    print(0)
  else:
    if y2=='1':
      z=za
      z-=moda[i]
      z%=ct1
    else:
      z=zc
      z+=modc[i]
      z%=ct1
    
    ans=1
    while z!=0:
      z=ct[z]
      ans+=1
    print(ans)

### FIXED CODE ###

import copy
n=int(input())
x=list(input())
b=[]
for i in range(2**18):
  b.append(format(i,'0'+str(18)+'b'))
  if i>n+1:
    break
ct=[0]*(n+1)
for i in range(1,n):
  ct1=0
  for j in range(len(b[i])):
    if b[i][j]=='1':
      ct1+=1
  ct[i]=i%ct1

CT=0
for i in range(n):
  if x[i]=='1':
    CT+=1

moda=[1]
modb=[1]
modc=[1]
for i in range(n-1):
  if CT>=2:
    moda.append(moda[-1]*2%(CT-1))
  if CT>=1:
    modb.append(modb[-1]*2%CT)
  modc.append(modc[-1]*2%(CT+1))


x.reverse()
za=0
zb=0
zc=0
for i in range(n):
  if x[i]=='1':
    if CT>=2:
      za+=moda[i]
      za%=(CT-1)
    if CT>=1:
      zb+=modb[i]
      zb%=CT
    zc+=modc[i]
    zc%=(CT+1)
x.reverse()
moda.reverse()
modc.reverse()

for i in range(n):
  y2=x[i]
  if y2=='1':
    ct1=CT-1
  else:
    ct1=CT+1
  if ct1==0:
    print(0)
  else:
    if y2=='1':
      z=za
      z-=moda[i]
      z%=ct1
    else:
      z=zc
      z+=modc[i]
      z%=ct1
    
    ans=1
    while z!=0:
      z=ct[z]
      ans+=1
    print(ans)
### BUGGY CODE ###


# -*- coding: utf-8 -*-
def slv():
    import sys
    input = sys.stdin.readline
    N, M, L = list(map(int, input().rstrip('\n').split()))
    g = [[sys.maxsize]*(N) for _ in range(N)]
    gg = [[sys.maxsize]*(N) for _ in range(N)]

    for i in range(N):
        g[i][i] = 0
    for _ in range(M):
        a, b, c = list(map(int, input().rstrip('\n').split()))
        if c <= L:
            g[a-1][b-1] = c
            g[b-1][a-1] = c
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                g[i][j] = min(g[i][j], g[i][k] + g[k][j])
    
    for u in range(N):
        for v in range(N):
            if g[u][v] <= L:
                gg[u][v] = 1
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                gg[i][j] = min(gg[i][j], gg[i][k] + gg[k][j])

    Q = int(input())
    for _ in range(Q):
        s, t = list(map(int, input().rstrip('\n').split()))
        c = gg[s-1][t-1]
        if c != sys.maxsize:
            print(c-1)
        else:
            print(-1)



def main():
    slv()

if __name__ == '__main__':
    main()


### FIXED CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    n, m, l = list(map(int, input().rstrip('\n').split()))
    INF = 10 ** 11
    w = [[INF] * n for _ in range(n)]
    wl = [[INF] * n for _ in range(n)]

    for i in range(n):
        w[i][i] = 0

    for i in range(m):
        a, b, c = list(map(int, input().rstrip('\n').split()))
        if c <= l:
            w[a - 1][b - 1] = c
            w[b - 1][a - 1] = c

    for i in range(n):
        for j in range(n):
            for k in range(n):
                w[j][k] = min(w[j][k], w[j][i] + w[i][k])

    for i in range(n):
        for j in range(n):
            if w[i][j] <= l:
                wl[i][j] = 1
    for i in range(n):
        for j in range(n):
            for k in range(n):
                wl[j][k] = min(wl[j][k], wl[j][i] + wl[i][k])

    q = int(input().rstrip('\n'))
    for i in range(q):
        s, t = list(map(int, input().rstrip('\n').split()))
        if wl[s-1][t-1] == INF:
            print(-1)
        else:
            print(wl[s-1][t-1] - 1)


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

n, w = map(int, input().split())
item = [list(map(int, input().split())) for i in range(n)]

max_v = 100005

dp = [[float('inf') for i in range(max_v)] for j in range(n + 1)]

dp[0][0] = 0
for i in range(n):
    for sum_v in range(max_v):
        if sum_v - item[i][1] >= 0:
            dp[i + 1][sum_v] = min(dp[i + 1][sum_v], dp[i][sum_v - item[i][1]] + item[i][0])
        dp[i + 1][sum_v] = min((dp[i + 1][sum_v], dp[i][sum_v]))

ans = 0
for sum_v in reversed(range(max_v)):
    if dp[-1][sum_v] <= w:
        print(sum_v)
        break

### FIXED CODE ###

n, w = map(int, input().split())
item = [list(map(int, input().split())) for i in range(n)]

max_v = 100005

dp = [[float('inf')] * max_v for j in range(n + 1)]
dp[0][0] = 0

for i in range(n):
    for sum_v in range(max_v):
        if sum_v - item[i][1] >= 0:
            dp[i + 1][sum_v] = min(dp[i + 1][sum_v], dp[i][sum_v - item[i][1]] + item[i][0])
        dp[i + 1][sum_v] = min((dp[i + 1][sum_v], dp[i][sum_v]))

for sum_v in reversed(range(max_v)):
    if dp[-1][sum_v] <= w:
        print(sum_v)
        break
### BUGGY CODE ###

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

def gcd(x, y):
    if x == 0:return y
    else: return gcd(y % x, x)

is_prime = [True] * 1100000

is_prime[0] = is_prime[1] = False

for i in range(2, 1100000):
    if not is_prime[i]:continue
    for j in range(i*i, 1100000, i):
        is_prime[j] = False

small_prime = [p for p in range(1100) if is_prime[p]]
        
g = 0

for a in A:
    g = gcd(g, a)

if g != 1:
    print("not coprime")
    exit()

used = [False] * 1100000
primes = [a for a in A if is_prime[a]]
for p in primes:
    used[p] = True

not_primes = [a for a in A if not is_prime[a]]

for a in not_primes:
    for p in small_prime:
        if a % p != 0:continue
        if used[p]:
            print("setwise coprime")
            exit()
        used[p] = True
        while a % p == 0:
            a //= p
    if a > 1:
        if used[a]:
            print("setwise coprime")
            exit()
        used[a] = True

print("pairwise coprime")




### FIXED CODE ###

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

def gcd(x, y):
    if x == 0:return y
    else: return gcd(y % x, x)

is_prime = [True] * 1100000

is_prime[0] = is_prime[1] = False

for i in range(2, 1100000):
    if not is_prime[i]:continue
    for j in range(i*i, 1100000, i):
        is_prime[j] = False

small_prime = [p for p in range(1100) if is_prime[p]]
        
g = 0

for a in A:
    g = gcd(g, a)

if g != 1:
    print("not coprime")
    exit()

used = [False] * 1100000
primes = [a for a in A if is_prime[a]]
for p in primes:
    used[p] = True

not_primes = [a for a in A if not is_prime[a]]

for a in not_primes:
    for p in small_prime:
        if a == 1:break
        if a % p != 0:continue
        if used[p]:
            print("setwise coprime")
            exit()
        used[p] = True
        while a % p == 0:
            a //= p
    if a > 1:
        if used[a]:
            print("setwise coprime")
            exit()
        used[a] = True

print("pairwise coprime")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())
#k, x = map(int, input().split())
al = list(map(int, input().split()))
#l=[list(map(int,input().split())) for i in range(n)]
money=[]
m=2
day=0
def dfs(cur, day, kabu):
    global money
    if day==n:
        money.append(cur)
        return
    # buy
    for v in range(0,cur//al[day]+1):
        buynum=v*al[day]
        nowkabu=kabu+v
        dfs(cur-v*al[day],day+1,kabu+v)
        #A.append(v)
        #dfs(A)
        #A.pop()
    # sell
    for w in range(0,kabu+1):
        sellnum=w
        dfs(cur+w*al[day],day+1,kabu-w)
dfs(1000,day,0)
print(max(money))

### FIXED CODE ###

n=int(input())
#n,k=map(int,input().split())
al=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]
stock = 0
money = 1000
for i in range(n-1):
    sell = stock*al[i]
    stock = 0
    money += sell
    if al[i] < al[i+1]:# buy
        buynum = money//al[i]
        stock= buynum
        money -= buynum*al[i]

print(money + stock*al[n-1])
### BUGGY CODE ###

#import sys
#input = sys.stdin.readline
#input = sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

#import numpy as np
from collections import defaultdict

def main():

	mod=10**9+7

	n=II()
	s=input()
	s=len(s)

	pp=[1]
	for i in range(n+10):
		pp.append(pp[-1]*25%mod)


	nn=n+s

	comb=[1]
	for i in range(1,n+10):
		comb.append(comb[-1]*(nn-i+1)*pow(i,mod-2,mod)%mod)
	#print(comb)


	ans=0

	for i in range(n+1):
		ans+=(pp[i]*comb[i])%mod
		ans%=mod
	print(ans)












if __name__ == "__main__":
	main()


### FIXED CODE ###

#import sys
#input = sys.stdin.readline
#input = sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

#import numpy as np
from collections import defaultdict

def main():

	mod=10**9+7

	n=II()
	s=input()
	s=len(s)

	pp=[1]
	for i in range(n+10):
		pp.append(pp[-1]*25%mod)


	nn=n+s

	comb=[1]
	for i in range(1,n+10):
		comb.append(comb[-1]*(nn-i+1)*pow(i,mod-2,mod)%mod)
	#print(comb)


	ans=0

	for i in range(n+1):
		ans+=(pp[i]*comb[i])%mod
		ans%=mod
	print(ans)












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

# from pprint import pprint
n = int(input())
a = map(int, input().split())
a = sorted(((ax, x) for x, ax in enumerate(a)), reverse=True)
dp = [[-1] * (n+1) for _ in range(n+1)]
dp[0][0] = 0
for i, (ax, x) in enumerate(a):
    for j in range(i+1):
        dp[j+1][i-j] = max(dp[j+1][i-j], dp[j][i-j] + ax*abs(x-j))
        dp[j][i-j+1] = max(dp[j][i-j+1], dp[j][i-j] + ax*abs(n-1-x-i+j))
# pprint(dp)
print(max(dp[i][n-i] for i in range(n+1)))


### FIXED CODE ###

#  from pprint import pprint
n = int(input())
a = map(int, input().split())
a = sorted(((ax, x) for x, ax in enumerate(a)), reverse=True)
dp = [[-1] * (n+1) for _ in range(n+1)]
dp[0][0] = 0
for i, (ax, x) in enumerate(a):
    for j in range(i+1):
        dp[j+1][i-j] = max(dp[j+1][i-j], dp[j][i-j] + ax*abs(x-j))
        dp[j][i-j+1] = max(dp[j][i-j+1], dp[j][i-j] + ax*abs(n-1-x-i+j))
# pprint(dp)
print(max(dp[i][n-i] for i in range(n+1)))
### BUGGY CODE ###

# N=頂点数、X,Y=座標
N, X, Y = map(int, input().split())
X -= 1
Y -= 1

# 未セットの値
INF = 10**4

# キューデータ(次の値、最短距離)
queue_list = []

# 最短距離ごとのリスト
min_e_list = [0 for i in range(N)]

for i in range(N):
    # キューデータ初期値をセット
    queue_list.append([i, 0])
    # 最短距離リスト(最短距離)
    min_dist_list = [INF for i in range(N)] 

    # キューデータが空になるまで繰り返す
    while(len(queue_list) != 0):
        
        # 先頭データを取り出す。
        pop_data = queue_list.pop(0)

        # 取り出した座標がセット済みの場合は何もしない
        if(min_dist_list[pop_data[0]] != INF):
            continue

        # 最短距離リストにデータセット
        min_dist_list[pop_data[0]] = pop_data[1]

        # 2重に数えないよう(i < 取り出した座標時)、最短距離ごとのリストにデータセット
        if(i < pop_data[0]):
            min_e_list[pop_data[1]] += 1

        # 1.隣の頂点(次の座標、+1,-1した値)
        if(pop_data[0]+1 < N):
            queue_list.append([pop_data[0]+1, pop_data[1]+1])
        if(pop_data[0] > 0 and pop_data[0]-1 < N):
            queue_list.append([pop_data[0]-1, pop_data[1]+1])
        
        # 2.X,Yで示した値
        if(pop_data[0] == X):
            queue_list.append([Y, pop_data[1]+1])
        if(pop_data[0] == Y):
            queue_list.append([X, pop_data[1]+1])

# 出力
for i,v in enumerate(min_e_list):
    if(i != 0):
        print(v)

### FIXED CODE ###

# N=頂点数、X,Y=座標
N, X, Y = map(int, input().split())

# 最短距離データ
min_dist_list = [0 for i in range(N+1)]

for i in range(1,N+1):
    for j in range(i+1, N+1):
            t_dist = min(abs(j-i), 1+abs(X-i)+abs(Y-j), 1+abs(Y-i)+abs(X-j)) 
            min_dist_list[t_dist] += 1         

for i in range(1, N):
    print(min_dist_list[i])
### BUGGY CODE ###

from functools import reduce
from math import gcd

N = int(input())
print(sum([reduce(gcd, [i, j, k]) for i in range(1, N+1) for j in range(1, N+1) for k in range(1, N+1)]))

### FIXED CODE ###

# from functools import reduce
# from math import gcd
import math

N = int(input())
result = 0
# print(sum([reduce(gcd, [i, j, k]) for i in range(1, N+1) for j in range(1, N+1) for k in range(1, N+1)]))
for i in range(1, N+1):
    for j in range(1, N+1):
        tmp = math.gcd(i, j)
        for k in range(1, N+1):
            result += math.gcd(tmp, k)

print(result)
### BUGGY CODE ###

n = int(input())
sum = 0
for i in range(len(str(n))):
    sum += (n % 10)
    n //= 10
if sum % 9 == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

n = int(input())
if n % 9 == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
for i in range(n):
    ans *= a[i]
if ans > int(1e18):
    print(-1)
    exit()
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
lis = [0] * (n+1)


for i in range(n):
    if a[i] == 0:
        lis[i+1] += 1
    lis[i+1] += lis[i]
#print(lis)
if lis[-1] > 0:
    print(0)
    exit()
for i in range(n):
    ans *= a[i]
    if lis[-1]-lis[i+1] == 0:
        if ans > int(1e18):
            print(-1)
            exit()
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
lr = [list(map(int, input().split())) for _ in range(Q)]
for l, r in lr:
    print(S[l-1:r].count('AC'))


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
cnt = [0]*(N+1)
for i in range(N):
    cnt[i+1] = cnt[i] + (1 if S[i:i+2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(cnt[r-1] - cnt[l-1])
### BUGGY CODE ###

n, k = map(int,input().split())
i = 1
x = k
while True:
  if (x >= n):
    print(i)
    break
  else:
    i = i + 1


### FIXED CODE ###

n, k = map(int,input().split())
i = 1
x = k
while True:
  if (x > n):
    print(i)
    break
  else:
    i = i + 1
    x = x*k
### BUGGY CODE ###

import numpy as np
Nn, Kk, Qq = input().split()
N, K, Q = int(Nn), int(Kk), int(Qq)
a = []
for q in range(Q):
    a.append(int(input()))
r = (np.ones(N) * K).astype(int)
for i in a:
    b = np.ones(N)
    b[i-1] = 0
    r = r - b
print("\n".join(["Yes" if rr > 0 else "No" for rr in r]))

### FIXED CODE ###

import numpy as np
Nn, Kk, Qq = input().split()
N, K, Q = int(Nn), int(Kk), int(Qq)
a = []
for q in range(Q):
    a.append(int(input()))
result = np.ones(N) * (K - Q)
for i in a:
    result[i-1] += 1
result = result > 0
for r in result:
    if r:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

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

L.sort()

s = 0
#print(L)
#print("")
for j in range(N-2):
    for k in range(j+1,N-1):
        # L[i] < L[j]+L[k] となる L[i]の数を求める
        key = L[j]+L[k]
        l = k + 1
        r = N - 1
        while r - l > 1:
            m = l + (r - l) // 2
            if L[m] < key:
                l = m
            else:
                r = m
        if L[k+1] < key <= L[N-1]:
            s += l-k
        elif key <= L[k+1]:
            s += 0
        else:
            s += N-k-1

print(s)

### FIXED CODE ###

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

L.sort()

s = 0

ma = L[N-1]
for j in range(N-2):
    ja = L[j]
    for k in range(j+1,N-1):
        ka = L[k]
        # L[i] < L[j]+L[k] となる L[i]の数を求める
        key = ja + ka
        l = k + 1
        r = N - 1
        while r - l > 1:
            m = l + (r - l) // 2
            if L[m] < key:
                l = m
            else:
                r = m
        kka = L[k+1]
        if kka < key <= ma:
            s += l-k
        elif key <= kka:
            s += 0
        else:
            s += N-k-1

print(s)
### BUGGY CODE ###

import numpy as np

n, m = map(int, input().split())
lst = list(map(int, input().split()))

array = np.array([0]*n)

count = 0
for k, i in enumerate(lst):
    array[:k+1] = (array[:k+1] + i) % m
    count += sum(array[:k+1] == 0)
print(count)

### FIXED CODE ###

import itertools
from math import factorial
from collections import Counter
 
ans = 0
N, L = map(int, input().split())
x = list(map(int, input().split()))
y = itertools.accumulate(x)
y = [e % L for e in y]
#print(y)
#print(y)
so = set(y)
#print(so)
#print(so)
counter = Counter([0]+y)
#print(counter.values())
#print
for i in counter.values():
    #print(ans)
    ans+=i * (i - 1) // 2
print(ans)
### BUGGY CODE ###

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

for _ in range(k):
    lst = [0] * n
    for i in range(n):
        num = a[i]
        if i-num >= 0:
            lst[i-num] += 1
        else:
            lst[0] += 1
        if i+num+1 <= n-1:
            lst[i+num+1] -= 1
    mini = lst[0]
    for i in range(1, n):
        lst[i] += lst[i-1]
        mini = min(mini, lst[i])
    a = lst[:]
    if mini == n:
        break
print(' '.join(map(str, a)))

### FIXED CODE ###

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

for _ in range(k):
    lst = [0] * n
    for i in range(n):
        num = a[i]
        if i-num >= 0:
            lst[i-num] += 1
        else:
            lst[0] += 1
        if i+num+1 <= n-1:
            lst[i+num+1] -= 1
    mini = lst[0]
    for i in range(1, n):
        lst[i] += lst[i-1]
        mini = min(mini, lst[i])
    a = lst[:]
    if mini == n:
        break
print(' '.join(map(str, a)))
### BUGGY CODE ###

N = int(input())
List = list(map(int, input().split()))
res = 0
New_List = sorted(List)
Flag = [1]*N
for i in range(N):
  if Flag[i] ==1:
    for j in range(i+1,N):
      if Flag[j] ==1:
        if New_List[i] == New_List[j]:
          Flag[i] = 0
          Flag[j] = 0
        elif New_List[j] % New_List[i] ==0:
          Flag[j] = 0
        else:
          pass
      elif Flag[j] ==0:
        pass
  else:
    pass
res = Flag.count(1)
print(res)

### FIXED CODE ###

N = int(input())
List = list(map(int, input().split()))
res = 0
List.sort()
K = List[N-1]+1
Flag = [1]*K
for i in range(N):
  if Flag[List[i]] ==1:
    res +=1
    for j in range(List[i],K,List[i]):
      Flag[j] = 0
    if i != N-1 and List[i] == List[i+1]:
      res += -1
print(res)
### BUGGY CODE ###

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

ans=0
for i in range(a,b+1):
  if i%x==0:
    ans+=1
print(ans)

### FIXED CODE ###

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

print(b//x - (a-1)//x)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N,K = map(int,input().split())
 
def modpow(a,n,mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res
 
def modinv(a,mod):
    return modpow(a,mod - 2,mod)
 
def cnk(a,b):
    MOD = 10**9+7
    ret = 1
    for i in range(b):
        ret *= (a-i)
        ret %= MOD
        ret = ret * modinv(i+1,MOD) % MOD
    return ret
 
 
for i in range(1,K+1):
    if i == 1:
        print(N-K+1)
    else:
        print(cnk(N-K+1,i)*cnk(K-1,i-1)%(10**9+7))

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N,K = map(int,input().split())
     
    def modpow(a,n,mod):
        res = 1
        while n > 0:
            if n & 1:
                res = res * a % mod
            a = a * a % mod
            n >>= 1
        return res
     
    def modinv(a,mod):
        return modpow(a,mod - 2,mod)
     
    def cnk(a,b):
        MOD = 10**9+7
        ret = 1
        for i in range(b):
            ret *= (a-i)
            ret %= MOD
            ret = ret * modinv(i+1,MOD) % MOD
        return ret
     
     
    for i in range(1,K+1):
        if i > N - K +1:
            print(0)
        elif i == 1:
            print(N-K+1)
        else:
            print(cnk(N-K+1,i)*cnk(K-1,i-1)%(10**9+7))
if __name__ == '__main__':
    main()
### BUGGY CODE ###

def solve():
    BASE = 10**9 + 7
    MOD = 2**31 - 1  # メルセンヌ素数

    # [Ssの先頭lenRH文字]のハッシュ値を求める
    def getHash(Ss, lenRH):
        hashS = 0
        for S in Ss[:lenRH]:
            hashS *= BASE
            hashS += ord(S)
            hashS %= MOD
        return hashS

    ss = input()
    ts = input()

    cs = set(ss)
    ct = set(ts)
    if len(cs) == 1 and len(ct) == 1 and cs == ct:
        print(-1)
        return

    Ss = ss + ss
    lenS, lenT = len(Ss), len(ts)
    lenRH = lenT

    powB_P = pow(BASE, lenRH)

    hashS = getHash(Ss, lenRH)
    hashT = getHash(ts, lenRH)

    isFounds = [False] * lenS

    Ss += '$' # ダミー
    for i in range(lenS - lenRH + 1):
        # ハッシュ値が一致
        if hashS == hashT:
            isFounds[i] = True
        hashS *= BASE
        hashS += ord(Ss[i+lenRH]) - ord(Ss[i])*powB_P
        hashS %= MOD
#    print(isFounds)

    ans = 0
    for i in range(lenS):
        if not isFounds[i]: continue
        num = 0
        for j in range(i, lenS, lenT):
            if isFounds[j]:
                num += 1
                isFounds[j] = False
            else:
                break
#        ans = max(ans, num)
        if num > ans:
            ans = num

    if lenS % lenT == 0 and ans == lenS//lenT:
        print(-1)
    else:
        print(ans)


solve()


### FIXED CODE ###

def getTableKMP(Ss):
    Ss += '$'
    lenS = len(Ss)
    table = [-1] * lenS
    j = -1
    for i in range(lenS-1):
        while j >= 0 and Ss[i] != Ss[j]:
            j = table[j]
        j += 1
        if Ss[i+1] == Ss[j]:
            table[i+1] = table[j]
        else:
            table[i+1] = j
    return table

def getPosPtnsKMP(Ss, ptn, table):
    anss = []
    lenS, lenP = len(Ss), len(ptn)
    iS, iP = 0, 0
    while iS < lenS:
        if Ss[iS] == ptn[iP]:
            iS += 1
            iP += 1
            if iP == lenP:
                anss.append(iS-lenP)
                iP = table[iP]
        else:
            iP = table[iP]
            if iP == -1:
                iS += 1
                iP = 0
    return anss


Ss = input()
Ts = input()

lenS, lenT = len(Ss), len(Ts)
num = (lenT+lenS-1+lenS-1) // lenS
S2s = Ss * num

tableKMP = getTableKMP(Ts)
posPtns = getPosPtnsKMP(S2s, Ts, tableKMP)

isFounds = [False] * lenS
for pos in posPtns:
    if pos >= lenS:
        break
    isFounds[pos] = True

ans = 0
numDone = 0
for i in range(lenS):
    if not isFounds[i]:
        i = (i+lenT) % lenS
        for num in range(lenS+1):
            if not isFounds[i]:
                ans = max(ans, num)
                numDone += num+1
                break
            i = (i+lenT) % lenS
        else:
            ans = -1
            break

if numDone < lenS:
    ans = -1
print(ans)