Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    s = input()

    ans = 1
    for c in 'RGB':
        ans *= s.count(c)

    for j in range(N):
        for i in range(j):
            k = (j - i) + j
            if k >= N: continue
            if len({s[x] for x in (i, j, k)}) == 3:
                ans -= 1

    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    from bisect import bisect_left

    N = int(input())
    s = input()

    Rs = []
    Gs = []
    Bs = []
    for i, c in enumerate(s):
        if c == 'R':
            Rs.append(i)
        elif c == 'G':
            Gs.append(i)
        else:
            Bs.append(i)

    s += 'Z' * 4000

    ans = 0
    for mid in Rs:
        for g in Gs:
            if g >= mid: break
            ans += len(Bs) - bisect_left(Bs, mid) - (1 if s[mid * 2 - g] == 'B' else 0)
        for b in Bs:
            if b >= mid: break
            ans += len(Gs) - bisect_left(Gs, mid) - (1 if s[mid * 2 - b] == 'G' else 0)
    for mid in Gs:
        for r in Rs:
            if r >= mid: break
            ans += len(Bs) - bisect_left(Bs, mid) - (1 if s[mid * 2 - r] == 'B' else 0)
        for b in Bs:
            if b >= mid: break
            ans += len(Rs) - bisect_left(Rs, mid) - (1 if s[mid * 2 - b] == 'R' else 0)
    for mid in Bs:
        for r in Rs:
            if r >= mid: break
            ans += len(Gs) - bisect_left(Gs, mid) - (1 if s[mid * 2 - r] == 'G' else 0)
        for g in Gs:
            if g >= mid: break
            ans += len(Rs) - bisect_left(Rs, mid) - (1 if s[mid * 2 - g] == 'R' else 0)
    print(ans)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())
