Problem:
 Score : 500 points    Problem Statement You are given a positive integer L in base two.
How many pairs of non-negative integers (a, b) satisfy the following conditions?   a + b \leq L  a + b = a \mbox{ XOR } b   Since there can be extremely many such pairs, print the count modulo 10^9 + 7 .   What is XOR?  The XOR of integers A and B , A \mbox{ XOR } B , is defined as follows:   When A \mbox{ XOR } B is written in base two, the digit in the 2^k 's place ( k \geq 0 ) is 1 if either A or B , but not both, has 1 in the 2^k 's place, and 0 otherwise.   For example, 3 \mbox{ XOR } 5 = 6 . (In base two: 011 \mbox{ XOR } 101 = 110 .)

Solution (Python):
MOD = 10 ** 9 + 7
L = input()
N = len(L)
total = 0
one_count = 0
p3 = [1] * N
for i in range(1, N):
    p3[i] = p3[i - 1] * 3 % MOD
p2 = 1
for i in range(N):
    if L[i] == "1":
        total = (total + p2 * p3[N - i - 1]) % MOD
        p2 = p2 * 2 % MOD
print((total + p2 * p3[N - i - 1]) % MOD)

Solution (Python):
MOD = 10 ** 9 + 7
L = input()
N = len(L)
total = 0
one_count = 0
pow2, pow3 = [1], [1]
p2, p3 = 1, 1
for i in range(N):
    p2 = p2 * 2 % MOD
    p3 = p3 * 3 % MOD
    pow2.append(p2)
    pow3.append(p3)
for i in range(N):
    if L[i] == "1":
        total = (total + pow2[one_count] * pow3[N - i - 1]) % MOD
        one_count += 1
print((total + pow2[one_count] * pow3[N - i - 1]) % MOD)

Solution (Python):
"""

AtCoder Beginner Contest 129  E - Sum Equals Xor

XORは桁上がりがないので、A xor B がA+Bより大きくなることはない（最大でもA+Bまで）
なので、 A xor B = A + B が成立するのは、AとBを二進数でみたときに、両方1が立っているbitがないこと。

桁DPの文脈で考えると、
dp1,2[i] : AやBの左からi文字目までを決めたときに、
・dp2 : その時点でのA+BがL以下になることがわかっている（左からi番目までについて、A+Bのp桁目は0だが、Lのp桁目は1、みたいなのが存在する（先頭～p-1までは一致してもしなくてもOK））AとBの組の個数
・dp1 : その時点ではA+BがL以下になるか分からないAとBの組の個数（その時点まではLのi桁目までと一致する組の数）



遷移について、
Lのi桁目が
・0の場合
 - dp1 : dp2から遷移するとL以下になることが確定するので、dp2から遷移してくることはない＆A+Bのiビット目に1が立つとLを上回るので、0になるしかなく、i桁目は両方0の１通りで遷移
 - dp2 : dp1から遷移してきてi番目に0をいれても、L以下になるか確定しないので、dp1からの遷移はない。一方で。dp2から遷移してくる場合、既にL以下であることが確定しているので、A,B = 1,1以外の３パターンをとれる
・1の場合
 - dp1 : dp2から遷移してくるのを考えると、dp2の時点で既にL以下になるのが確定しているので、dp2からは遷移できない。一方で、dp1から遷移してくる場合、i桁目までLと同じになるので、A,Bの一方が1で他方が0の２通りをとれる
 - dp2 : dp1から遷移して A,B=0,0 をとればL以下が確定＆dp2から遷移して 1,1 以外の3通りの遷移

"""


L = input()
N = len(L)
MOD = 10**9 + 7

dp1 = [0] * (N+1)
dp2 = [0] * (N+1)
dp1[0] = 1


for i in range(N):
    if L[i] == "0":
        dp1[i+1] = dp1[i] 
        dp2[i+1] = dp2[i] * 3 
    else:
        dp1[i+1] = dp1[i] * 2 
        dp2[i+1] = dp2[i] * 3 + dp1[i] 

    dp1[i+1] %= MOD
    dp2[i+1] %= MOD

print((dp1[-1] + dp2[-1]) % MOD)

