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):

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]

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

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

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

S = input()
N = len(S)

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

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

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

Solution (Python):
def main():
    
    MOD = 10**9 + 7
    S = input()
    N = len(S)
    dp = [[0]*2 for i in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        
        if S[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]
            dp[i+1][1] %= MOD
        
        if S[i] == '0':
            dp[i+1][1] += dp[i][1]*2
            dp[i+1][1] %= MOD
        else:
            dp[i+1][0] += dp[i][0]*2
            dp[i+1][0] %= MOD
            dp[i+1][1] += dp[i][1]*2
            dp[i+1][1] %= MOD
    print((dp[N][0]+dp[N][1]) % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
"""
全ての桁でa, b共に0ではない場合を考えれば良い。
"""
mod = 10 ** 9 + 7
L = input()

dp1 = 0
dp2 = 1

for l in L:
    if l == "1":
        dp1 = dp1 * 3 + dp2
        dp2 = dp2 * 2

    else:
        dp1 = dp1 * 3
    dp2 %= mod
    dp1 %= mod

print((dp1 + dp2) % mod)

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

eqDp = 1
lessDp = 0

for l in L:
    if l == '1':
        eqDp, lessDp = eqDp * 2, lessDp * 3 + eqDp
    else:
        eqDp, lessDp = eqDp, lessDp * 3

    eqDp %= MOD
    lessDp %= MOD

print((eqDp + lessDp) % MOD)

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




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

dp[0][0] = 1


for i in range(N):
    for j in range(2):
        
        if int(L[i]): 
            dp[i + 1][1] = (dp[i + 1][1] + dp[i][j]) % MOD
        else: 
            dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % MOD
        
        
        if int(L[i]) or j:
            dp[i+1][j] = (dp[i+1][j] + dp[i][j] * 2) % MOD

print(sum(dp[N]) % MOD)

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

L_ = str(L)


dp = [[0]*2 for j in range(10**5+5)]

dp[0][0] = 1

n = len(L_)
for i in range(n):
    for k in range(2):
        nd = int(L_[i])
        for d in range(2):
            ni = i+1
            nk = k
            if k == 0:
                if d > nd:
                    continue
                elif d < nd:
                    nk = 1
                else:
                    pass
            if d == 0:
                dp[ni][nk] += dp[i][k]%mod
            else:
                dp[ni][nk] += 2*dp[i][k]%mod

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

Solution (Python):
L=input()

MOD = 10**9+7
class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value += Mint.get_value(other)
        if self.value >= MOD: self.value -= MOD
        return self
    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value -= Mint.get_value(other)
        if self.value < 0: self.value += MOD
        return self
    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj
    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self
    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self
    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj
    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj

d0 = Mint(1)
d1 = Mint()
for b in L:
    if b == '0':
        d1 *= (1 + 2)
        
    else:
        d1 = d1 * (1 + 2) + d0
        d0 *= (0 + 2)

print(d0+d1)

Solution (Python):
import sys
input = sys.stdin.readline
L = list(map(int, list(input())[: -1]))
L.reverse()
mod = 10 ** 9 + 7
res = 1
for i in range(len(L)):
  if L[i]: res = (2 * res + pow(3, i, mod)) % mod
print(res)

Solution (Python):
def solve():
    s = input()
    l = list(map(int,s))
    dp = [[0]*2 for _ in range(len(l)+10)]
    dp[0][1] = 1
    
    
    mod = 10**9+7
    for i in range(len(l)):
        if l[i]==1:
            dp[i+1][1]+=dp[i][1]*2
            dp[i+1][0]+=dp[i][0]*2
            dp[i+1][0]+=dp[i][1]
            dp[i+1][0]+=dp[i][0]
            dp[i+1][0]%=mod
            dp[i+1][1]%=mod
        else:
            dp[i+1][1]+=dp[i][1]
            dp[i+1][0]+=dp[i][0]*2
            dp[i+1][0]+=dp[i][0]
            dp[i+1][0]%=mod
    print((dp[len(l)][0]+dp[len(l)][1])%mod)
if __name__ == "__main__":
    solve()

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

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

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

L=input()
l=len(L)
ans=3**(l-1)
a=L.count('1')
cnt=1

for i in range(1,l):
    if L[i]=='1':
        ans+=pow(2,cnt,mod)*pow(3,l-i-1,mod)
        cnt+=1
        
print((ans+pow(2,a,mod))%mod)

Solution (Python):
l = input()
m = 10**9+7
ans = 0
c = 1
while len(l) > 1:
  ans = (ans+c*pow(3,len(l)-1,m))%m
  j = 1
  while l[j] == '0':
    j += 1
    if j == len(l):
      j -= 1
      break
  l = l[j:]
  c = (2*c)%m
ans = (ans+(2*int(l)+1)*c)%m
print(ans)

Solution (Python):
L = input()
n = len(L)

onecnt = 0
ans = 0

MOD = 10 ** 9 + 7

for i in range(n):
    if L[i] == '0':continue
    onecnt += 1
    rest = n - i - 1
    ans += pow(2, onecnt - 1, MOD) * pow(3, rest, MOD) % MOD
    ans %= MOD
ans += pow(2, onecnt, MOD)
print(ans % MOD)

Solution (Python):

import sys

MOD = 1000000007  


def solve(L: str):
    dp = [(0,0)] * (len(L)+1)
    dp[0] = (1,0)
    for i in range(1,len(L)+1):
        isOne = L[i-1] == "1"
        if isOne:
            mContinue = dp[i-1][0]*2%MOD
            mDiscontinue = (dp[i-1][0] + dp[i-1][1]*3)%MOD
            dp[i] = (mContinue,mDiscontinue)
        else:
            mContinue = dp[i-1][0]%MOD
            mDiscontinue = (dp[i-1][1]*3)%MOD
            dp[i] = (mContinue,mDiscontinue)
    print((dp[len(L)][0]+dp[len(L)][1])%MOD)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    L = next(tokens)  
    solve(L)

if __name__ == '__main__':
    main()

Solution (Python):
S = input()
l = len(S)
mod = int(1e9) + 7

'''def saiki(s):
  if s == "0":
    return 1
  elif s == "1":
    return 3
  else:
    if s[0] == '0':
      return saiki(s[1:])
    else:
      SS = 2*saiki(s[1:]) + 3 ** (len(s) - 1)
      return SS'''

cnt = int(S[l-1]) * 2 + 1
base = 3
for i in range(l-1, 0, -1):
  x = int(S[i-1])
  cnt *= x+1
  cnt += base * int(x)
  cnt %= mod
  base *= 3
  base %= mod
print(cnt)

Solution (Python):
S=input()
mod=10**9 + 7
dp=[[0,0,0] for i in range(len(S))]
dp[0][0]=2
dp[0][2]=1

for i in range(1,len(S)):
   if S[i]=="1":
      dp[i][0]+=dp[i-1][0]* 2 % mod  
      dp[i][2]+=dp[i-1][0]* 1 % mod 
   else:
      dp[i][0]+=dp[i-1][0]* 1 % mod 
   dp[i][1]+=(dp[i-1][1]+dp[i-1][2]) * 2 % mod
   dp[i][2]+=(dp[i-1][1]+dp[i-1][2]) * 1 % mod                 
   dp[i][0]%=mod             
   dp[i][1]%=mod
   dp[i][2]%=mod
value=(dp[-1][0]+dp[-1][1]+dp[-1][2])%mod
print(value)

Solution (Python):









import sys



ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    l = input()
    n = len(l)

    dp_small = [0] * n
    dp_indet = [0] * n

    dp_small[0] = 1
    dp_indet[0] = 2

    for i in range(1,n):
        bit = l[i]

        if bit == "1":
            dp_small[i] += dp_small[i-1] * 3 + dp_indet[i-1]
            dp_indet[i] += 2 * dp_indet[i-1]
        else:
            dp_small[i] += dp_small[i-1] * 3
            dp_indet[i] += dp_indet[i-1]

        dp_small[i] %= MOD
        dp_indet[i] %= MOD

    print((dp_small[-1]+dp_indet[-1])% MOD)


if __name__ == '__main__':
    main()

Solution (Python):









import sys



ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    l = input()
    l_len = len(l)

    if l == "1":
        print(3)
        sys.exit()

    
    a1 = pow(3 ,l_len-1, MOD)

    

    a2 = 0
    count = 1

    for i in range(1, l_len-1):
        if l[i] == "1":
            temp1 = pow(2,count,MOD)
            temp2 = pow(3,(l_len-i)-1,MOD)
            a2 += temp1 * temp2
            a2 %= MOD
            count += 1

    if l_len > 1:
        temp1 = pow(2,count,MOD)
        a2 += temp1
        a2 = a2 % MOD
        if l[-1] == "1":
            temp1 *= 2
            temp1 %= MOD
            a2 += temp1
            a2 %= MOD

    ans = (a1+a2) % MOD

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
MOD = 10**9 + 7
L = input()
n = len(L)
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):
b=input()
m=10**9+7

t1,t2=1,2
for c in list(b)[1:]:
  t1*=3
  if c=='1':
    t1+=t2
    t2=(t2*2)%m
  t1%=m

print((t1+t2)%m)

Solution (Python):
import sys
input = sys.stdin.readline
mod = 10**9 + 7
l = input().rstrip()

dp = [[0, 0] for _ in range(len(l))]

for i in range(len(l)):
    s = l[i]
    if i == 0:
        if s == "1":
            dp[i][0] = 2 
            dp[i][1] = 1 
        else:
            dp[i][0] = 1
            dp[i][1] = 0
        continue
    if s == "1":
        dp[i][0] = (dp[i - 1][0] * 2) % mod
        dp[i][1] = (dp[i - 1][0] * 1 + dp[i - 1][1] * 3) % mod
    else:
        dp[i][0] = dp[i - 1][0] * 1
        dp[i][1] = (dp[i - 1][1] * 3) % mod

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

print(ans)

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

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

for i, e in enumerate(l, 1):
    
    if e == "1":
        dp[i][0] += dp[i-1][0] * 3
    else:
        dp[i][0] += dp[i-1][0] * 3
    
    if e == "1":
        dp[i][0] += dp[i-1][1]
    
    if e == "1":
        dp[i][1] += dp[i-1][1] * 2
    else:
        dp[i][1] += dp[i-1][1]

    dp[i][0] %= mod
    dp[i][1] %= mod

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

Solution (Python):
L = input()
dp1 = [0] * 100001 
dp2 = [0] * 100001 
MOD = 10**9 + 7
dp1[0] = 1
for i,d in enumerate(L):
    if int(d) == 1:
        dp1[i+1] = dp1[i]*2 
        dp2[i+1] = dp1[i] + dp2[i]*3 
    if int(d) == 0:
        dp1[i+1] = dp1[i] 
        dp2[i+1] = dp2[i]*3 
    dp1[i+1] %= MOD    
    dp2[i+1] %= MOD    
N = len(L)
ans = dp1[N]+dp2[N]
print(ans%MOD)

Solution (Python):

l = input()
x = len(l)
mod = 10 ** 9 + 7

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

Solution (Python):
L = input()

dp1 = [0 for i in range(len(L))]
dp2 = [0 for i in range(len(L))]

dp1[0] = 2
dp2[0] = 1

mod = 10 ** 9 + 7

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

print((dp1[len(L)-1] + dp2[len(L)-1]) % mod)

Solution (Python):
l = input()

mod = 10**9+7


dplow = [0]*len(l)
dp2 = [0]*len(l)

dplow[0] = 1
dp2[0] = 2

for i in range(1,len(l)):
    dplow[i] += dplow[i-1]*3%mod
    if l[i] == "1":
        dplow[i] += dp2[i-1]%mod
        dp2[i] += dp2[i-1]*2%mod
    else:
        dp2[i] += dp2[i-1] %mod

print((dplow[-1]+dp2[-1])%mod)

Solution (Python):

import sys


L = input()

MOD = 10**9+7


dp = [[0]*2 for _ in range(len(L))]
dp[0][0] = 1
dp[0][1] = 2
for i,l in enumerate(L[1:]):
    dp[i+1][0] = (3*dp[i][0] + int(l)*dp[i][1])%MOD
    dp[i+1][1] = ((1+int(l))*dp[i][1])%MOD
print((dp[-1][0]+dp[-1][1])%MOD)

Solution (Python):
def main():
    MOD = 10 ** 9 + 7
    l = [int(char) for char in input()]

    n = len(l)

    cumsum = []
    tmp = 0
    for number in l:
        if number == 1:
            tmp += 1
        cumsum.append(tmp)
    sel = [pow(2, number, MOD) for number in cumsum]
    sel.append(1)

    def dp(i):
        if l[i] == 0:
            return srs[i-1]
        result = srs[i-1] + sel[i-1] * pow(3, n - 1 - i, MOD)
        result %= MOD
        return result
    
    srs = {-1: 0}
    for i in range(n):
        srs[i] = dp(i)
    
    answer = srs[n-1] + sel[n-1]
    answer %= MOD
    print(answer)


main()

Solution (Python):
from sys import setrecursionlimit

setrecursionlimit(10 ** 8)

def main():
    MOD = 10 ** 9 + 7
    l = [int(char) for char in input()]

    n = len(l)

    cumsum = []
    tmp = 0
    for number in l:
        if number == 1:
            tmp += 1
        cumsum.append(tmp)
    sel = [pow(2, number, MOD) for number in cumsum]
    sel.append(1)

    def dp(i, _cache={-1: 0}):
        if i in _cache:
            return _cache[i]
        if l[i] == 0:
            result = dp(i-1)
            _cache[i] = result
            return result
        result = dp(i-1) + sel[i-1] * pow(3, n - 1 - i, MOD)
        result %= MOD
        _cache[i] = result
        return result
    
    answer = dp(n-1) + sel[n-1]
    answer %= MOD
    print(answer)


main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



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

dp = [[0] * 2 for _ in range(N+1)]
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]
    elif L[i] == '1':
        
        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
    elif L[i] == '1':
        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]) % MOD
