Buggy python submission (verdict: Time Limit Exceeded):
import sys


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


sys.setrecursionlimit(20000000)
MOD = 10 ** 9 + 7


def main():
    L = input()

    pow = [0] * (len(L) + 1)
    pow[0] = 1
    for i in range(1, len(L) + 1):
        pow[i] = pow[i - 1] * 3 % MOD

    def cnt(s):
        if len(s) == 1:
            if s[0] == "1":
                return 3
            else:
                return 1
        if s[0] == "0":
            return cnt(s[1:]) % MOD
        else:
            return (cnt(s[1:]) * 2) % MOD + pow[len(s) - 1]

    answer = cnt(L) % MOD

    print(answer)


if __name__ == "__main__":
    main()


Fixed submission:
import sys
import queue


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


sys.setrecursionlimit(20000000)
MOD = 10 ** 9 + 7


def main():
    L = list(input())

    pow = [0] * (len(L) + 1)
    pow[0] = 1
    for i in range(1, len(L) + 1):
        pow[i] = pow[i - 1] * 3 % MOD
    N = len(L)
    if L[-1] == "0":
        answer = 1
    else:
        answer = 3
    for i in range(1, N):
        if L[N - i - 1] == "1":
            answer = answer * 2 + pow[i]
            answer %= MOD
        else:
            continue
    print(answer)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


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


sys.setrecursionlimit(20000000)
MOD = 10 ** 9 + 7


def main():
    L = list(input())

    pow = [0] * (len(L) + 1)
    pow[0] = 1
    for i in range(1, len(L) + 1):
        pow[i] = pow[i - 1] * 3 % MOD

    def cnt(s):
        if len(s) == 1:
            if s[0] == "1":
                return 3
            else:
                return 1
        if s[0] == "0":
            return cnt(s[1:]) % MOD
        else:
            return (cnt(s[1:]) * 2) % MOD + pow[len(s) - 1]

    answer = cnt(L) % MOD

    print(answer)


if __name__ == "__main__":
    main()


Fixed submission:
import sys
import queue


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


sys.setrecursionlimit(20000000)
MOD = 10 ** 9 + 7


def main():
    L = list(input())

    pow = [0] * (len(L) + 1)
    pow[0] = 1
    for i in range(1, len(L) + 1):
        pow[i] = pow[i - 1] * 3 % MOD
    N = len(L)
    if L[-1] == "0":
        answer = 1
    else:
        answer = 3
    for i in range(1, N):
        if L[N - i - 1] == "1":
            answer = answer * 2 + pow[i]
            answer %= MOD
        else:
            continue
    print(answer)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


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


sys.setrecursionlimit(20000000)
MOD = 10 ** 9 + 7


def main():
    L = list(input())

    def power(a, n):
        x = 1
        while n:
            if n & 1:
                x = x * a % MOD
            n >>= 1
            a = a * a % MOD
        return x

    pow = [0] * (len(L) + 1)
    pow[0] = 1
    for i in range(1, len(L) + 1):
        pow[i] = pow[i - 1] * 3

    def cnt(s):
        if len(s) == 1:
            if s[0] == "1":
                return 3
            else:
                return 1
        if s[0] == "0":
            return cnt(s[1:]) % MOD
        else:
            return (cnt(s[1:]) * 2) % MOD + pow[len(s) - 1]

    answer = cnt(L) % MOD

    print(answer)


if __name__ == "__main__":
    main()


Fixed submission:
import sys
import queue


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


sys.setrecursionlimit(20000000)
MOD = 10 ** 9 + 7


def main():
    L = list(input())

    pow = [0] * (len(L) + 1)
    pow[0] = 1
    for i in range(1, len(L) + 1):
        pow[i] = pow[i - 1] * 3 % MOD
    N = len(L)
    if L[-1] == "0":
        answer = 1
    else:
        answer = 3
    for i in range(1, N):
        if L[N - i - 1] == "1":
            answer = answer * 2 + pow[i]
            answer %= MOD
        else:
            continue
    print(answer)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


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