Solution (Python):
"""

AtCoder Beginner Contest 129  E - Sum Equals Xor

XORは桁上がりがないので、A xor B がA+Bより大きくなることはない（最大でもA+Bまで）
なので、 A xor B = A + B が成立するのは、AとBを二進数でみたときに、両方1が立っているbitがないこと。

桁DPの文脈で考えると、
dp1,2[i] : AやBの左からi文字目までを決めたときに、
・dp2 : その時点でのA+BがL以下になることがわかっている（左からi番目までについて、A+Bのp桁目は0だが、Lのp桁目は1、みたいなのが存在する（先頭～p-1までは一致））AとBの組の個数
・dp1 : その時点ではA+BがL以下になるか分からないAとBの組の個数（その時点まではLのi桁目までと一致する組の数）



遷移について、
Lのi桁目が
・0の場合
 - dp1 : dp2から遷移するとL以下になることが確定するので、dp2から遷移してくることはない＆A+Bのiビット目に1が立つとLを上回るので、0になるしかなく、i桁目は両方0の１通りで遷移
 - dp2 : dp1から遷移してきてi番目に0をいれても、L以下になるか確定しないので、dp1からの遷移はない。一方で。dp2から遷移してくる場合、既にL以下であることが確定しているので、A,B = 1,1以外の３パターンをとれる
・1の場合
 - dp1 : dp2から遷移してくるのを考えると、dp2の時点で既にL以下になるのが確定しているので、dp2からは遷移できない。一方で、dp1から遷移してくる場合、i桁目までLと同じになるので、A,Bの一方が1で他方が0の２通りをとれる
 - dp2 : dp1から遷移して A,B=0,0 をとればL以下が確定＆dp2から遷移して 1,1 以外の3通りの遷移

"""


L = input()
N = len(L)
MOD = 10**9 + 7

dp1 = [0] * (N+1)
dp2 = [0] * (N+1)
dp1[0] = 1


for i in range(N):
    if L[i] == "0":
        dp1[i+1] = dp1[i] 
        dp2[i+1] = dp2[i] * 3 
    else:
        dp1[i+1] = dp1[i] * 2 
        dp2[i+1] = dp2[i] * 3 + dp1[i] 

    dp1[i+1] %= MOD
    dp2[i+1] %= MOD

print((dp1[-1] + dp2[-1]) % MOD)

Solution (Python):
L = input()
N = len(L)
mod = 10 ** 9 + 7
dp = [[0] * 2 for _ in range(100005)]
dp[0][0] = 1
for i in range(N):
    
    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]) % mod

    
    if L[i] == "0":
        dp[i + 1][1] += dp[i][1] * 2 % mod
        dp[i + 1][1] %= mod
    else:
        dp[i + 1][0] += dp[i][0] * 2 % mod
        dp[i + 1][0] %= mod
        dp[i + 1][1] += dp[i][1] * 2 % mod
        dp[i + 1][1] %= mod

ans = dp[N][0] + dp[N][1]
print(ans % mod)

Solution (Python):
import numpy as np

L = input()
mod = 10**9+7

DP = np.zeros((len(L)+1, 2), int)
DP[0][0] = 1

for i in range(len(L)):
    if L[i] == '1':
        DP[i+1][0] = DP[i][0] * 2
        DP[i+1][1] = DP[i][0] + DP[i][1] * 3
    else:
        DP[i+1][0] = DP[i][0]
        DP[i+1][1] = DP[i][1] * 3
    DP[i+1] %= mod

print(sum(DP[-1]) % mod)

Solution (Python):
MOD = 10 ** 9 + 7
INF = 10 ** 11
import sys
sys.setrecursionlimit(100000000)

def main():
    L = input()
    dp = [[0]*2 for _ in range(len(L) + 1)]
    
    dp[0][0] = 1
    for i in range(len(L)):
        if L[i] == '1':
            dp[i + 1][0] = dp[i][0]*2
            dp[i + 1][1] = dp[i][0] + dp[i][1]*3
        else:
            dp[i + 1][0] = dp[i][0]
            dp[i + 1][1] = dp[i][1]*3
        dp[i + 1][0] %= MOD
        dp[i + 1][1] %= MOD
    print(sum(dp[-1])%MOD)
if __name__ == '__main__':
    main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

L = input()

dp = [[0]*2 for _ in range(len(L)+1)]
dp[0][0] = 1

for i in range(len(L)):
	nd = int(L[i])
	ni = i+1
	for a in range(2):
		for b in range(2):
			if a == b == 1:
				continue
			for k in range(2):
				nk = k

				if nk == 0:  
					if nd == 1 and a == b == 0:
						nk = 1
					if nd == 0 and a | b:  
						continue

				dp[ni][nk] += dp[i][k]
				dp[ni][nk] %= mod

