Problem p03015 (python)

Fixed submission:
#!/usr/bin/env python3
import sys
from operator import itemgetter
# gcd
# from fractions import gcd
# 切り上げ，切り捨て
# from math import ceil, floor
# リストの真のコピー（変更が伝播しない）
# from copy import deepcopy
# 累積和。list(accumulate(A))としてAの累積和
# from itertools import accumulate
# l = ['a', 'b', 'b', 'c', 'b', 'a', 'c', 'c', 'b', 'c', 'b', 'a']
# S = Counter(l)  # カウンタークラスが作られる。S=Counter({'b': 5, 'c': 4, 'a': 3})
# print(S.most_common(2))  # [('b', 5), ('c', 4)]
# print(S.keys())  # dict_keys(['a', 'b', 'c'])
# print(S.values())  # dict_values([3, 5, 4])
# print(S.items())  # dict_items([('a', 3), ('b', 5), ('c', 4)])
# from collections import Counter
# import math
# from functools import reduce
#
# input関係の定義
# fin = open('in_2.txt', 'r')
# sys.stdin = fin
# 提出時はコメントアウト+上のshebangを有効にする
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template

MOD = 1000000007  # type: int

def iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word

if __name__ == '__main__':

    tokens = iterate_tokens()
    L = list(map(int, list(next(tokens))))  # type: int
    
    # print(L)
    # write code
    dp = [[0, 0] for _ in range(100005)]
    dp[0][0] = 1
    # 桁dpをする
    # dp[i][0]……i桁目までみて一致する個数
    # dp[i][0]……i桁目までみて真に小さい個数
    for i in range(len(L)):
        # a+b = 0の数
        if L[i] == 0:
            dp[i + 1][0] += dp[i][0]
            dp[i + 1][1] += dp[i][1]
        else:
            dp[i+1][1] += dp[i][0] + dp[i][1]
        # a+b = 1の数
        if L[i] == 0:
            dp[i + 1][1] += dp[i][1] * 2
        else:
            dp[i + 1][0] += dp[i][0] * 2
            dp[i + 1][1] += dp[i][1] * 2
        dp[i + 1][0] %= MOD
        dp[i + 1][1] %= MOD
    print((dp[len(L)][0]+dp[len(L)][1])%MOD)

Buggy submission (verdict: Runtime Error):
##!/usr/bin/env python3
import sys
from operator import itemgetter
# gcd
# from fractions import gcd
# 切り上げ，切り捨て
# from math import ceil, floor
# リストの真のコピー（変更が伝播しない）
# from copy import deepcopy
# 累積和。list(accumulate(A))としてAの累積和
# from itertools import accumulate
# l = ['a', 'b', 'b', 'c', 'b', 'a', 'c', 'c', 'b', 'c', 'b', 'a']
# S = Counter(l)  # カウンタークラスが作られる。S=Counter({'b': 5, 'c': 4, 'a': 3})
# print(S.most_common(2))  # [('b', 5), ('c', 4)]
# print(S.keys())  # dict_keys(['a', 'b', 'c'])
# print(S.values())  # dict_values([3, 5, 4])
# print(S.items())  # dict_items([('a', 3), ('b', 5), ('c', 4)])
# from collections import Counter
# import math
# from functools import reduce
#
sys.setrecursionlimit(1000000000)
# input関係の定義
fin = open('in_2.txt', 'r')
sys.stdin = fin
# 提出時はコメントアウト+上のshebangを有効にする
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template

MOD = 1000000007  # type: int

def iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word

def calculate(x):
    global cnt
    cnt += 1
    if x == 0:
        return 0
    elif x == 1:
        return 1
    else:
        return (3*calculate(x//2)+(x%2)*pow(2,bin(x-1).count('1')))%MOD

if __name__ == '__main__':

    tokens = iterate_tokens()
    L = int(next(tokens),2)  # type: int
    cnt = 0
    # print(L)
    # write code
    print(calculate(L+1))
    # print(cnt)