sys.setrecursionlimit(20000000)
MOD = 10 ** 9 + 7


def main():
    L = list(input())

    def power(a, n):
        x = 1
        while n:
            if n & 1:
                x = x * a % MOD
            n >>= 1
            a = a * a % MOD
        return x

    def cnt(s):
        if len(s) == 1:
            if s[0] == "1":
                return 3
            else:
                return 1
        if s[0] == "0":
            return cnt(s[1:]) % MOD
        else:
            return (cnt(s[1:]) * 2) % MOD + pow(3, len(s) - 1)

    answer = cnt(L) % MOD

    print(answer)


if __name__ == "__main__":
    main()


Fixed submission:
import sys
import queue


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


sys.setrecursionlimit(20000000)
MOD = 10 ** 9 + 7


def main():
    L = list(input())

    pow = [0] * (len(L) + 1)
    pow[0] = 1
    for i in range(1, len(L) + 1):
        pow[i] = pow[i - 1] * 3 % MOD
    N = len(L)
    if L[-1] == "0":
        answer = 1
    else:
        answer = 3
    for i in range(1, N):
        if L[N - i - 1] == "1":
            answer = answer * 2 + pow[i]
            answer %= MOD
        else:
            continue
    print(answer)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


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


sys.setrecursionlimit(20000000)
MOD = 10 ** 9 + 7


def main():
    L = list(input())

    def cnt(s):
        if len(s) == 1:
            if s[0] == "1":
                return 3
            else:
                return 1
        if s[0] == "0":
            return cnt(s[1:]) % MOD
        else:
            return (cnt(s[1:]) % MOD) * 2 + 3 ** (len(s) - 1) % MOD

    answer = cnt(L) % MOD

    print(answer)


if __name__ == "__main__":
    main()


Fixed submission:
import sys
import queue


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


sys.setrecursionlimit(20000000)
MOD = 10 ** 9 + 7


def main():
    L = list(input())

    pow = [0] * (len(L) + 1)
    pow[0] = 1
    for i in range(1, len(L) + 1):
        pow[i] = pow[i - 1] * 3 % MOD
    N = len(L)
    if L[-1] == "0":
        answer = 1
    else:
        answer = 3
    for i in range(1, N):
        if L[N - i - 1] == "1":
            answer = answer * 2 + pow[i]
            answer %= MOD
        else:
            continue
    print(answer)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Runtime Error):
import sys


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


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """

    def __init__(self, n_max, mod=10 ** 9 + 7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        if n < r:
            return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n - r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n + 1):
            fac.append(fac[i - 1] * i % self.mod)
            facinv.append(facinv[i - 1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n + 1)
        modinv[1] = 1
        for i in range(2, n + 1):
            modinv[i] = self.mod - self.mod // i * modinv[self.mod % i] % self.mod
        return modinv


MOD = 10 ** 9 + 7


def main():
    L = list(input())

    def cnt(s):
        if len(s) == 1:
            if s[0] == "1":
                return 3
            else:
                return 1
        if s[0] == "0":
            return cnt(s[1:]) % MOD
        else:
            return (cnt(s[1:]) % MOD) * 2 + 3 ** (len(s) - 1) % MOD

    answer = cnt(L) % MOD

    print(answer)


if __name__ == "__main__":
    main()


Fixed submission:
import sys
import queue


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


sys.setrecursionlimit(20000000)
MOD = 10 ** 9 + 7


def main():
    L = list(input())

    pow = [0] * (len(L) + 1)
    pow[0] = 1
    for i in range(1, len(L) + 1):
        pow[i] = pow[i - 1] * 3 % MOD
    N = len(L)
    if L[-1] == "0":
        answer = 1
    else:
        answer = 3
    for i in range(1, N):
        if L[N - i - 1] == "1":
            answer = answer * 2 + pow[i]
            answer %= MOD
        else:
            continue
    print(answer)


if __name__ == "__main__":
    main()