ans = dp[-1][0]+dp[-1][1]
print(ans%mod)

Solution (Python):
MOD = 10**9 + 7


def main():
    S = input()
    N = len(S)
    dp = [[0]*2 for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        
        dp[i+1][1] += dp[i][1]*3

        
        if S[i] == "1":
            dp[i+1][0] += dp[i][0]*2
        else:
            dp[i+1][0] += dp[i][0]

        
        if S[i] == "1":
            dp[i+1][1] += dp[i][0]

        dp[i+1][0] %= MOD
        dp[i+1][1] %= MOD

    print((dp[N][0]+dp[N][1]) % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
MOD = 10**9 + 7


def main():
    L = input()
    N = len(L)
    dp = [[0]*2 for i in range(N+1)]
    dp[0][0] = 1

    for i in range(N):
        
        if L[i] == "1":
            dp[i+1][1] += dp[i][1] * 3
            dp[i+1][1] %= MOD
        else:
            dp[i+1][1] += dp[i][1] * 3
            dp[i+1][1] %= MOD
        
        if L[i] == "1":
            dp[i+1][1] += dp[i][0] * 1
            dp[i+1][1] %= MOD
        
        if L[i] == "1":
            dp[i+1][0] += dp[i][0] * 2
            dp[i+1][0] %= MOD
        else:
            dp[i+1][0] += dp[i][0] * 1
            dp[i+1][0] %= MOD

    print((dp[N][0]+dp[N][1]) % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
s = input() 
n = len(s)
p=10**9+7

dp = [[0]*2 for _ in range(n)]

dp[0][0]=2
dp[0][1]=1




for i in range(1,n):
        if s[i]=='1':
            dp[i][0] = (dp[i-1][0]*2)%p
            dp[i][1] = (dp[i-1][1]*3)%p + (dp[i-1][0])%p
        else:
            dp[i][0] = dp[i-1][0]*1
            dp[i][1] = (dp[i-1][1]*3)%p

print((dp[n-1][0]+dp[n-1][1])%p)

Solution (Python):
MOD = 10**9+7
l = input()
n = len(l)
dp = [[[0] * 2 for _ in range(3)] for _ in range(n+1)]
dp[0][0][1] = 1

for i in range(n):
    for j in range(3):
        dp[i][j][0] %= MOD
        dp[i][j][1] %= MOD
        dp[i+1][0][0] += dp[i][j][0]
        dp[i+1][1][0] += dp[i][j][0]
        dp[i+1][2][0] += dp[i][j][0]
        if l[i] == "1":
            dp[i+1][1][1] += dp[i][j][1]
            dp[i+1][2][1] += dp[i][j][1]
            dp[i+1][0][0] += dp[i][j][1]
        else:
            dp[i+1][0][1] += dp[i][j][1]

print(sum(map(lambda x: sum(x) % MOD, dp[n])) % MOD)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
mod = 10**9+7

def main():
    L = input()
    l = len(L)
    """
    LについてbitDP、かつa, bは同じ桁に1, 1とならない
    """
    stoic = 2
    affordable = 1
    for i in range(1, l):
        if L[i] == '1':
            affordable = (stoic + affordable * 3) % mod
            stoic = (stoic * 2) % mod
        else:
            affordable = (affordable * 3) % mod

    print((stoic + affordable) % mod)







if __name__ == "__main__":
    main()

Solution (Python):




import sys
read = sys.stdin.readline
ra = range
enu = enumerate


class ModInt:
    def __init__(self, x, MOD=10 ** 9 + 7):
        '''
        pypyじゃないと地獄みたいな遅さなので注意
        '''
        self.mod = MOD
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x + other.x, self.mod)
        else:
            return ModInt(self.x + other, self.mod)

    def __sub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x - other.x, self.mod)
        else:
            return ModInt(self.x - other, self.mod)

    def __mul__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * other.x, self.mod)
        else:
            return ModInt(self.x * other, self.mod)

    def __truediv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * pow(other.x, self.mod - 2, self.mod), self.mod)
        else:
            return ModInt(self.x * pow(other, self.mod - 2, self.mod), self.mod)

    def __pow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(self.x, other.x, self.mod), self.mod)
        else:
            return ModInt(pow(self.x, other, self.mod), self.mod)

    __radd__ = __add__

    def __rsub__(self, other):  
        if isinstance(other, ModInt):
            return ModInt(other.x - self.x, self.mod)
        else:
            return ModInt(other - self.x, self.mod)

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(other.x * pow(self.x, self.mod - 2, self.mod), self.mod)
        else:
            return ModInt(other * pow(self.x, self.mod - 2, self.mod), self.mod)

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, self.mod), self.mod)
        else:
            return ModInt(pow(other, self.x, self.mod), self.mod)


