Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from numba import njit


def comb(n, r, p):
    r = min(r, n - r)
    ret = fac[n]
    ret = ret * facinv[r] % p
    return ret * facinv[n - r] % p


@njit
def comb_init(N_UNTIL, p):
    N_UNTIL += 1
    inv = np.empty(N_UNTIL, np.int64)
    fac = np.empty(N_UNTIL, np.int64)
    facinv = np.empty(N_UNTIL, np.int64)
    inv[0] = 0
    inv[1] = 1
    fac[0] = 1
    facinv[0] = 1
    for i in range(2, N_UNTIL):
        inv[i] = -inv[p % i] * (p // i) % p
    for i in range(1, N_UNTIL):
        fac[i] = fac[i - 1] * i % p
    for i in range(1, N_UNTIL):
        facinv[i] = facinv[i - 1] * inv[i] % p
    return inv, fac, facinv


K = int(input())
S = input()
N = len(S)
MOD = 1_000_000_007
inv, fac, facinv = comb_init(N + K - 1, MOD)
ans = 0
for i in range(K + 1):
    tmp = pow(25, K - i, MOD)
    tmp *= comb(N + K - i - 1, K - i, MOD)
    tmp %= MOD
    tmp *= pow(26, i, MOD)
    tmp %= MOD
    ans += tmp
    ans %= MOD
print(ans)


Fixed submission:
def comb(n, r, p):
    return fac[n] * facinv[r] * facinv[n - r] % p


def comb_pre(N_UNTIL, p):
    for i in range(2, N_UNTIL + 1):
        fac.append(fac[i - 1] * i % p)
        inv.append(-inv[p % i] * (p // i) % p)
        facinv.append(facinv[-1] * inv[-1] % p)


fac = [1, 1]
facinv = [1, 1]
inv = [0, 1]

K = int(input())
S = input()
N = len(S)
MOD = 1_000_000_007
comb_pre(N + K - 1, MOD)
ans = 0
for i in range(K + 1):
    tmp = pow(25, K - i, MOD)
    tmp *= comb(N + K - i - 1, K - i, MOD)
    tmp %= MOD
    tmp *= pow(26, i, MOD)
    tmp %= MOD
    ans += tmp
    ans %= MOD
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
def comb(n, r, p):
    return fac[n] * facinv[r] * facinv[n - r] % p


def comb_pre(N_UNTIL, p):
    for i in range(2, N_UNTIL + 1):
        fac.append(fac[i - 1] * i % p)
        inv.append(-inv[p % i] * (p // i) % p)
        facinv.append(facinv[-1] * inv[-1] % p)


fac = [1, 1]
facinv = [1, 1]
inv = [0, 1]

K = int(input())
S = input()
N = len(S)
MOD = 1_000_000_007
comb_pre(N + K - 1, MOD)
ans = 0
for i in range(K + 1):
    tmp = pow(25, K - i, MOD)
    tmp *= comb(N + K - i - 1, K - i, MOD)
    tmp %= MOD
    tmp *= pow(26, i, MOD)
    tmp %= MOD
    ans += tmp
    ans %= MOD
print(ans)


Fixed submission:
def comb(n, r, p):
    return fac[n] * facinv[r] * facinv[n - r] % p


def comb_pre(N_UNTIL, p):
    for i in range(2, N_UNTIL + 1):
        fac.append(fac[i - 1] * i % p)
        inv.append(-inv[p % i] * (p // i) % p)
        facinv.append(facinv[-1] * inv[-1] % p)


fac = [1, 1]
facinv = [1, 1]
inv = [0, 1]

K = int(input())
S = input()
N = len(S)
MOD = 1_000_000_007
comb_pre(N + K - 1, MOD)
ans = 0
for i in range(K + 1):
    tmp = pow(25, K - i, MOD)
    tmp *= comb(N + K - i - 1, K - i, MOD)
    tmp %= MOD
    tmp *= pow(26, i, MOD)
    tmp %= MOD
    ans += tmp
    ans %= MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter


def enum_divs(n):
    res = []
    for i in range(1, int(n ** .5) + 1):
        if n % i == 0:
            res.append(i)
            if i != n // i:
                res.append(n // i)
    return res


N = int(input())
A = list(map(int, input().split()))
uq_A = [k for k, v in Counter(A).items() if v == 1]
set_A = set(A)
ans = 0
for uq_a in uq_A:
    if any(d in set_A - {uq_a} for d in enum_divs(uq_a)):
        continue
    ans += 1
print(ans)



Fixed submission:
from collections import Counter


LEN = 10 ** 6
is_avl = [0] * (LEN + 1)
N = int(input())
A = Counter(map(int, input().split()))
for a in A:
    is_avl[a] = 1
for a in A:
    for i in range(2 * a, LEN + 1, a):
        is_avl[i] = 0
ans = 0
for a in A:
    if is_avl[a] == 1 and A[a] == 1:
        ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
N, A = map(int, open(0).read().split())
if 0 in A:
    print(0)
    exit()
ans = 1
for a in A:
    ans *= a
    if ans > 10 ** 18:
        print(-1)
        break
else:
    print(ans)


Fixed submission:
N = input()
A = list(map(int, input().split()))
if 0 in A:
    print(0)
    exit()
ans = 1
for a in A:
    ans *= a
    if ans > 10 ** 18:
        print(-1)
        break
else:
    print(ans)
Buggy python submission (verdict: Runtime Error):
from math import gcd
from collections import defaultdict


def cmb(n, r):
    return (fac[n] * pow(fac[r], p - 2, p) * pow(fac[n - r], p - 2, p)) % p


p = 1000000007
fac = [1] * (2 * 10 ** 6 + 1)
for i in range(1, 2 * 10 ** 6 + 1):
    fac[i] = (fac[i - 1] * i) % p


N = int(input())

AB = defaultdict(int)
for i in range(N):
    a, b = map(int, input().split())
    g = gcd(a, b)
    AB[(a // g, b // g)] += 1

bad_pairs_cnt = 0
for a, b in AB:
    bad_pairs_cnt += AB[(a, b)] * (AB.get((-b, a), 0) + AB.get((b, -a), 0))

ans = N
for i in range(2, N + 1):
    b = cmb(N, 2) - bad_pairs_cnt * (N ** (i - 1))
    if b <= 0:
        break
    ans += b
    ans %= p
print(ans)


Fixed submission:
from collections import defaultdict
from math import gcd


MOD = 1000000007
N = int(input())
both_zeros_cnt = 0
bads = defaultdict(lambda: [0, 0])
for _ in range(N):
    A, B = map(int, input().split())
    if A == 0 and B == 0:
        both_zeros_cnt += 1
        continue
    if B < 0 or (B == 0 and A < 0):
        A, B = -A, -B
    g = gcd(A, B)
    A, B = A // g, B // g
    if A > 0:
        bads[(A, B)][0] += 1
    else:
        bads[(B, -A)][1] += 1

ans = 1
for k, l in bads.values():
    ans *= (pow(2, k, MOD) - 1) + (pow(2, l, MOD) - 1) + 1
    ans %= MOD
print((ans + both_zeros_cnt - 1) % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
def cmb(n, r, p):
    return (fac[n] * pow(fac[r], p - 2, p) * pow(fac[n - r], p - 2, p)) % p


p = 998244353
N, M, K = map(int, input().split())
fac = [1] * (N + 1)
for i in range(1, N + 1):
    fac[i] = (fac[i - 1] * i) % p

ans = 0
for k in range(K + 1):
    ans += M * pow(M - 1, N - k - 1, p) * cmb(N - 1, k, p)
    ans %= p
print(ans)


Fixed submission:
def cmb(n, r, p):
    return (fac[n] * pow(fac[r], p - 2, p) * pow(fac[n - r], p - 2, p)) % p


p = 998244353
N, M, K = map(int, input().split())
fac = [1] * (max(N, M) + 1)
for i in range(1, max(N, M) + 1):
    fac[i] = (fac[i - 1] * i) % p

ans = 0
for k in range(K + 1):
    ans += M * pow(M - 1, N - k - 1, p) * cmb(N - 1, k, p)
    ans %= p
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
def cmb(n, r, p):
    return (fac[n] * pow(fac[r], p - 2, p) * pow(fac[n - r], p - 2, p)) % p


p = 998244353
N, M, K = map(int, input().split())
fac = [1] * (max(N, M) + 1)
for i in range(1, max(N, M) + 1):
    fac[i] = (fac[i - 1] * i) % p

ans = 0
for k in range(K + 1):
    ans += M * pow(M - 1, N - k - 1, p) * cmb(N - 1, k, p)
    ans %= p
print(ans)


Fixed submission:
def cmb(n, r, p):
    return (fac[n] * pow(fac[r], p - 2, p) * pow(fac[n - r], p - 2, p)) % p


p = 998244353
N, M, K = map(int, input().split())
fac = [1] * (max(N, M) + 1)
for i in range(1, max(N, M) + 1):
    fac[i] = (fac[i - 1] * i) % p

ans = 0
for k in range(K + 1):
    ans += M * pow(M - 1, N - k - 1, p) * cmb(N - 1, k, p)
    ans %= p
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = sorted(((v, i) for i, v in enumerate(map(int, input().split()))))

ans = 0
for i in range(n):
    for j in range(i, n):
        hi, ki = A[i]
        hj, kj = A[j]
        if abs(kj - ki) == hi + hj:
            ans += 1
        if hi >= n:
            break
print(ans)

Fixed submission:
from collections import defaultdict


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

L = defaultdict(int)
R = defaultdict(int)
for i, v in enumerate(A):
    L[i + v] += 1
    R[i - v] += 1
print(sum(L.get(i, 0) * R.get(i, 0) for i in range(n)))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = sorted(((v, i) for i, v in enumerate(map(int, input().split()))))

ans = 0
for i in range(n):
    for j in range(i, n):
        hi, ki = A[i]
        hj, kj = A[j]
        if abs(kj - ki) == hi + hj:
            ans += 1
        if hi >= n:
            break
print(ans)


Fixed submission:
from collections import defaultdict


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

L = defaultdict(int)
R = defaultdict(int)
for i, v in enumerate(A):
    L[i + v] += 1
    R[i - v] += 1
print(sum(L.get(i, 0) * R.get(i, 0) for i in range(n)))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
from operator import mul
from functools import reduce


memo = {}


def cmb(n, r):
    if (n, r) in memo:
        return memo[(n, r)]
    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    memo[(n, r)] = over // under
    return over // under


s = input()[::-1]
acc = [int(s[0])]
cntr = defaultdict(int)
for i, c in enumerate(s[1:], 1):
    if c == '0':
        continue
    next_mod = (acc[-1] + 10 ** i * int(c)) % 2019
    cntr[next_mod] += 1
    acc.append(next_mod)

ans = 0
for k, v in cntr.items():
    if k == 0:
        ans += v
    if v > 1:
        ans += cmb(v, 2)
print(ans)


Fixed submission:
from collections import defaultdict


s = input()[::-1]
cntr = defaultdict(int)
cntr[0] += 1
tens = 1
n = 0
for c in s:
    n += tens * int(c) % 2019
    n %= 2019
    cntr[n] += 1
    tens = tens * 10 % 2019

ans = 0
for v in cntr.values():
    if v > 1:
        ans += v * (v - 1) // 2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict, deque, Counter


def bfs(start):
    queue = deque([start])
    dist = [-1] * n
    dist[start] = 0
    while queue:
        v = queue.popleft()
        for nv in graph[v]:
            if dist[nv] != -1:
                continue
            queue.append(nv)
            dist[nv] = dist[v] + 1
    return dist


n, x, y = map(int, input().split())
# 0-indexed nodes
x -= 1
y -= 1

graph = defaultdict(set)
for i in range(n - 1):
    graph[i].add(i + 1)
    graph[i + 1].add(i)
graph[x].add(y)
graph[y].add(x)

dic = defaultdict(int)
for i in range(n):
    for k, v in Counter(bfs(i)).items():
        dic[k] += v

[print(dic[i] // 2) for i in range(1, n)]


Fixed submission:
from collections import defaultdict

n, x, y = map(int, input().split())
x -= 1
y -= 1

circle = y - x + 1
a = [0 for _ in range(circle)]
for i in range(1, circle // 2 + 1):
    a[i] = i
    a[-i] = i

dists = defaultdict(int)
for i in range(n - 1):
    if i >= y:
        for j in range(i + 1, n):
            dists[j - i] += 1
    elif x < i < y:
        for j in a[1:y - i + 1]:
            dists[j] += 1
        for j in range(1, n - y):
            dists[a[y - i] + j] += 1
    else:
        # i <= x
        for j in range(i + 1, x):
            dists[j - i] += 1
        for j in a:
            dists[x - i + j] += 1
        for j in range(1, n - y):
            dists[x - i + a[-1] + j] += 1

for i in range(1, n):
    print(dists[i])
Buggy python submission (verdict: Time Limit Exceeded):
n, p = map(int, input().split())
s = input()

cnt = 0
for i in range(1, n + 1):
    for j in range(n - i + 1):
        number = int(s[j:j + i])
        if number % p == 0:
            cnt += 1

print(cnt)


Fixed submission:
n, p = map(int, input(). split())
s = list(map(int, input()[::-1]))

cnt = 0
if 10 % p == 0:
    for i, c in enumerate(s):
        if int(c) % p == 0:
            cnt += n - i
else:
    accmod = [0] * p
    accmod[0] = 1
    num = 0
    for i in range(n):
        num = (num + s[i] * pow(10, i, p)) % p
        accmod[num] += 1
    for v in accmod:
        if v > 1:
            cnt += v * (v - 1) // 2
print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
from string import ascii_lowercase
import sys


def input():
    return sys.stdin.readline().strip()


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
        self.k_init = 2 ** (self.n - 1).bit_length()

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            i += i & -i


n = int(input())
s = input()
q = int(input())

bits = {c: BIT(n) for c in ascii_lowercase}
[bits[c].add(i, 1) for i, c in enumerate(s, 1)]
queries = (input().split() for _ in range(q))

ans = []
for q_type, *q in queries:
    if q_type == '1':
        iq = int(q[0])
        cq = q[1]
        for c in ascii_lowercase:
            if bits[c].sum(iq) - bits[c].sum(iq - 1) == 1:
                bits[c].add(iq, -1)
                break
        bits[cq].add(iq, 1)
    else:
        l, r = map(int, q)
        cnt = 0
        for c in ascii_lowercase:
            if bits[c].sum(r) - bits[c].sum(l - 1) > 0:
                cnt += 1
        ans.append(cnt)
[print(i) for i in ans]

Fixed submission:
from string import ascii_lowercase
import sys


def input():
    return sys.stdin.readline().strip()


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
        self.k_init = 2 ** (self.n - 1).bit_length()

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            i += i & -i


n = int(input())
s = input()
q = int(input())

bits = {c: BIT(n) for c in ascii_lowercase}
[bits[c].add(i, 1) for i, c in enumerate(s, 1)]
queries = (input().split() for _ in range(q))

ans = []
for q_type, *q in queries:
    if q_type == '1':
        iq = int(q[0])
        cq = q[1]
        for c in ascii_lowercase:
            if bits[c].sum(iq) - bits[c].sum(iq - 1) == 1:
                bits[c].add(iq, -1)
                break
        bits[cq].add(iq, 1)
    else:
        l, r = map(int, q)
        cnt = 0
        for c in ascii_lowercase:
            if bits[c].sum(r) - bits[c].sum(l - 1) > 0:
                cnt += 1
        ans.append(cnt)
[print(i) for i in ans]
Buggy python submission (verdict: Runtime Error):
print(“x” * len(input()))

Fixed submission:
print("x" * len(input()))
Buggy python submission (verdict: Runtime Error):
H, A = map(isn’t, input().split())
print((H + A - 1) // A)

Fixed submission:
H, A = map(int, input().split())
print((H + A - 1) // A)
Buggy python submission (verdict: Time Limit Exceeded):
H, N, *AB = map(int, open(0).read().split())
magics = [(A, B) for A, B in zip(*[iter(AB)] * 2)]
dp = [float("inf")] * (H + 1)
dp[0] = 0
for i in range(N):
    A, B = magics[i]
    for h in range(H):
        dp[min(h + A, H)] = min(dp[min(h + A, H)], dp[h] + B)
print(dp[-1])


Fixed submission:
H, N, *AB = map(int, open(0).read().split())
A = []
B = []
for a, b in zip(*[iter(AB)] * 2):
    A.append(a)
    B.append(b)

dp = [float("inf")] * (H + 1)
dp[0] = 0

for i in range(N):
    for h in range(H):
        dec_health = min(h + A[i], H)
        dp[dec_health] = min(dp[dec_health], dp[h] + B[i])
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
H, N, *AB = map(int, open(0).read().split())
A = AB[::2]
B = AB[1::2]

dp = [float("inf")] * (H + 1)
dp[0] = 0

for i in range(N):
    for h in range(H):
        dec_health = min(h + A[i], H)
        dp[dec_health] = min(dp[dec_health], dp[h] + B[i])
print(dp[-1])


Fixed submission:
H, N, *AB = map(int, open(0).read().split())
A = []
B = []
for a, b in zip(*[iter(AB)] * 2):
    A.append(a)
    B.append(b)

dp = [float("inf")] * (H + 1)
dp[0] = 0

for i in range(N):
    for h in range(H):
        dec_health = min(h + A[i], H)
        dp[dec_health] = min(dp[dec_health], dp[h] + B[i])
print(dp[-1])

Buggy python submission (verdict: Runtime Error):
import numpy as np


H, N, *AB = map(int, open(0).read().split())
A = np.array(AB[::2])
B = np.array(AB[1::2])
max_A = A.max()

dp = np.zeros(H, dtype=np.int64)
for h in range(H):
    dp[h] = np.min(dp[h - A] + B)

print(dp[-1])


Fixed submission:
H, N, *AB = map(int, open(0).read().split())
A = []
B = []
for a, b in zip(*[iter(AB)] * 2):
    A.append(a)
    B.append(b)

dp = [float("inf")] * (H + 1)
dp[0] = 0

for i in range(N):
    for h in range(H):
        dec_health = min(h + A[i], H)
        dp[dec_health] = min(dp[dec_health], dp[h] + B[i])
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
H, N, *AB = map(int, open(0).read().split())
A = []
B = []
for a, b in zip(*[iter(AB)] * 2):
    A.append(a)
    B.append(b)

dp = [float("inf")] * (H + 1)
dp[0] = 0

for i in range(N):
    for h in range(H):
        dec_health = min(h + A[i], H)
        dp[dec_health] = min(dp[dec_health], dp[h] + B[i])
print(dp[-1])



Fixed submission:
H, N, *AB = map(int, open(0).read().split())
A = []
B = []
for a, b in zip(*[iter(AB)] * 2):
    A.append(a)
    B.append(b)

dp = [float("inf")] * (H + 1)
dp[0] = 0

for i in range(N):
    for h in range(H):
        dec_health = min(h + A[i], H)
        dp[dec_health] = min(dp[dec_health], dp[h] + B[i])
print(dp[-1])
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict

n, m = map(int, input().split())
ps = []
for _ in range(n):
  ps.append(map(int, input().split()))

sub_st = defaultdict(list)
for p, s in ps:
  sub_st[p].append(s)

solved = 0
error = 0
for k, v in sub_st.items():
  temp_error = 0
  for history in v:
    temp_error += 1
    if 'AC' in v:
      error += temp_error
      solved += 1
      break

priny(solved, error)
    

Fixed submission:
from collections import defaultdict

n, m = map(int, input().split())
ps = []
for _ in range(m):
    ps.append(input().split())

sub_st = defaultdict(list)
for p, s in ps:
    sub_st[p].append(s)

solved = 0
error = 0
for k, v in sub_st.items():
    temp_error = 0
    for history in v:
        if 'AC' in history:
            error += temp_error
            solved += 1
            break
        temp_error += 1

print(solved, error)
Buggy python submission (verdict: Runtime Error):
 k, x = map(int, input().split())
 if 500 * k >= x:
  print('Yes')
 else:
  print('No)

Fixed submission:
k, x = map(int, input().split())
if 500 * k >= x:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Time Limit Exceeded):
N, *A = map(int, open(0).read().split())
MOD = 1_000_000_007
ans = 0
for i in range(61):
    p, q, = 0, 0
    for a in A:
        if a >> i & 1:
            p += 1
        else:
            q += 1
    ans += pow(2, i, MOD) * p * q
    ans %= MOD
print(ans)

Fixed submission:
import numpy as np


def solve():
    ans = 0
    mask = 1
    for i in range(60):
        one_cnt = np.sum(A >> i & 1)
        tmp = one_cnt * (N - one_cnt)
        tmp %= MOD
        ans += tmp * mask
        ans %= MOD
        mask <<= 1
        mask %= MOD
    return ans


N, *A = map(int, open(0).read().split())
A = np.array(A, dtype=np.int64)
MOD = 1_000_000_007
print(solve())

Buggy python submission (verdict: Time Limit Exceeded):
N, *A = map(int, open(0).read().split())
MOD = 1_000_000_007
ans = 0
for i in range(64):
    p, q, = 0, 0
    for a in A:
        if a >> i & 1:
            p += 1
        else:
            q += 1
    ans += pow(2, i, MOD) * p * q
    ans %= MOD
print(ans)

Fixed submission:
import numpy as np


def solve():
    ans = 0
    mask = 1
    for i in range(60):
        one_cnt = np.sum(A >> i & 1)
        tmp = one_cnt * (N - one_cnt)
        tmp %= MOD
        ans += tmp * mask
        ans %= MOD
        mask <<= 1
        mask %= MOD
    return ans


N, *A = map(int, open(0).read().split())
A = np.array(A, dtype=np.int64)
MOD = 1_000_000_007
print(solve())

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
MOD = 1_000_000_007

ans = 0
two_exp = 1
for i in range(60):
    one_cnt = 0
    zero_cnt = 0
    for a in A:
        if a >> i & 1:
            one_cnt += 1
        else:
            zero_cnt += 1
    ans += one_cnt * zero_cnt * two_exp
    ans %= MOD
    two_exp <<= 1
    two_exp %= MOD
print(ans)


Fixed submission:
import numpy as np


def solve():
    ans = 0
    mask = 1
    for i in range(60):
        one_cnt = np.sum(A >> i & 1)
        tmp = one_cnt * (N - one_cnt)
        tmp %= MOD
        ans += tmp * mask
        ans %= MOD
        mask <<= 1
        mask %= MOD
    return ans


N, *A = map(int, open(0).read().split())
A = np.array(A, dtype=np.int64)
MOD = 1_000_000_007
print(solve())
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
ans = 0
for i in range(1000):
    T = str(i).zfill(3)
    j = 0
    for c in S:
        if c == T[j]:
            j += 1
            if j > 2:
                ans += 1
                break
print(ans)


Fixed submission:
N = int(input())
S = input()
ans = 0
d = [set() for _ in range(3)]
for i in range(N - 2):
    if S[i] in d[0]:
        continue
    d[0].add(S[i])
    for j in range(i + 1, N - 1):
        if S[i] + S[j] in d[1]:
            continue
        d[1].add(S[i] + S[j])
        for k in range(j + 1, N):
            if S[i] + S[j] + S[k] in d[2]:
                continue
            d[2].add(S[i] + S[j] + S[k])
            ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def is_good(mid, key):
    return sum(max(0, a - mid // f) for a, f in zip(A, F)) <= key


def binary_search(bad, good, key):
    while good - bad > 1:
        mid = (bad + good) // 2
        if is_good(mid, key):
            good = mid
        else:
            bad = mid
    return good


N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)
A_sum = sum(A)
ans = binary_search(-1, max(a * f for a, f in zip(A, F)), K)
print(ans)


Fixed submission:
def is_good(mid, key):
    ret = 0
    for i in range(N):
        ret += max(0, A[i] - mid // F[i])
    return ret <= key


def binary_search(key):
    bad, good = -1, 10 ** 18
    while good - bad > 1:
        mid = (bad + good) // 2
        if is_good(mid, key):
            good = mid
        else:
            bad = mid
    return good


N, K = map(int, input().split())
A = sorted(map(int, input().split()))
F = sorted(map(int, input().split()), reverse=True)
print(binary_search(K))

Buggy python submission (verdict: Time Limit Exceeded):
def is_good(mid, key):
    ret = 0
    for i in range(N):
        ret += max(0, A[i] - mid // F[i])
    return ret <= key


def binary_search(key):
    bad, good = -1, 10 ** 18
    while good - bad > 1:
        mid = (bad + good) // 2
        if is_good(mid, key):
            good = mid
        else:
            bad = mid
    return good


N, K = map(int, input().split())
A = sorted(map(int, input().split()))
F = sorted(map(int, input().split()), reverse=True)
print(binary_search(K))


Fixed submission:
def is_good(mid, key):
    ret = 0
    for i in range(N):
        ret += max(0, A[i] - mid // F[i])
    return ret <= key


def binary_search(key):
    bad, good = -1, 10 ** 18
    while good - bad > 1:
        mid = (bad + good) // 2
        if is_good(mid, key):
            good = mid
        else:
            bad = mid
    return good


N, K = map(int, input().split())
A = sorted(map(int, input().split()))
F = sorted(map(int, input().split()), reverse=True)
print(binary_search(K))
Buggy python submission (verdict: Runtime Error):
S = input()
N = len(S)
K = int(input())

i = 0
T = []
U = []
while i <= N - 1:
    if i == N - 1:
        T.append(S[-1])
        if S[-2] == S[-1]:
            U.append("?")
        else:
            U.append(S[-1])
        break
    if S[i] == S[i + 1]:
        T.append(S[i] + "?")
        U.append("?" + S[i])
        i += 2
    else:
        T.append(S[i])
        U.append(S[i])
        i += 1

T = "".join(T)
U = "".join(U)
if T[0] == T[-1]:
    print((K + 1) // 2 * T.count("?") + K // 2 * U.count("?"))
else:
    print(K * T.count("?"))


Fixed submission:
S = input()
K = int(input())
prev = S[0]
compressed = [[prev, 1]]
for c in S[1:]:
    if c == compressed[-1][0]:
        compressed[-1][1] += 1
    else:
        compressed.append([c, 1])
if len(compressed) == 1:
    print(len(S) * K // 2)
else:
    ans = sum(cnt // 2 for _, cnt in compressed) * K
    if S[0] == S[-1]:
        tmp = (compressed[0][1] + compressed[-1][1]) // 2
        tmp -= compressed[0][1] // 2
        tmp -= compressed[-1][1] // 2
        ans += tmp * (K - 1)
    print(ans)