print(ans)

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

def main():
    l=input()
    n=len(l)

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

    for i in range(1,n):
        if l[i]=='0':
            dp[i][0] = dp[i-1][0]
            dp[i][1] = 3*dp[i-1][1]
            dp[i][1] %= MOD
        else:
            dp[i][0] = 2*dp[i-1][0]
            dp[i][0] %= MOD
            dp[i][1] = dp[i-1][0] + 3*dp[i-1][1]
            dp[i][1] %= MOD
    
    print(sum(dp[-1])%MOD)
if __name__=='__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

ans = 0


cnt = 0
for i in range(N):
    if L[i] == '1':
        cnt += 1
        ans += pow(3, N - i - 1, MOD) * pow(2, cnt - 1, MOD)
        ans %= MOD

ans += pow(2, cnt, MOD)
ans %= MOD

print(ans)

Solution (Python):
L = input()

result = 1
t = 1
for c in L[::-1]:
    if c == '1':
        result = result * 2 + t
        result %= 1000000007
    t *= 3
    t %= 1000000007
print(result)

Solution (Python):
L = input()

MOD = 10**9 + 7



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

dp[0][0] = 1

for i in range(len(L)):
    for j in range(2):
        
        if int(L[i]):
            dp[i+1][1] += dp[i][j]
            dp[i+1][1] %= MOD
        else:
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= MOD

        
        if int(L[i]) or j:
            dp[i+1][j] += dp[i][j] * 2
            dp[i+1][j] %= MOD

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