MOD = 10 ** 9 + 7

L = read()[:-1]
n = len(L)




dp = [[0] * 2 for _ in ra(n + 1)]
dp[0][0] = ModInt(1)
for i in ra(n):
    
    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]

    
    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

print(dp[-1][0] + dp[-1][1])

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    
    mod = 10**9 + 7

    l = input().rstrip()
    n = len(l)

    
    
    dp1 = [0]*n
    
    dp2 = [0]*n
    
    
    dp1[0] = 1
    dp2[0] = 2
    
    for i in range(1, n):
        if l[i] == '1':
            dp1[i] = (dp1[i-1] * 3 + dp2[i-1]) % mod
            dp2[i] = dp2[i-1] * 2 % mod
        else:
            dp1[i] = dp1[i-1] * 3 % mod
            dp2[i] = dp2[i-1]
    print((dp1[-1]+dp2[-1]) % mod)

if __name__ == '__main__':
    main()

Solution (Python):
s=input()
ans=1
ans2=1
for i in range(len(s)):
  if s[len(s)-1-i]=='1':
    ans=(ans*2+ans2)%(10**9+7)
  ans2=(ans2*3)%(10**9+7)
print(ans)

Solution (Python):
def main():
    MOD = 10 ** 9 + 7

    EQ = 0  
    SMALL = 1  

    S = map(int, input())
    dp = [1, 0]
    for x in S:
        ndp = [0] * 2

        if x == 0:
            ndp[EQ] = dp[EQ]  
            ndp[SMALL] = dp[SMALL] * 3  
        elif x == 1:
            ndp[EQ] = dp[EQ] * 2  
            ndp[SMALL] = dp[EQ] + dp[SMALL] * 3  

        *dp, = map(lambda x: x % MOD, ndp)

    ans = sum(dp) % MOD  

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
S = input()
L = len(S)
mod = 10**9+7
dp_c = [0] * L
dp_u = [0] * L
dp_c[0] = 1
dp_u[0] = 2

for i in range(1,L):
    if S[i] == "1":
        dp_c[i] = dp_c[i-1] * 3 + dp_u[i-1]
        dp_u[i] = dp_u[i-1] * 2
    else:
        dp_c[i] = dp_c[i-1] * 3
        dp_u[i] = dp_u[i-1] * 1
    dp_c[i] %= mod
    dp_u[i] %= mod

ans = (dp_c[-1] + dp_u[-1]) % mod
print(ans)

Solution (Python):
L = list(input())
N = len(L)
if '0' not in L:
    L = ['1'] + ['0']*N
    N += 1
else:
    for i in range(N):
        t = L[N-i-1]
        if t == '0':
            L[N-i-1] = '1'
            break
        else:
            L[N-i-1] = '0'
res = 0
MOD = 10**9+7
buff = 1
for d, char in enumerate(L):
    if char == '1':
        res = (res + buff * pow(3, N-1-d, MOD))%MOD
        buff = (2 * buff) % MOD
print(res)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

l = read().rstrip().decode()
n = len(l)
mod = 10 ** 9 + 7
dp = [[0, 0] for _ in range(n)]
dp[0] = [1, 2]
for i, check in enumerate(l[1:]):
    i += 1
    dp[i][0] = dp[i - 1][0] * 3
    dp[i][1] = dp[i - 1][1]
    if check == '1':
        dp[i][0] += dp[i - 1][1]
        dp[i][1] += dp[i - 1][1]
    dp[i][0] %= mod
    dp[i][1] %= mod
print(sum(dp[-1]) % mod)

Solution (Python):
MOD = 10 ** 9 + 7

L = list(input())

N = len(L)

OK = [0] * (N + 1)
JUST = [0] * (N + 1)
JUST[0] = 1

for i in range(N):
    if L[i] == '1':
        OK[i + 1] = (OK[i] * 3 + JUST[i]) % MOD
        JUST[i + 1] = (JUST[i] * 2) % MOD
    else:
        OK[i + 1] = (OK[i] * 3) % MOD
        JUST[i + 1] = (JUST[i]) % MOD

