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

#coding:utf8
import random

def is_prime3(q,k=1):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

A,B=map(int,input().split())
C=[1]
for i in range(2,min(A,B)+1):
    if A % i == 0 and B % i == 0:
        C.append(i)

ans=[]

for j in C:
    if is_prime3(j):
        ans.append(j)

print(len(ans)+1)
        
    
    
    
        


### FIXED CODE ###

import fractions
import collections
   
A,B = map(int,input().split())
gcd = fractions.gcd(A,B)

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

c = collections.Counter(prime_factorize(gcd))
print(len(list(c.keys()))+1)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import itertools
import sys
input = sys.stdin.readline


def func(i):
    ans = list()
    for a in itertools.combinations(i, 2):
        ans.append(
            [(a[0] + a[1]) / 2] + [j for j in i if j not in [a[0], a[1]]])

    return ans


def judge(v):
    for i in v:
        if len(i) != 1:
            return False

    return True


def main():
    n = int(input())
    v = list()

    for i in map(int, input().split()):
        v.append(i)

    v = [v]

    while True:
        for i in v:
            if len(i) != 1:
                v.remove(i)
                new = func(i)
                # 新たにできた具材のセットを足す
                v += new

        if judge(v):
            break

    print(max(v)[0])


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline


def main():
    n = int(input())
    v = list()

    for i in map(int, input().split()):
        v.append(i)

    v.sort()

    ans = v[0]
    for i in range(1, n):
        ans = (ans + v[i]) / 2

    print(ans)


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

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

MOD = 10**9 + 7

from functools import reduce
from fractions import gcd
def lcm(x,y):return x*y//gcd(x,y)
def lcmm(l):return reduce(lcm,l)

x = lcmm(A)

ans = 0
for a in A:
    ans += x//a
    ans %= MOD

print(ans)


### FIXED CODE ###

from functools import reduce
from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
 
MOD = 10 ** 9 + 7
 