Solution (Python):
l = input()
n = len(l)
law = 10 ** 9 + 7
dp = [[0, 0] for _ in range(n)]

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

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

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

dp[0][1] = 1

for i in range(1,len_l+1):
    dp[i][0] += dp[i-1][0] * 3

    if(l[i-1] == '0'):
        dp[i][1] += dp[i-1][1]
    else:
        dp[i][0] += dp[i-1][1]
        dp[i][1] += dp[i-1][1] * 2

    dp[i][0] %= mod
    dp[i][1] %= mod

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

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

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7

l=input()

dp1=[0]*(len(l)+1)
dp2=[0]*(len(l)+1)
dp1[0]=1
for i in range(len(l)):
    if l[i]=="1":
        dp1[i+1]+=dp1[i]*2
        dp2[i+1]+=dp1[i]
        dp2[i+1]+=dp2[i]*3
    else:
        dp1[i+1]+=dp1[i]
        dp2[i+1]+=dp2[i]*3
    dp1[i+1]%=mod
    dp2[i+1]%=mod


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

Solution (Python):
MOD = 1000000007
def power(a, b):
	if b == 0:
		return 1
	elif b == 1:
		return a % MOD
	elif b % 2 == 0:
		return (power(a, b//2) ** 2) % MOD
	else:
		return (power(a, b//2) ** 2 * a) % MOD
 
L = input()
N = len(L)
ans = 0
cou = 0
for i in range(N):
    if L[i] == "1":
        if i == 0:
            ans += (power(3, N-1-i) + 2) * (power(2, cou))
            ans %= MOD
            cou += 1
        else:
            ans += (power(3, N-1-i) + 1) * (power(2, cou))
            ans %= MOD
            cou += 1
print(ans)

Solution (Python):
l = input()
dp = [[0 for j in range(2)] for k in range(len(l)+1)]
dp[0][0] = 1
for i in range(len(l)):
    
    if l[i] == '0':
        dp[i+1][1] = dp[i][1]*2
    else:
        dp[i+1][1] = dp[i][1]*2
        dp[i+1][0] = dp[i][0]*2
    
    
    if l[i] == '0':
        dp[i+1][1] += dp[i][1]
        dp[i+1][0] += dp[i][0]
    else:
        dp[i+1][1] += dp[i][1]+dp[i][0]
        
    dp[i+1][1] %= 10**9+7
    dp[i+1][0] %= 10**9+7
print((dp[len(l)][0]+dp[len(l)][1])%(10**9+7))

Solution (Python):
import time

def pow_k(x, n):
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K = (K*x)%(10**9+7)
        x = (x*x)%(10**9+7)
        n //= 2

    return (K*x)%(10**9+7)

L=input()
N=len(L)


bit=[]
for i in range(0,N):
    if L[N-1-i]=='1':
        bit.append(i+1)

dp=[0 for i in range(0,100001)]

m=bit[0]
if m!=1:
    dp[m]=(2+3**(m-1))%(10**9+7)
else:
    dp[m]=3
time0=time.time()
for i in range(1,len(bit)):
    s=bit[i]
    t=bit[i-1]
    dp[s]=(2*dp[t]+pow_k(3,s-1))
time1=time.time()
print(dp[N]%(10**9+7))

Solution (Python):
L = list(map(int,list(input())))
num = len(L)
mod = 10 ** 9 + 7

dp1 = [0] * num


dp2 = [0] * num



dp1[0] = 1 
dp2[0] = 2 

for i in range(1,num):
    if L[i] == 1:
        dp1[i] = dp1[i-1] * 3 + dp2[i-1]
        dp2[i] = dp2[i-1] * 2
    else:
        dp1[i] = dp1[i-1] * 3
        dp2[i] = dp2[i-1]
    dp1[i] %= mod
    dp2[i] %= mod

print((dp1[num-1] + dp2[num-1])%mod)

Solution (Python):
L = input()


dp1 = [0 for i in range(len(L))]
dp2 = [0 for i in range(len(L))]
mod = 10**9 + 7
dp1[0] = 1 
dp2[0] = 2 

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

Solution (Python):
import sys
input = sys.stdin.readline

def main():
    MOD = 10**9+7
    L = input()
    K = len(L)-1
    
    dp1 = [0] * K
    dp1[0] = 1
    
    dp2 = [0] * K
    dp2[0] = 2
    
    for i in range(1, K):
        if L[i] == '0':
            dp1[i] = dp1[i-1] * 3
            dp2[i] = dp2[i-1]
        
        else:
            dp1[i] = dp1[i-1] * 3
            dp2[i] = dp2[i-1] * 2
            dp1[i] += dp2[i-1]
            
        dp1[i] %= MOD
        dp2[i] %= MOD

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

if __name__ == '__main__':
    main()

Solution (Python):
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
from fractions import gcd
from copy import deepcopy
import math
import queue
import numpy as np

Mod = 1000000007
import sys
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): 
    L = input()
    ans = 1
    p = 1
    for i,b in enumerate(reversed(L)):
        if b == "1":
            ans = ((ans*2%Mod)+p)%Mod
        p = p*3 % Mod
    print(ans)
if __name__ == "__main__":
    main()

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

Solution (Python):
def main():
    L = input().rstrip()
    MOD = 10**9 + 7
    dp = [[0 for equal in range(2)] for digit in range(len(L) + 1)]
    dp[0][0] = 1
    for digit in range(len(L)):
        x = int(L[digit])
        if x == 1:
            dp[digit+1][1] += dp[digit][0] + dp[digit][1]
            dp[digit+1][0] += dp[digit][0] * 2
            dp[digit+1][1] += dp[digit][1] * 2
        else:
            dp[digit+1][0] += dp[digit][0]
            dp[digit+1][1] += dp[digit][1]
            dp[digit+1][1] += dp[digit][1] * 2
        dp[digit+1][0] %= MOD
        dp[digit+1][1] %= MOD
    print((dp[len(L)][0] + dp[len(L)][1])%MOD)

if __name__ == "__main__":
    main()

Solution (Python):
l=input()
mod=10**9+7
n=len(l)
dp1=[1]
dp2=[1]
for i in range(1,n+1):
  dp1.append((dp1[i-1]*3)%mod)
  dp2.append(dp2[i-1])
  if l[n-i]=='1':
    dp2[i]=(dp2[i]*2+dp1[i-1])%mod
print(dp2[n])

Solution (Python):
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

l = ins()
a = l[::-1]
n = len(l)
x = 3 if a[0]=='1' else 1
for i in range(1,n):
    if a[i]=='1':
        x = (2*x+pow(3,i,R))%R
print(x)

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

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

for i in range(N):
    d = int(L[i])
    for j in range(2):
        D = 1 if (d == 1 or j == 1) else 0
        for a, b in [(1, 0), (0, 1), (0, 0)]:
            if a + b <= D:
                here = dp[i + 1][j | (a + b < D)]
                here = (here + dp[i][j]) % MOD
                dp[i + 1][j | (a + b < D)] = here

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

Solution (Python):
import sys


def main():
    L = str(input())
    MOD = 10**9+7
    dpa = [1]
    dpb = [2]
    N = len(L)
    for i in range(1,N):
        if L[i] == "1":
            dpa.append((dpa[-1]*3+dpb[-1])%MOD)
            dpb.append((dpb[-1]*2)%MOD)
        else:
            dpa.append((dpa[-1]*3)%MOD)
            dpb.append((dpb[-1])%MOD)
            
    print((dpa[-1]+dpb[-1])%MOD)

if __name__ == "__main__":
    main()

Solution (Python):
S = input()
N = len(S)
mod = 10**9+7
ans = pow(2, S.count("1"), mod)

a = 0
for i, s in enumerate(S, start=1):
    if s=="1":
        a += 1
        ans += pow(2, a-1, mod)*pow(3, N-i, mod)
        ans %= mod

print(ans%mod)

Solution (Python):
L = str(input())

n = len(L)
MOD = 10**9+7
 
dp = [[0]*2 for i in range(n+1)]
dp[0][0] = 1

for i in range(n):
  for k in range(2):
    nd = int(L[i])
    for d in range(2):
      ni = i+1
      nk = k
      if k == 0:
        if d > nd:
          continue
        elif d < nd:
          nk = 1
        else:
          pass
      if d == 1:
        dp[ni][nk] += (dp[i][k]*2)%MOD
      else:
        dp[ni][nk] += (dp[i][k])%MOD
        

print(sum(dp[-1])%MOD)

Solution (Python):
L = str(input())

n = len(L)
MOD = 10**9+7
 
dp = [[0]*2 for i in range(n+1)]
dp[0][0] = 1

for i in range(n):
  for k in range(2):
    nd = int(L[i])
    for d in range(2):
      ni = i+1
      nk = k
      if k == 0:
        if d > nd:
          continue
        elif d < nd:
          nk = 1
        else:
          pass
      if d == 1:
        dp[ni][nk] += (dp[i][k]*2)%MOD
      else:
        dp[ni][nk] += (dp[i][k])%MOD
        

print(sum(dp[-1])%MOD)

Solution (Python):

s = input()
l = len(s)
cnt = 0
ans = 0
mod = 10**9 + 7
di = [1]
tri = [1]
for _ in range(l):
  di.append(di[-1] * 2 % mod)
  tri.append(tri[-1] * 3 % mod)


for i in range(l):
  if s[i] == '1':
    cnt += 1
    ans += tri[l-1-i] * di[cnt-1]
    ans %= mod
    
ans += di[cnt]
ans %= mod
print(ans)

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


dp = [[0] * 2 for i in range(len(L) + 1)]
dp[0][0] = 1
for i, l in enumerate(L, start=1):
    if l == '0':
        dp[i][0] = dp[i - 1][0]
        dp[i][1] = (3 * dp[i - 1][1]) % MOD
    else:
        dp[i][0] = (2 * dp[i - 1][0]) % MOD
        dp[i][1] = (3 * dp[i - 1][1] + dp[i - 1][0]) % MOD

print(sum(dp[-1]) % MOD)

Solution (Python):
from functools import lru_cache

MOD = 10 ** 9 + 7

s = input()
s = s[::-1]
dp0 = [0] * len(s)
dp1 = [0] * len(s)  
if s[0] == "0":
    dp1[0] = 1
else:
    dp1[0] = 3
dp0[0] = 3

for i in range(1, len(s)):
    if s[i] == "1":
        dp1[i] = dp0[i-1] + dp1[i-1] * 2
    else:
        dp1[i] = dp1[i-1]
    dp0[i] = dp0[i-1] * 3

    dp0[i] %= MOD
    dp1[i] %= MOD

print(dp1[-1])

Solution (Python):
from functools import lru_cache

MOD = 10 ** 9 + 7

s = input()
s = s[::-1]
dp0 = [0] * len(s)
dp1 = [0] * len(s)  
if s[0] == "0":
    dp1[0] = 1
else:
    dp1[0] = 3
dp0[0] = 3

for i in range(1, len(s)):
    if s[i] == "1":
        dp1[i] = dp0[i-1] + dp1[i-1] * 2
    else:
        dp1[i] = dp1[i-1]
    dp0[i] = dp0[i-1] * 3

    dp0[i] %= MOD
    dp1[i] %= MOD

print(dp1[-1])

Solution (Python):
import sys
from functools import lru_cache

sys.setrecursionlimit(1000000000)

MOD = 10 ** 9 + 7

@lru_cache(maxsize=None)
def r(k, smaller):
    global s

    if k == len(s):
        return 1

    if smaller:
        if s[k] == "1":
            return (2 * r(k + 1, True) + r(k + 1, False)) % MOD
        else:
            return r(k + 1, True) % MOD
    else:
        return (3 * r(k + 1, False)) % MOD


s = input()
print(r(0, True))

Solution (Python):
import sys

MOD = 10 ** 9 + 7

s = sys.stdin.readline().rstrip()
l = len(s)

def main():
    dp1 = [0] * (l + 1)
    dp2 = [0] * (l + 1)
    dp2[0] = 1
    for i in range(l):
        dp1[i+1] = dp1[i] * 3
        if s[i] == '1':
            dp1[i+1] += dp2[i]
            dp2[i+1] = dp2[i] * 2
        else:
            dp2[i+1] = dp2[i]
        dp1[i+1] %= MOD
        dp2[i+1] %= MOD

    return (dp1[l] + dp2[l]) % MOD

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
mod = 1000000007
l = input()
n = len(l)
dp1 = [1]
dp2 = [1]
for i in range(1, n + 1):
    dp1.append((dp1[i - 1] * 3) % mod)
    dp2.append(dp2[i - 1])
    if l[n - i] == '1':
        dp2[i] = (dp2[i] * 2 + dp1[i - 1]) % mod
print(dp2[n])