print ((OK[-1] + JUST[-1]) % MOD)

Solution (Python):
L = input()
MOD = 10**9 + 7

eq = 1
less = 0
for n in L:
    if n == '1':
        eq, less = eq * 2, eq + less * 3
    else:
        less = less * 3
    eq %= MOD
    less %= MOD

print((eq + less) % MOD)

Solution (Python):
mod=10**9+7
s=input()
n=len(s)
dp=[[0]*2 for _ in range(n+1)]
dp[0][0]=1
for i in range(n):
  if s[i]=='0':
    dp[i+1][0]=(dp[i+1][0]+dp[i][0])%mod
    dp[i+1][1]=(dp[i+1][1]+dp[i][1]*3)%mod
  else:
    dp[i+1][0]=(dp[i+1][0]+dp[i][0]*2)%mod
    dp[i+1][1]=(dp[i+1][1]+dp[i][1]*3)%mod
    dp[i+1][1]=(dp[i+1][1]+dp[i][0])%mod
    
print(sum(dp[n])%mod)

Solution (Python):
mod = 10 ** 9 + 7

L = input()
N = len(L)

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

for i in range(N):
    nd = int(L[i])
    for a in range(2):
        for b in range(2):
            if a == b == 1:  
                continue
            for k in range(2):
                ni = i + 1
                nk = k
                if nk == 0:
                    if nd == 1 and a == 0 and b == 0:
                        nk += 1
                    if nd == 0 and a | b > 0:
                        continue
                dp[ni][nk] += dp[i][k]
                dp[ni][nk] %= mod

ans = 0
for k in range(2):
    ans += dp[N][k]
    ans %= mod

print(ans)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')

class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x + other.x)
        else:
            return ModInt(self.x + other)

    __radd__ = __add__
        
    def __sub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x - other.x)
        else:
            return ModInt(self.x - other)

    def __rsub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(other.x - self.x)
        else:
            return ModInt(other - self.x)

    def __mul__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * other.x)
        else:
            return ModInt(self.x * other)

    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * pow(other.x, mod-2,mod))
        else:
            return ModInt(self.x * pow(other, mod - 2, mod))
            
    def __rtruediv(self, other):
        if isinstance(other, self):
            return ModInt(other * pow(self.x, mod - 2, mod))
        else:
            return ModInt(other.x * pow(self.x, mod - 2, mod))
            

    def __pow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(self.x, other.x, mod))
        else:
            return ModInt(pow(self.x, other, mod))
            

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, mod))
        else:
            return ModInt(pow(other, self.x, mod))

def main():
    S=ST()
    N=len(S)
    dp = [[ModInt(0),ModInt(0)] for _ in range(N+1)] 
    dp[0][0] += 1
    for i in range(N):
        for less in range(2):
            if(less):
                dp[i+1][less] += dp[i][less] * 3
            else:
                if(S[i]=="1"):
                    dp[i+1][1] += dp[i][less] 
                    dp[i+1][0] += dp[i][less] * 2 
                else:
                    dp[i+1][0] += dp[i][less] 
    print(sum(dp[-1]))
if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    l = list(map(int, input()))
    n = len(l)
    dp = [[0]*2 for i in range(n+1)]
    dp[0][0] = 1
    for i in range(n):
        ni = i+1
        for j in range(2):
            x = 1 if j else l[i]
            for d in range(x+1):
                nj = j or d < l[i]
                if d:
                    dp[ni][nj] += 2*dp[i][j]
                else:
                    dp[ni][nj] += dp[i][j]
                dp[ni][nj] %= mod
    print(sum(dp[n])%mod)
    return


if __name__ == "__main__":
    solve()

Solution (Python):


import sys











from itertools import accumulate             







def main():
    mod = 1000000007                  
    inf = float('inf')
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    
    bs = input()
    l = len(bs)
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    A = [0] * (l+1)    
    A[1] = 3
    for i in range(2, l+1):
        if i == 2:
            A[i] = 3
        else:
            A[i] = (A[i-1] * 3) % mod

    
    def calc_pair(s, i):
        n = len(s)
        if i >= n:
            return 0      
        while i <= n - 1 and s[i] == '0':
            i += 1
        if i == n:
            return 1
        else:
            return (A[n - i] + 2 * calc_pair(s, i+1)) % mod
    
    print(calc_pair(bs, 0))