Buggy python submission (verdict: Runtime Error):
def main():
    from functools import lru_cache

    inf = 2 * 10 ** 14 + 1

    N = int(input())
    *a, = map(int, input().split())

    @lru_cache(maxsize=None)
    def recursion(cur, need):
        """
        cur: pickableなindex
        """
        if cur >= N:
            if need == 0:
                return 0
            else:
                return -inf

        rest = N - cur
        if (rest + 1) // 2 < need:
            return -inf

        return max(
            a[cur] + recursion(cur + 2, need - 1),
            recursion(cur + 1, need)
        )

    ans = recursion(0, N // 2)

    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    from collections import defaultdict

    inf = 10 ** 15

    N = int(input())
    *a, = map(int, input().split())

    it = iter(a)

    dp = [defaultdict(lambda: -inf) for _ in range(N + 1)]
    dp[0][0] = 0
    dp[1][0] = 0
    dp[1][1] = next(it)
    for i, x in enumerate(it, 2):
        mi = (i - 1) // 2
        ma = (i + 1) // 2
        for taken_count in range(mi, ma + 1):
            dp[i][taken_count] = max(
                dp[i - 1][taken_count],
                dp[i - 2][taken_count - 1] + x
            )

    ans = dp[N][N // 2]

    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    from collections import deque

    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1

    g = tuple(set() for _ in range(N))
    for v in range(N):
        if v > 0:
            g[v].add(v - 1)
        if v < N - 1:
            g[v].add(v + 1)

    g[X].add(Y)
    g[Y].add(X)

    ctr = [0] * N
    for v in range(N):
        dist = [-1] * N

        q = deque()
        q.append((v, 0))

        while q:
            v, d = q.popleft()
            if ~dist[v] and dist[v] < d: continue
            dist[v] = d
            for u in g[v]:
                if ~dist[u]: continue
                dist[u] = d + 1
                q.append((u, d + 1))

        for d in dist:
            ctr[d] += 1

    print(*map(lambda x: x // 2, ctr[1:]), sep='\n')


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    from collections import deque

    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1

    g = tuple(set() for _ in range(N))
    for v in range(N):
        if v > 0:
            g[v].add(v - 1)
        if v < N - 1:
            g[v].add(v + 1)

    g[X].add(Y)
    g[Y].add(X)

    ctr = [0] * N
    for v in range(N):
        dist = [-1] * N

        q = deque()
        q.append((v, 0))

        while q:
            v, d = q.popleft()
            if ~dist[v] and dist[v] < d: continue
            dist[v] = d
            for u in g[v]:
                if ~dist[u]: continue
                dist[u] = d + 1
                q.append((u, d + 1))

        for d in dist:
            ctr[d] += 1

    print(*map(lambda x: x // 2, ctr[1:]), sep='\n')


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    from collections import defaultdict
    N = int(input())
    *a, = map(int, input().split())

    d = defaultdict(int)
    for x in a:
        d[x] += 1

    for x in a:
        t = 0
        d[x] -= 1

        for key, value in d.items():
            t += value * (value - 1) // 2

        d[x] += 1

        print(t)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())


Fixed submission:
def main():
    N = int(input())
    *a, = map(int, input().split())

    d = [0] * (N + 1)
    for x in a:
        d[x] += 1

    b = 0
    for x in d:
        b += x * (x - 1) // 2

    for x in a:
        t = b - (d[x] - 1)

        print(t)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    from collections import defaultdict

    N, P = map(int, input().split())
    S = (int(x) % P for x in input())

    dp = defaultdict(int)
    ndp = defaultdict(int)

    ret = 0
    for x in S:
        ndp[x] += 1
        for rest in dp.keys():
            next_rest = (rest * 10 + x) % P
            ndp[next_rest] += dp[rest]
        ret += ndp[0]
        dp = ndp
        ndp = defaultdict(int)

    print(ret)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())


Fixed submission:
def main():
    N, P = map(int, input().split())
    S = [int(c) for c in input()]

    ret = 0
    if P in {2, 5}:
        for i, x in enumerate(S, 1):
            if x % P == 0:
                ret += i
        print(ret)
        return

    else:
        curr_num = 0
        counter = [0] * P
        counter[0] = 1
        for i, x in enumerate(reversed(S)):
            curr_num = (curr_num + x * pow(10, i, P)) % P
            ret += counter[curr_num]
            counter[curr_num] += 1
        print(ret)
        return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, P = map(int, input().split())
    S = map(int, input())

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

    for i, x in enumerate(S):
        dp[i + 1][x % P] += 1
        for rest in range(P - 1, -1, -1):
            # dp[i + 1][rest] += dp[i][rest]

            next_rest = (rest * 10 + x) % P
            dp[i + 1][next_rest] += dp[i][rest]

    ret = sum(dp[i][0] for i in range(1, N + 1))
    print(ret)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())


Fixed submission:
def main():
    N, P = map(int, input().split())
    S = [int(c) for c in input()]

    ret = 0
    if P in {2, 5}:
        for i, x in enumerate(S, 1):
            if x % P == 0:
                ret += i
        print(ret)
        return

    else:
        curr_num = 0
        counter = [0] * P
        counter[0] = 1
        for i, x in enumerate(reversed(S)):
            curr_num = (curr_num + x * pow(10, i, P)) % P
            ret += counter[curr_num]
            counter[curr_num] += 1
        print(ret)
        return


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    import sys
    input = sys.stdin.readline

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

    fs = tuple(set() for _ in range(N))
    for _ in range(M):
        a, b = (int(x) - 1 for x in input().split())
        fs[a].add(b)
        fs[b].add(a)

    bs = tuple(set() for _ in range(N))
    for _ in range(K):
        a, b = (int(x) - 1 for x in input().split())
        bs[a].add(b)
        bs[b].add(a)

    roots = [-1] * N
    sizes = [-1] * N

    def dfs(v):
        """
        return: 連結成分のサイズを返す
        roots: 連結成分の各成分に根のindexを割り当てる
        """
        sz = 1
        for u in fs[v]:
            if ~roots[u]: continue
            roots[u] = roots[v]
            sz += dfs(u)
        return sz

    for v in range(N):
        if ~roots[v]: continue
        roots[v] = v
        sizes[v] = dfs(v)

    ans = []
    for v in range(N):
        r = roots[v]
        res = sizes[r] - 1 - len(fs[v]) - sum(1 for u in bs[v] if roots[u] == r)
        ans.append(res)

    print(*ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    from collections import defaultdict, deque
    import sys
    input = sys.stdin.readline

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

    g = tuple(set() for _ in range(N))
    direct_friend = [0] * N
    for _ in range(M):
        a, b = (int(x) - 1 for x in input().split())

        g[a].add(b)
        g[b].add(a)

        direct_friend[a] += 1
        direct_friend[b] += 1

    bk = tuple(set() for _ in range(N))
    for _ in range(K):
        c, d = (int(x) - 1 for x in input().split())
        bk[c].add(d)
        bk[d].add(c)

    dq = deque()
    checked = [-1] * N
    for v in range(N):
        if ~checked[v]:
            continue

        dq.append((v, v))  # v,root
        checked[v] = v
        while dq:
            v, root = dq.pop()
            for u in g[v]:
                if ~checked[u]:
                    continue
                checked[u] = root
                dq.append((u, root))

    ctr = defaultdict(int)
    for v in range(N):
        root = checked[v]
        ctr[root] += 1

    ret = []
    for v in range(N):
        root = checked[v]
        t = ctr[root] - direct_friend[v] - 1
        for u in bk[v]:
            if checked[u] == root:
                # 同じ連結成分に属するがブロック関係
                # for二重なので間に合わないと思っていたが総数K<=10**5で間に合う
                t -= 1
        ret.append(t)

    print(*ret)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
# 解説放送

def main():
    from itertools import islice, tee

    k, q = map(int, input().split())
    *d, = map(int, input().split())
    for g in tee(d, q):
        n, x, m = map(int, input().split())
        g = map(lambda x: x % m, g)
        g1, g2, g3 = tee(g, 3)
        rep, rest = divmod(n - 1, k)
        last = x + (sum(g1) * rep) + sum(islice(g2, 0, rest))
        eq = sum(rep + (1 if i < rest else 0) for i, gg in enumerate(g3) if gg == 0)
        ans = (n - 1) - eq - (last // m - x // m)
        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
# 解説放送

def main():
    from itertools import islice, tee

    k, q = map(int, input().split())
    *d, = map(int, input().split())
    for g in tee(d, q):
        n, x, m = map(int, input().split())
        g = map(lambda x: x % m, g)
        g1, g2, g3 = tee(g, 3)
        rep, rest = divmod(n - 1, k)
        last = x + (sum(g1) * rep) + sum(islice(g2, 0, rest))
        eq = sum(rep + (1 if i < rest else 0) for i, gg in enumerate(g3) if gg == 0)
        ans = (n - 1) - eq - (last // m - x // m)
        print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def prime_decomposition(n):
    ret = set()

    x = n

    divisor = 2
    while x % divisor == 0:
        x //= divisor
        ret.add(divisor)

    divisor = 3
    while divisor * divisor <= n:
        while x % divisor == 0:
            x //= divisor
            ret.add(divisor)
        divisor += 2

    if x > 1:
        ret.add(x)

    return ret


def main():
    from functools import reduce
    from operator import mul

    n, k, s = map(int, input().split())

    pd = prime_decomposition(s)
    m = reduce(mul, pd) - 1  # 互いに素

    ret = [s] * k + [m] * (n - k)
    print(*ret)


if __name__ == '__main__':
    main()


Fixed submission:
def prime_decomposition(n):
    ret = set()

    x = n

    divisor = 2
    while x % divisor == 0:
        x //= divisor
        ret.add(divisor)

    divisor = 3
    while divisor * divisor <= n:
        while x % divisor == 0:
            x //= divisor
            ret.add(divisor)
        divisor += 2

    if x > 1:
        ret.add(x)

    return ret


def main():
    from functools import reduce
    from operator import mul

    n, k, s = map(int, input().split())

    pd = prime_decomposition(s)
    if not pd:
        m = s + 1
    else:
        m = reduce(mul, pd) - 1  # 互いに素

    ret = [s] * k + [m] * (n - k)
    print(*ret)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    from collections import deque

    dd = 0, 1, 0, -1

    H, W = map(int, input().split())
    G = [input() for _ in range(H)]

    def dist(sr, sc, gr, gc):
        if G[sr][sc] == '#' or G[gr][gc] == '#':
            return -1

        memo = [[-1] * W for _ in range(H)]

        dq = deque()
        dq.append((sr, sc, 0))
        while dq:
            r, c, d = dq.popleft()
            if r == gr and c == gc:
                return d

            nd = d + 1
            for i in range(4):
                nr = r + dd[i]
                nc = c + dd[i ^ 1]
                if not (0 <= nr < H and 0 <= nc < W):
                    continue
                if ~memo[nr][nc]:
                    continue
                if G[nr][nc] == '#':
                    continue
                dq.append((nr, nc, nd))
                memo[nr][nc] = nd

        return -1

    ans = 0
    for sr in range(H):
        for sc in range(W):
            for gr in range(H):
                for gc in range(W):
                    ans = max(ans, dist(sr, sc, gr, gc))

    print(ans)


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok


Fixed submission:
def main():
    from collections import deque

    h, w = map(int, input().split())

    s = [input() for _ in range(h)]

    drdc = (1, 0), (-1, 0), (0, 1), (0, -1)

    ret = -1
    for r in range(h):
        for c in range(w):
            if s[r][c] == '.':
                dist = [[-1] * w for _ in range(h)]
                dist[r][c] = 0

                q = deque()
                q.append((r, c, 0))

                md = -1
                while q:
                    qr, qc, d = q.popleft()
                    for dr, dc in drdc:
                        nr = qr + dr
                        if nr < 0 or h <= nr:
                            continue
                        nc = qc + dc
                        if nc < 0 or w <= nc:
                            continue
                        if s[nr][nc] == '#':
                            continue
                        if dist[nr][nc] != -1:
                            continue
                        nd = d + 1
                        dist[nr][nc] = nd
                        if md < nd:
                            md = nd

                        q.append((nr, nc, nd))

                ret = max(ret, md)

    print(ret)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    MOD = 10 ** 9 + 7
    n, k = map(int, input().split())
    *a, = map(int, input().split())

    compress = {x: i for i, x in enumerate(sorted(set(a)), 1)}
    rev = {i: x for x, i in compress.items()}

    e = [compress[x] for x in a]

    # -+-+-+-prepare combination-+-+-+-
    # -+-+-+-START-+-+-+-
    fact = [1] * (n + 1)
    for x in range(2, n + 1):
        fact[x] = x * fact[x - 1] % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(fact[n], MOD - 2, MOD)
    for x in range(n - 1, 0, -1):
        invs[x] = invs[x + 1] * (x + 1) % MOD

    def cmb(n, r):
        if n < r:
            return 0
        return (((invs[r] * invs[n - r]) % MOD) * fact[n]) % MOD

    # -+-+-+-END-+-+-+-

    def add(k, x):
        while k <= n:
            b[k] += x
            k += k & -k

    def get(k):
        s = 0
        while k:
            s += b[k]
            k -= k & -k
        return s

    ret = 0
    b = [0] * (n + 10)

    cnt = [0] * (n + 10)
    for a_ in a:
        e_ = compress[a_]
        add(e_, 1)
        cnt[a_] += 1

    for e_ in e:
        a_ = rev[e_]
        c = cnt[a_]

        smaller_eq = get(e_)
        ser = n - smaller_eq

        cnt_s = 0
        for x in range(1, min(k, c) + 1):
            cnt_s = (cnt_s + cmb(ser, k - x) * cmb(c, x)) % MOD

        larger_eq = n - get(e_ - 1)
        ler = n - larger_eq

        cnt_l = 0
        for x in range(1, min(k, c) + 1):
            cnt_l = (cnt_l + cmb(ler, k - x) * cmb(c, x)) % MOD

        ret = (ret + (cnt_l - cnt_s) * a_) % MOD

    print(ret % MOD)


if __name__ == '__main__':
    main()

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

# int(input())
# map(int, input().split())


Fixed submission:
MOD = 10 ** 9 + 7

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

# -+-+-+-prepare combination-+-+-+-
# -+-+-+-START-+-+-+-
fact = [1] * (n + 1)
for x in range(2, n + 1):
    fact[x] = x * fact[x - 1] % MOD

invs = [1] * (n + 1)
invs[n] = pow(fact[n], MOD - 2, MOD)
for x in range(n - 1, 0, -1):
    invs[x] = invs[x + 1] * (x + 1) % MOD


def cmb(n, r):
    if n < r:
        return 0
    return (((invs[r] * invs[n - r]) % MOD) * fact[n]) % MOD


# -+-+-+-END-+-+-+-

ret = 0
for lt, x in enumerate(a):
    gt = n - lt - 1
    mi = cmb(gt, k - 1)
    ma = cmb(lt, k - 1)
    ret = (ret + (ma - mi) * x) % MOD

print(ret)
Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/dwacon6th-prelims/submissions/9425560
# 部分点解法

def main():
    from functools import reduce

    MOD = 10 ** 9 + 7

    n = int(input())
    *x, = map(int, input().split())

    fact = [1]
    for i in range(1, n + 1):
        fact.append(fact[-1] * i)

    dist_to_r_edge = [x[-1] - x_ for x_ in x[:-1]]

    ret = reduce(
        lambda a, b: (a + b) % MOD,
        (
            d * pow(i, MOD - 2, MOD)
            for i, d in enumerate(dist_to_r_edge, 1)
        )
    )
    print(ret * fact[n - 1] % MOD)


if __name__ == '__main__':
    main()

# ret = 0
# for i, d in enumerate(dist_to_r_edge, 1):
#     ret = (ret + d * pow(i, MOD - 2, MOD)) % MOD
# print(ret * fact[n - 1] % MOD)


Fixed submission:
def main():
    from itertools import accumulate

    MOD = 10 ** 9 + 7
    n = int(input())
    *x, = map(int, input().split())
    y = [b - a for b, a in zip(x[1:], x)]

    csum_invs = [0] + list(accumulate([pow(i, MOD - 2, MOD) for i in range(1, n + 1)]))
    # csum_invs = [0]
    # t = 0
    # for i in range(1, n + 1):
    #     t += pow(i, MOD - 2, MOD)
    #     t %= MOD
    #     csum_invs.append(t)

    fact = [0]
    t = 1
    for i in range(1, n + 1):
        t *= i
        t %= MOD
        fact.append(t)

    ret = 0
    for j, y_ in enumerate(y, 1):
        ret = (ret + csum_invs[j] * y_) % MOD
    print((ret * fact[n - 1]) % MOD)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    from functools import reduce
    from math import gcd

    def lcm(a, b):
        return (a // gcd(a, b)) * b

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

    p = -1
    b = []
    for x in a:
        cnt = 0
        while x % 2 == 0:
            x //= 2
            cnt += 1
        if ~p and p != cnt:
            print(0)
            return
        p = cnt
        b.append(x)

    if p == 0:
        print(0)
        return

    t = pow(2, p - 1) * reduce(lcm, b)
    ans = (M // t) - (M // (t * 2))

    print(ans)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())


Fixed submission:
# https://atcoder.jp/contests/abc150/submissions/9395610

def main():
    from functools import reduce

    def count_two(x):
        ret = 0
        while x % 2 == 0:
            x //= 2
            ret += 1
        return ret

    def lcm(a, b):
        def _gcd(a, b):
            return a if b == 0 else _gcd(b, a % b)

        return a * b // _gcd(a, b)

    n, m = map(int, input().split())
    *a, = map(int, input().split())

    a = [x >> 1 for x in a]

    e = len(set(map(count_two, a)))
    if e != 1:
        print(0)
        return

    # x=(ai/2)*(2p+1)と変形する
    # 2p+1は奇数だから、
    # すべてのiについて,xと(ai/2)は,2で割れる回数が等しい必要がある

    x = reduce(lcm, a)
    ret = (m // x) - (m // (x + x))
    print(ret)
    # xは(ai/2)の最小公倍数の奇数倍
    # (ai/2)の最小公倍数の倍数全体から
    # (ai/2)の最小公倍数の偶数倍を引いた残り


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
# 解説放送を見た
# https://youtu.be/9MphwmIsO7Q?t=5738

def main():
    mod = 10 ** 9 + 7

    n = int(input())
    *c, = map(int, input().split())

    c.sort()

    pw = [1 << j for j in range(n + 1)]

    ret = 0
    for l, x in enumerate(c):
        r = n - 1 - l  # lxr
        ret = (ret + x * pw[l] * (pw[r] + pw[r - 1] * r)) % mod

    ret = ret * pw[n] % mod

    print(ret)


if __name__ == '__main__':
    main()


Fixed submission:
# 解説放送を見た
# https://youtu.be/9MphwmIsO7Q?t=5738

def main():
    mod = 10 ** 9 + 7

    n = int(input())
    *c, = map(int, input().split())

    c.sort()

    pw = [1]
    t = 1
    for _ in range(n):
        t = t * 2 % mod
        pw.append(t)

    ret = 0
    for l, x in enumerate(c):
        r = n - 1 - l  # lxr
        ret = (ret + x * pw[l] * (pw[r] + pw[r - 1] * r)) % mod

    ret = ret * pw[n] % mod

    print(ret)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product
from string import digits

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

ret = 0
for perm in product(digits, repeat=3):
    i = 0
    for c in s:
        if c == perm[i]:
            i += 1
            if i == 3:
                break
    if i == 3:
        ret += 1

print(ret)


Fixed submission:
def main():
    from collections import defaultdict

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

    d = defaultdict(bool)

    for c in s:
        for x in '0123456789':
            for y in '0123456789':
                if d[x + y]:
                    d[x + y + c] = True
        for x in '0123456789':
            if d[x]:
                d[x + c] = True
        d[c] = True

    print(sum(len(k) == 3 for k in d))


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = map(int, input())

dp = tuple([0] * 1000 for _ in range(4))
dp[0][0] = 1
# dp[x][int(str)]:=x文字のstrは構成可能か？0/1

for x in s:
    for k in range(2, -1, -1):
        for incomplete_key in range(100):
            dp[k + 1][incomplete_key * 10 + x] |= dp[k][incomplete_key]

print(sum(dp[3]))

# dp


Fixed submission:
def main():
    from collections import defaultdict

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

    d = defaultdict(bool)

    for c in s:
        for x in '0123456789':
            for y in '0123456789':
                if d[x + y]:
                    d[x + y + c] = True
        for x in '0123456789':
            if d[x]:
                d[x + c] = True
        d[c] = True

    print(sum(len(k) == 3 for k in d))


if __name__ == '__main__':
    main()