lcm = reduce(lambda x,y: x*(y//gcd(x,y)), A)
lcm %= MOD

coef = sum(pow(a, MOD-2, MOD) for a in A)
ans = lcm * coef % MOD

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

N, M, K = map(int, input().split())
MOD = 10 ** 9 + 7

def comb(n, k):
    ret = 1
    for i in range(1, k + 1):
        ret = ret * (n - i + 1) % MOD        
        ret = ret * pow(i, MOD - 2, MOD) % MOD
        
    return ret

ans = 0
for d in range(N):
    ans += d * comb(N * M - 2, K - 2) * (N - d) * M ** 2
    ans %= MOD
    
for d in range(M):
    ans += d * comb(N * M - 2, K - 2) * (M - d) * N ** 2
    ans %= MOD
    
print(ans)



### FIXED CODE ###

N, M, K = map(int, input().split())
MOD = 10 ** 9 + 7

def comb(n, k):
    ret = 1
    for i in range(1, k + 1):
        ret = ret * (n - i + 1) % MOD        
        ret = ret * pow(i, MOD - 2, MOD) % MOD
        
    return ret

ans = 0
for d in range(N):
    ans += d * (N - d) * M ** 2
    ans %= MOD
    
for d in range(M):
    ans += d * (M - d) * N ** 2
    ans %= MOD
    
print(ans * comb(N * M - 2, K - 2) % MOD)
### BUGGY CODE ###

import copy
S = input()

def bit_cal(max_num,cal_list=[],current_cnt=0):
    new_list = []
    if len(cal_list) == 0:
        for i in range(2):
            new_list.append([i])
    else:
        for cal_val in cal_list:
            for i in range(2):
                tmp = copy.deepcopy(cal_val)
                tmp.append(i)
                new_list.append(tmp)
    current_cnt += 1
    if max_num == current_cnt:
        return new_list
    return bit_cal(max_num,new_list,current_cnt)

all_plus_combination = bit_cal(len(S)-1)


ans = 0
for plus_combination in all_plus_combination:
    start_idx = 0
    for i in range(len(S)-1):
        if plus_combination[i] == 1:
            ans += int(S[start_idx:i+1])
            start_idx = i+1
    ans +=int(S[start_idx:100])
print(ans)


### FIXED CODE ###

import copy
S = input()

'''
bit探索
2 進数表記した場合の下から数えて n 桁目（一番下の桁を 0 とします）が 1 であるかどうかをチェックするためのコードは、(i >> n) & 1 
'''
def bit_cal2(n):
    return_list = ['']* (2 ** n)
    for i in range(2 ** n):
        for j in range(n):
            if ((i >> j) & 1):
                return_list[i] = return_list[i] + '1'
            else:
                return_list[i] = return_list[i] + '0'
    return return_list

#自作のは遅かった
'''
def bit_cal(max_num,cal_list=[],current_cnt=0):
    new_list = []
    if len(cal_list) == 0:
        for i in range(2):
            new_list.append([i])
    else:
        for cal_val in cal_list:
            for i in range(2):
                tmp = copy.deepcopy(cal_val)
                tmp.append(i)
                new_list.append(tmp)
    current_cnt += 1
    if max_num == current_cnt:
        return new_list
    return bit_cal(max_num,new_list,current_cnt)

'''
all_plus_combination = bit_cal2(len(S)-1)
ans = 0
for plus_combination in all_plus_combination:
    start_idx = 0
    for i in range(len(S)-1):
        if plus_combination[i] == '1':
            ans += int(S[start_idx:i+1])
            start_idx = i+1
    ans +=int(S[start_idx:100])
print(ans)
### BUGGY CODE ###

N = int(input())
a = {}
for i in range(N):
    a[i + 1] = int(input())

i = 1
before_i = None
cnt = 0
while True:
    next_i = a[i]
    cnt += 1
    if next_i in [1, i, before_i]:
        print(-1)
        break
    elif next_i == 2:
        print(cnt)
        break

    i = next_i

### FIXED CODE ###

N = int(input())
a = {}
for i in range(N):
    a[i + 1] = int(input())

i = 1
cnt = 0
while True:
    next_i = a[i]
    cnt += 1
    if next_i < 1:
        print(-1)
        break
    elif next_i == 2:
        print(cnt)
        break

    a[i] = 0
    i = next_i
### BUGGY CODE ###

N = int(input())
S = input()

r = S.count('R')
g = S.count('G')
b = S.count('B')
ans = r*g*b

for i in range(N):
  for j in range(i+1,N):
    for k in range(j+1,N):
      if k>2*j-i:
        break
      if S[i]!=S[j]!=S[k]!=S[i]:
        if j-i==k-j:
          ans -= 1

print(ans)

### FIXED CODE ###

N = int(input())
S = input()

r = S.count('R')
g = S.count('G')
b = S.count('B')
ans = r*g*b

for i in range(N):
  for j in range(i+1,N):
    k=2*j-i
    if k<N and S[i]!=S[j]!=S[k]!=S[i]:
      ans -= 1

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

N = int(input())
S_list = []
str_cnt = 0
for n in range(N):
    tmp = input()
    if((tmp in S_list) == False):
        str_cnt += 1
        S_list.append(tmp)

print(str_cnt)

### FIXED CODE ###

N = int(input())
S_list = []
for n in range(N):
    S_list.append(input())

print(len(set(S_list)))
### BUGGY CODE ###

import sys

n,m=map(int,input().split())
a=[]
b=[]
for i in range(m):
	numa,numb=map(int,input().split())
	a.append(numa)
	b.append(numb)
bb=[]
for j in range(len(a)):
    if 1==a[j]:
        bb.append(b[j])
if len(bb)==0:
	print("IMPOSSIBLE")
	sys.exit()
for k in range(len(bb)):
	for l in range(len(a)):
		if bb[k]==a[l] and b[l]==n :
			print("POSSIBLE")
			sys.exit()
print("IMPOSSIBLE")



### FIXED CODE ###

import sys

n,m=map(int,input().split())
a=[]
b=[]
for i in range(m):
	numa,numb=map(int,input().split())
	a.append(numa)
	b.append(numb)
bb=[]
aa=[]
if not 1 in a or not n in b:
	print("IMPOSSIBLE")
	sys.exit()
for j in range(len(a)):
    if 1==a[j]:
        bb.append(b[j])
for k in range(len(b)):
    if n==b[k]:
        aa.append(a[k])
list=set(aa) & set(bb)
print("IMPOSSIBLE" if len(list)==0 else "POSSIBLE")
### BUGGY CODE ###

# A
n,m = map(int, input().split())
s = str(input())
t = str(input())

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
def lcm(a,b):
    return a*b/gcd(a,b)
l=int(lcm(n,m))
si = ti= 0
ss = tt = 1
for i in range(l):
    if ss<i:
        ss=int(ss+l/n)
        si+=1
    if tt<i:
        tt=int(tt+l/m)
        ti+=1
    if ss<=l and tt<=l and i<=ss and i<=tt and ss==tt:
        if s[si]!=t[ti]:
            print('-1')
            break
else:
    print(l)

### FIXED CODE ###

from fractions import gcd
n,m = map(int, input().split())
s = input()
t = input()

u = gcd(n,m)
l = n*m//u
x = n//u
y = m//u
for i in range(u):
    # print(n, m, u, l, i, i*x, s[i*x], i*y, t[i*y])
    if s[i * x] != t[i * y]:
        print(-1)
        break
else:
    print(l)
### BUGGY CODE ###

n,k = map(int, input().split())
dp = [float("inf")] * 100000
h = list(map(int, input().split()))
dp[0] = 0
for i in range(n):
    for j in range(1,k+1):
        if i+j < n:
            dp[i+j] = min(dp[i+j], dp[i] + abs(h[i]-h[i+j]))
print(dp[n-1])


### FIXED CODE ###

n,k = map(int, input().split())
dp = [float("inf")] * 100000
h = list(map(int, input().split()))
dp[0] = 0
for i in range(n):
    for j in range(1,k+1):
        if i+j < n:
            dp[i+j] = min(dp[i+j], dp[i] + abs(h[i]-h[i+j]))
print(dp[n-1])
### BUGGY CODE ###

N, M = map(int, input().split())
H = list(map(int, input().split()))
AB = [[] for i in range(M)]
for i in range(M):
    AB[i] = list(map(int, input().split()))

cnt = 0
for i in range(N):
    for j in AB:
        if i + 1 in j:
            for k in j:
                if i + 1 == k:
                    continue
                if H[k-1] >= H[i]:
                    break
            else:
                continue
            break
    else:
        cnt += 1

print(cnt)



### FIXED CODE ###

N, M = map(int, input().split())
H = list(map(int, input().split()))
AB = [[] for i in range(M)]
for i in range(M):
    AB[i] = list(map(int, input().split()))

cnt = 0
memo_loser = []
for bridge in AB:
    

    value = min(H[bridge[0]-1], H[bridge[1]-1])
    if value == H[bridge[0]-1] and not bridge[0] in memo_loser:
        memo_loser.append(bridge[0])
    if value == H[bridge[1] - 1] and not bridge[1] in memo_loser:
        memo_loser.append(bridge[1])
print(N - len(memo_loser))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n=int(input())
ss=input()
s=[]
for i in ss:
  s.append(ord(i)-ord('a'))
q=int(input())
bit=[[0]*(n+1) for _ in range(26)]
#print(bit)
def upd(at,by,char):
  while at<=n:
    bit[char][at]+=by
    at+=at&-at
def qry(at,char):
  ret=0
  while at>0:
    #print(at,char,end=" inside \n")
    ret+=bit[char][at]
    at-=at&-at
  return ret
for i in range(n):
  upd(i+1,1,s[i])
for _ in range(q):
  t,l,r=input().split()
  t=int(t)
  if t==1:
    # print(t,l,r,end=" inside if")
    i=int(l)
    cq=ord(r)-ord('a')
    prev=s[i-1]
    upd(i,-1,prev)
    curr=cq
    upd(i,1,curr)
    s[i-1]=cq
    #change ith character to cq  
  else:
    #    print(t,l,r,end=" inside else")
    l=int(l)
    r=int(r)
    ans=0
    for i in range(26):
      if qry(r,i)-qry(l-1,i)>0:
        ans+=1
    print(ans)


### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
#print(n,end=' n')
data=[0]*(2*n)
def upd(i,x):
  i+=n
  data[i]=x
  while i>1:
    data[i>>1]=data[i]|data[i^1]
    i>>=1
def qry(l,r):
  l+=n
  r+=n
  res=0
  while l<r:
    if l&1:
      res|=data[l]
      l+=1
    if r&1:
      r-=1
      res|=data[r]
    l>>=1
    r>>=1
  return bin(res).count('1')

for i,c in enumerate(input()[:-1],n):
  data[i]=1<<(ord(c)-ord('a'))
for i in range(n-1,0,-1):
  data[i]=data[i<<1]|data[i<<1|1]
ans=[]
for _ in range(int(input())):
  q,a,b=input().split()
  if int(q)==1:
    upd(int(a)-1,1<<(ord(b)-ord('a')))
  else:
    ans.append(qry(int(a)-1,int(b)))
print('\n'.join(map(str,ans)))
### BUGGY CODE ###

import itertools


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

MOD = 1000000007

l = []
for i in range(N):
    l.append(i)

C = itertools.combinations(l, 2)

a = 0
for c in C:
    a += (A[c[0]] * A[c[1]]) % MOD
a %= MOD
print(a)

### FIXED CODE ###

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

MOD = 1000000007

a = 0
b = 0
for i in range(N):
    a += A[i] % MOD
    b += (A[i] ** 2) % MOD
a = a ** 2
ans = (a - b) * pow(2, MOD - 2, MOD) % MOD
print(ans)
### BUGGY CODE ###

input()
l=list(map(int,input().split()))
ret=1
for i in l:
  ret*=i
print(ret if ret <= 10**18 else -1)

### FIXED CODE ###

input()
l=list(map(int,input().split()))
if 0 in l:
  ret = 0
else:
  ret = 1
  for i in l:
    ret *= i
    if ret > 10**18:
      ret = -1
      break
print(ret)
### BUGGY CODE ###

import math
mat =[]
a, b, n = map(int, input().split())
for x in range(n+1):
    ans = math.floor(a*x/b) - a * math.floor(x/b)
    mat.append(ans)
    if mat[x] < mat[x-1]:
        break
print(max(mat))

### FIXED CODE ###

a, b, n = map(int, input().split())
x = min(b-1, n)
s = (a*x) // b - a * (x // b)
print(s)
### BUGGY CODE ###

# xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


# xとyの属する集合の併合
def unite(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        # sizeの大きいほうがx
        if par[x] > par[y]:
            x, y = y, x
        par[x] += par[y]
        par[y] = x
        return True


# xとyが同じ集合に属するかの判定
def same(x, y):
    return find(x) == find(y)


# xが属する集合の個数
def size(x):
    return -par[find(x)]


n, m, k = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
cd = [list(map(int, input().split())) for i in range(k)]

# 初期化
# 根なら-size,子なら親の頂点
par = [-1] * n

friend = [[0] * n for i in range(n)]
block = [[0] * n for i in range(n)]

for a, b in ab:
    a -= 1
    b -= 1
    unite(a, b)
    friend[a][b] = 1
    friend[b][a] = 1

for c, d in cd:
    c -= 1
    d -= 1
    block[c][d] = 1
    block[d][c] = 1

for i in range(n):
    ans = 0
    for j in range(n):
        if i == j:
            continue
        if same(i, j):
            if not friend[i][j]:
                if not block[i][j]:
                    ans += 1
    print(ans)

### FIXED CODE ###

from collections import defaultdict


# xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


# xとyの属する集合の併合
def unite(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        # sizeの大きいほうがx
        if par[x] > par[y]:
            x, y = y, x
        par[x] += par[y]
        par[y] = x
        return True


# xとyが同じ集合に属するかの判定
def same(x, y):
    return find(x) == find(y)


# xが属する集合の個数
def size(x):
    return -par[find(x)]


n, m, k = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
cd = [list(map(int, input().split())) for i in range(k)]

# 初期化
# 根なら-size,子なら親の頂点
par = [-1] * n

not_see = defaultdict(set)

for a, b in ab:
    a -= 1
    b -= 1
    unite(a, b)
    if same(a, b):
        not_see[a].add(b)
        not_see[b].add(a)

for c, d in cd:
    c -= 1
    d -= 1
    if same(c, d):
        not_see[c].add(d)
        not_see[d].add(c)

for i in range(n):
    print(size(i) - len(not_see[i]) - 1)
### BUGGY CODE ###

while 1:
    n = int(input())
    if n == 0:break
    l = sum(map(int, input().split()))
    j = sorted(map(int, input().split()), reverse = True)
    print(max([((l + sum(j[:i])) * (n - i)) for i in range(n)]))


### FIXED CODE ###

while 1:
    n = int(input())
    if n == 0:break
    l = sum(map(int, input().split()))
    j = sorted(map(int, input().split()), reverse = True)
    d = [0] * n
    for i in range(n):
        d[i] = (l + sum(j[:i])) * (n - i)
        if d[i] < d[i - 1]:
            print(d[i - 1])
            break
    else:print(d[-1])
### BUGGY CODE ###

n,y=map(int,input().split())

a=0

for s in range(y//10000+1)[::-1]:
    for t in range(y//5000+1)[::-1]:
        for u in range(y//1000+1)[::-1]:
            if 10000*s+5000*t+1000*u==y and s+t+u==n:
                print(s,t,u)
                a=1
                break
                
            else:
                continue
            break
            
        else:
            continue
        break
        
    else:
        continue
    break
    
if a==0:
    print(-1,-1,-1)


### FIXED CODE ###

n,y=map(int,input().split())

ans=0

for i in range(y//10000,-1,-1):

    nokori=(y-i*10000)

    for j in range(min(n-i,nokori//5000),-1,-1):
 
        nokori2=nokori-j*5000
    
        if 10000*i+5000*j+1000*(n-i-j)==y:
            print(i,j,n-i-j)
            ans=1
            break
            
    else:
        continue
    break
    
          
if ans==0:
    print(-1,-1,-1)
### BUGGY CODE ###

a, b, c, d = list(map(int, input().split()))
def divNumCount(start, end, div):
    count = 0
    num = 0
    i = start
    while i <= end:
        if i % div == 0:
            i += div - 1
            count += 1
        i += 1
    return count
def euqlid(a,b):
    if a < b:
        temp = a
        a = b
        b = temp
    while(a % b != 0):
        temp = a % b
        a = b
        b = temp
    return b

C = 0
D = 0
CandD = 0
C = divNumCount(a, b, c)
D = divNumCount(a, b, d)
CandD = divNumCount(a, b, c * d / euqlid(c,d))
print(b - a + 1 - (C + D - CandD))

### FIXED CODE ###

a, b, c, d = list(map(int, input().split()))
def euqlid(x,y):
    if x < y :
        temp = x
        x = y
        y = temp
    while x % y != 0:
        temp = x
        x = y
        y = temp % y
    return y
def searchCount(p,q,k):
    min = 0
    max = 0
    if p % k == 0:
        min = p // k
    else:
        min = p//k + 1
    max = q//k
    return max - min + 1
lcm = euqlid(c,d)
gcd = int((c * d) / lcm)
print((b - a + 1) - searchCount(a,b,c) - searchCount(a,b,d) + searchCount(a,b,gcd))
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
imos=[0 for i in range(N+1)]

for t in range(K):
  for i in range(N):
    l=max(0,i-A[i])
    r=min(N,i+A[i]+1)
    imos[l]+=1
    imos[r]-=1
  for i in range(0,N):
    imos[i+1]+=imos[i]
    A[i]=imos[i]
  imos=[0 for i in range(N+1)]
  if len(set(A))==1 and (N in set(A)):
    break
for i in range(N):
  A[i]=str(A[i])
ans=" ".join(A)
print(ans)  

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
imos=[0 for i in range(N+1)]
ANS=[str(N)]*N
if K>=50:
  ans=" ".join(ANS)
  print(ans)
else:
  for t in range(K):
    for i in range(N):
      l=max(0,i-A[i])
      r=min(N,i+A[i]+1)
      imos[l]+=1
      imos[r]-=1
    for i in range(0,N):
      imos[i+1]+=imos[i]
      A[i]=imos[i]
    imos=[0 for i in range(N+1)]
  for i in range(N):
    A[i]=str(A[i])
  ans=" ".join(A)
  print(ans)
### BUGGY CODE ###

n=int(input())
S=0
while(n>0):
  S+=n%10
  S//=10
if n&S==0:
  print('Yes')
else:
  print('No')
  
  

### FIXED CODE ###

n=int(input())
k=n
S=0
while(n>0):
  S+=n%10
  n//=10
  #print(S,k)
if k%S==0:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

import sys

S=input()
if len(S)<2: print(0),sys.exit()
elif len(S)==3:
    print(1 if S=="ABC" else 0)
    sys.exit()

s=[]
a=[]
x=ord("A")
for i in range(len(S)):
    s.append(ord(S[i])-x)
    if S[i]=="A": a.append(i)
a=[a[i] for i in range(len(a)-1,-1,-1)]


tmp=0
abc,bca=[0,1,2],[1,2,0]
ans=0
while True:
    if a==[] or a[-1]>=len(s)-2: break
    tmp=a[-1]
    if s[tmp:tmp+3]==abc:
        s[tmp:tmp+3]=bca
        a.append(tmp+2)
        if tmp>0: a.append(tmp-1)
        ans+=1
    else: a.pop(-1)

print(ans)

### FIXED CODE ###

import sys

S=input()
if len(S)<2: print(0),sys.exit()
elif len(S)==3:
    print(1 if S=="ABC" else 0)
    sys.exit()



s=[S[i] for i in range(len(S))]
tmp=0
abc,bca=["A","B","C"],["B","C","A"]
ans=0
a,bc=0,0
i=0
while i<len(s)-1:
    if s[i]=="A": a+=1
    elif s[i]=="B" and s[i+1]=="C":
        bc+=1
        i+=1
        ans+=a
    
    else:
        a,bc=0,0
    i+=1
print(ans)
### BUGGY CODE ###

from sys import exit

R, G, B, N = map(int, input().split())

count = 0

for r in range(N // R + 1):
	for g in range(N // G + 1):
		if (N - r * R - g * G) % B == 0 and N - r * R - g * G >= 0:
			count += 1

print(count)


### FIXED CODE ###

from sys import exit

R, G, B, N = map(int, input().split())

count = 0

for r in range(N // R + 1):
	for g in range((N - r * R) // G + 1):
		if (N - r * R - g * G) % B == 0:
			count += 1

print(count)
### BUGGY CODE ###

a = input()
q = input()
q = int(q)
for i in range(q):
    que = input().split(" ")
    if que[0] == "1":
        a = a[::-1]
    else:
        if que[1] == "1":
            a = que[2]+a
        else:
            a += que[2]

print(a)

### FIXED CODE ###

S = input()
N = input()
N = int(N)
re = False
foward = ""
back = ""

for i in range(N):
    que = input().split(" ")
    if que[0] == "1":
        if re:
            re = False
        else:
            re = True
    else:
        if re:
            if que[1] == "1":
                back += que[2]
            else:
                foward += que[2]
        else:
            if que[1] == "1":
                foward += que[2]
            else:
                back += que[2]
S = foward[::-1]+S+back
if re:
    print(S[::-1])
else:
    print(S)
### BUGGY CODE ###

N=int(input())
X=list(map(int,input().split()))
for i in range(N):
    idx=i+1
    X_list=X[:idx-1]+X[idx:]
    X_list.sort()
    print(X_list[int(N/2-1)])

### FIXED CODE ###

N=int(input())
X=list(map(int,input().split()))
Y=X.copy()
Y.sort()
for i in range(N):
    if X[i]<Y[int(N/2)]:
        print(Y[int(N/2)])
    else:
        print(Y[int(N/2)-1])
### BUGGY CODE ###

def main():
    from collections import Counter
    import sys

    sys.setrecursionlimit(10 ** 7)
    input = sys.stdin.readline

    def f(c1, c2, c3):
        if dp[c1][c2][c3] != -1.0:
            return dp[c1][c2][c3]

        res = (n \
               + (f(c1 - 1, c2, c3) * c1 if c1 else 0) \
               + (f(c1 + 1, c2 - 1, c3) * c2 if c2 else 0) \
               + (f(c1, c2 + 1, c3 - 1) * c3 if c3 else 0)) \
              / (c1 + c2 + c3)

        dp[c1][c2][c3] = res
        return res

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

    c = Counter(a)
    c1 = c[1]
    c2 = c[2]
    c3 = c[3]

    dp = tuple(
        tuple(
            [-1.0] * (c3 + 1) for _ in range(c2 + c3 + 1)
        ) for _ in range(c1 + c2 + c3 + 1))
    dp[0][0][0] = 0.0
    # dp[x][y][z]:=1,2,3個の皿がx,y,z残っているときの期待値

    print(f(c1, c2, c3))


if __name__ == '__main__':
    main()

# dp[now] =
# 1
# + dp[1個の皿を食べた] * p
# + dp[2個の皿を食べた] * p
# + dp[3個の皿を食べた] * p
# + dp[0個の皿を食べた==now] * p

# if mainの追加
# 初期値None->-1.0にした
# checked配列を辞めた
# チェック済みかどうかの判定を-1.0と一致するかの比較にした


### FIXED CODE ###

def main():
    from collections import Counter

    n = int(input())
    a = tuple(int(x) for x in input().split())

    c = Counter(a)
    c1 = c[1]
    c2 = c[2]
    c3 = c[3]

    x1 = 310 ** 2
    x2 = 310

    dp = [0.0] * (310 ** 3)
    dp[0] = 0.0
    # dp[x * x1 + y * x2 + z]:=1,2,3個の皿がx,y,z残っているときの期待値

    for r3 in range(c3 + 1):
        d3 = c3 - r3
        for r2 in range(c2 + d3 + 1):
            for r1 in range(c1 + d3 + c2 - r2 + 1):
                ind = r1 * x1 + r2 * x2 + r3
                if ind != 0:
                    dp[ind] = (n \
                               + (dp[ind - x1] * r1 if r1 > 0 else 0) \
                               + (dp[ind + x1 - x2] * r2 if r2 > 0 else 0) \
                               + (dp[ind + x2 - 1] * r3 if r3 > 0 else 0)) \
                              / (r1 + r2 + r3)

    print(dp[c1 * x1 + c2 * x2 + c3])


if __name__ == '__main__':
    main()

# dp[now] =
# 1
# + dp[1個の皿を食べた] * p
# + dp[2個の皿を食べた] * p
# + dp[3個の皿を食べた] * p
# + dp[0個の皿を食べた==now] * p

# if mainの追加
# 初期値None->-1.0にした
# checked配列を辞めた
# チェック済みかどうかの判定を-1.0と一致するかの比較にした

# カウントはCounterを使う方が速い
# 1次元にした
# resの加算を複数回に分けると
# 三項演算子より遅くなる
# 再帰関数を辞めた