if __name__ == "__main__":
    main()

Solution (Python):
l = input()
n = len(l)
mod = pow(10, 9)+7

dp = [0]*n
if l[n-1] == "1":
  dp[0] = 3
else:
  dp[0] = 1
key = 3
for i in range(1, n):
  if l[n-1-i] == "0":
    dp[i] = dp[i-1]
  else:
    dp[i] = (dp[i-1]*2+key)%mod
  key *= 3
  key %= mod
  
print(dp[n-1])

Solution (Python):
L = input()
mod = 10**9+7
dp = [[0,0] for i in range(len(L)+1)] 
dp[0][0] = 2
dp[0][1] = 1
for i in range(len(L)-1):
    if L[i+1] == '0':
        dp[i+1][0] = dp[i][0]
        dp[i+1][1] = (dp[i][1]*3)%mod
    else:
        dp[i+1][0] = (dp[i][0]*2)%mod
        dp[i+1][1] = (dp[i][1]*3+dp[i][0])%mod
print((dp[len(L)-1][0]+dp[len(L)-1][1])%mod)

Solution (Python):
l = input()
n = len(l)
mod = 1000000007
ans = 0
cnt = 0
for i in range(n):
    if l[i] == "1":
        ans += pow(3, n - i - 1, mod) * pow(2, cnt, mod)
        ans %= mod
        cnt += 1
ans += pow(2, cnt, mod)
ans %= mod
print(ans)

Solution (Python):

"""
a+b = a^b
となる場合は、全2進数桁iに対して、
a[i] nand b[i] &1 を満たす場合になる
これは各桁に対してa[i]==b[i]==1を除く2**2-1の3通りが存在するので、
多分桁dpで制約あり/なしを求めてけば求まる
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
mod = 10**9+7
s = readline().rstrip().decode('utf-8')





dp = [[0]*2 for i in range(len(s)+2)]
dp[0][0] = 1 



for i in range(len(s)):
    for j in range(2): 
        nd = int(s[i])
        for d in range(3): 
            ni = i+1
            nj = j
            if j == 0:
                if nd==0 and d > 0:continue 
                elif nd == 1 and d==0:nj=1 

            dp[ni][nj] += dp[i][j]
            dp[ni][nj]%=mod



ans = (dp[ni][0] + dp[ni][1])%mod
print(ans)

Solution (Python):
MOD = 10**9 + 7

strL = input().rstrip()

maxD = len(strL)

dp = [[0]*(2) for _ in range(maxD+1)]
dp[0][0] = 1
for d, Ld in enumerate(strL):
    Ld = int(Ld)
    for isLT in range(2):
        dp[d][isLT] %= MOD
        for a, b in [(0, 0), (0, 1), (1, 0)]:
            if not isLT and a+b > Ld: continue
            isLT2 = isLT or a+b < Ld
            dp[d+1][isLT2] += dp[d][isLT]

ans = (dp[-1][0] + dp[-1][1]) % MOD
print(ans)

Solution (Python):
l = input()
n = len(l)
MOD = 10**9+7

dp0 = [0 for _ in range(n)]
dp1 = [0 for _ in range(n)]

dp0[0] = 1
dp1[0] = 2

for i in range(1,n):
  if l[i] == '0':
    dp1[i] = dp1[i-1]
    dp0[i] = dp0[i-1] * 3
  else:
    dp1[i] = dp1[i-1] * 2
    dp0[i] = dp1[i-1] + dp0[i-1] * 3
  dp1[i] %= MOD
  dp0[i] %= MOD  
print((dp1[-1] + dp0[-1])%MOD)

Solution (Python):
MOD = 10**9 + 7

strL = input().rstrip()

maxD = len(strL)

dp = [[0]*(2) for _ in range(maxD+1)]
dp[0][0] = 1
for d, Ld in enumerate(strL):
    Ld = int(Ld)
    for isLT in range(2):
        dp[d][isLT] %= MOD
        for a, b in [(0, 0), (0, 1), (1, 0)]:
            if not isLT and a+b > Ld: continue
            isLT2 = isLT or a+b < Ld
            dp[d+1][isLT2] += dp[d][isLT]

ans = (dp[-1][0] + dp[-1][1]) % MOD
print(ans)

Solution (Python):
MOD=10**9+7
L=input()

def powmod(a,p):
  if p==0:
    return 1
  elif p==1:
    return a
  else:
    pow2=powmod(a,p//2)
    if p%2==0:
      return (pow2**2)%MOD
    else:
      return (a*pow2**2)%MOD

def invmod(a):
  return powmod(a,MOD-2)    
    
sum=0
cnt_2=1
pow_3=powmod(3,len(L))
inv_3=invmod(3)
for i in range(len(L)):
  pow_3=pow_3*inv_3%MOD
  if L[i] == "1":
    sum += cnt_2*pow_3
    sum %= MOD
    cnt_2 = (cnt_2*2)%MOD
    
sum += cnt_2
sum %= MOD
print(sum)

Solution (Python):
MOD=10**9+7
L=input()

def powmod(a,p):
  if p==0:
    return 1
  elif p==1:
    return a
  else:
    pow2=powmod(a,p//2)
    if p%2==0:
      return (pow2**2)%MOD
    else:
      return (a*pow2**2)%MOD

sum=0
cnt_2=1
for i in range(len(L)):  
  if L[i] == "1":
    sum += cnt_2*powmod(3,len(L)-i-1)
    sum %= MOD
    cnt_2 = (cnt_2*2)%MOD
    
sum += cnt_2
sum %= MOD
print(sum)

Solution (Python):
MOD=10**9+7
L=input()

dp_eq=[2]+[-1]*(len(L)-1)
dp_ne=[1]+[-1]*(len(L)-1)

for i in range(1,len(L)):
  if L[i]=="0":
    dp_eq[i]=dp_eq[i-1]
    dp_ne[i]=3*dp_ne[i-1]%MOD
  elif L[i]=="1":
    dp_eq[i]=2*dp_eq[i-1]%MOD
    dp_ne[i]=(3*dp_ne[i-1]+dp_eq[i-1])%MOD
    

print((dp_eq[-1]+dp_ne[-1])%MOD)

Solution (Python):
L = input()
dp1 = 2
dp2 = 1
MOD = 10**9+7
for c in L[1:]:
  if c=='1':
    ndp1 = 2*dp1
    ndp2 = dp1 + 3*dp2
  else:
    ndp1 = dp1
    ndp2 = 3*dp2
  dp1,dp2 = ndp1%MOD,ndp2%MOD
print((dp1+dp2)%MOD)

Solution (Python):




L = input()
keta = len(L)
mod = 10 ** 9 + 7

dp = [[0] * 2 for _ in range(keta + 2)]
dp[0][0] = 1
for i in range(keta):
    nd = int(L[i])
    for j in range(2):
        ni = i + 1
        nj = j
        if j == 1:
            dp[ni][nj] += 3 * dp[i][j]
            dp[ni][nj] %= mod
        else:
            if nd == 0:
                dp[ni][nj] += dp[i][j]
                dp[ni][nj] %= mod
            else:  
                dp[ni][nj] += 2 * dp[i][j]  
                dp[ni][1] += dp[i][j]  
                dp[ni][nj] %= mod
ans = dp[keta][0] + dp[keta][1]
ans %= mod
print(ans)

Solution (Python):
L = input()
N = len(L)
MOD = 10**9+7
dp = [[0]*2 for _ in range(101010)]
dp[0][0] = 1
for i in range(N):
    dp[i+1][1] += 3*dp[i][1]
    dp[i + 1][1] %= MOD
    if L[i] == '1':
        dp[i+1][0] += 2*dp[i][0]  
        dp[i + 1][0] %= MOD
        dp[i+1][1] += dp[i][0]  
        dp[i + 1][1] %= MOD
    else:
        dp[i+1][0] += dp[i][0]  
        dp[i + 1][0] %= MOD
ans = (dp[N][0] + dp[N][1])%MOD
print(ans)

Solution (Python):
L = input()
MOD = 10**9+7

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

ans, m = 0, 1
while True:
    if '0' not in L:
        ans = (ans + (m * num_ab[len(L)]) % MOD) % MOD
        print(ans)
        exit()
    elif '1' not in L[1:]:
        ans = (ans + ((m * num_ab[len(L) - 1]) % MOD + (2 * m) % MOD) % MOD) % MOD
        print(ans)
        exit()
    else:
        ans = (ans + (m * num_ab[len(L) - 1]) % MOD) % MOD
        L = L[L[1:].index('1') + 1:]
        m = (2 * m) % MOD

Solution (Python):
l = input().rstrip()
n = len(l)

mod = 10**9 + 7
c = 1
d = 0
for i in range(n):
    d *= 3
    if l[i] == '1':
        d += c
        c <<= 1
    d %= mod
    c %= mod

print((c+d)%mod)

Solution (Python):
S=input()
l=len(S)
pow2=[1]
pow3=[1]
mod=10**9+7

for i in range(l+10):
    pow2.append(pow2[-1]*2%mod)
    pow3.append(pow3[-1]*3%mod)
    
if l==1:
    if S=="0":
        print(1)
    else:
        print(3)

else:
    ans=pow3[l-1]
    cnt=1 
    for i in range(l-1):
        if i==l-2:
            if S[i+1]=="1":
                ans+=pow2[cnt]*3%mod
            else:
                ans+=pow2[cnt]%mod
        else:
            if S[i+1]=="1":
                ans+=pow2[cnt]*pow3[l-i-2]%mod
                cnt+=1                                                  
    print(ans%mod)

Solution (Python):
L = input()
n = len(L)
mod = 10**9+7
dp1 = [0]*(n+1)
dp2 = [0]*(n+1)
dp1[0] = 1
for i in range(n):
    if L[i] == "1":
        dp1[i+1] = (dp1[i]*2)%mod
        dp2[i+1] = (dp1[i] + dp2[i]*3)%mod
    else:
        dp1[i+1] = dp1[i]
        dp2[i+1] = (dp2[i]*3)%mod
print((dp1[n]+dp2[n])%mod)

Solution (Python):

import sys
input = sys.stdin.readline









L = input().rstrip()

lenL = len(L)
mod = 10**9+7

dp0 = [0]*(lenL+1) 
dp1 = [0]*(lenL+1) 

dp0[0] = 1

for i,l in enumerate(L, 1):
    
    if l=="0":
        dp0[i] = dp0[i-1]   
        dp1[i] = dp1[i-1]*3 
    
    else:
        dp0[i] = dp0[i-1]*2 
        dp1[i] = dp0[i-1] + dp1[i-1]*3 
        
        
    dp0[i] %= mod
    dp1[i] %= mod

print((dp0[-1] + dp1[-1]) % mod)

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


MOD = 10 ** 9 + 7
L = sr()
dp = [1, 2]
length = len(L)
for i in range(1, length):
    prev = dp[:]
    if L[i] == '1':
        dp[0] = prev[0] * 3 + prev[1]
        dp[1] = prev[1] * 2
    else:
        dp[0] = prev[0] * 3
        dp[1] = prev[1]
    dp[0] %= MOD
    dp[1] %= MOD

answer = sum(dp)
print(answer%MOD)

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


MOD = 10 ** 9 + 7
L = sr()
dp_dec = 1 
dp_res = 2 
length = len(L)
for i in range(1, length):
    x, y = dp_dec, dp_res
    if L[i] == '1':
        dp_dec = x * 3 + y
        dp_res = y * 2
    else:
        dp_dec = x * 3
        dp_res = y
    dp_dec %= MOD
    dp_res %= MOD

answer = dp_dec + dp_res
print(answer % MOD)

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


MOD = 10 ** 9 + 7
L = sr()
dp_dec = 1 
dp_res = 2 
length = len(L)
for i in range(1, length):
    x, y = dp_dec, dp_res
    if L[i] == '1':
        dp_dec = x * 3 + y
        dp_res = y * 2
    else:
        dp_dec = x * 3
        dp_res = y
    dp_dec %= MOD
    dp_res %= MOD

answer = dp_dec + dp_res
print(answer % MOD)

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


MOD = 10 ** 9 + 7
L = sr()
dp_dec = 1 
dp_res = 2 
length = len(L)
for i in range(1, length):
    x, y = dp_dec, dp_res
    if L[i] == '1':
        dp_dec = x * 3 + y
        dp_res = y * 2
    else:
        dp_dec = x * 3
        dp_res = y

answer = dp_dec + dp_res
print(answer % MOD)

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


MOD = 10 ** 9 + 7
L = sr()
dp_dec = 1 
dp_res = 2 
length = len(L)
for i in range(1, length):
    x, y = dp_dec, dp_res
    if L[i] == '1':
        dp_dec = x * 3 + y
        dp_res = y * 2
    else:
        dp_dec = x * 3
        dp_res = y

answer = dp_dec + dp_res
print(answer % MOD)