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):
def main():
    MOD = 10 ** 9 + 7
    L = input()
    N = len(L)
    dp = [0 for _ in range(N + 1)]
    dpp = [0 for _ in range(N + 1)]
    dpp[0] = 1
    for n in range(1, N + 1):
        dpp_v = dpp[n - 1]
        d = int(L[n - 1])
        dpp[n] = ((d + 1) * dpp_v) % MOD
        dp[n] = (3 * dp[n - 1] + d * dpp_v) % MOD
    print((dp[N] + dpp[N]) % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
L = input()

m = 1000000007

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

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    L = readline().strip()

    eq, less = 2, 1
    for d in L[1:]:
        if d == '1':
            less = (eq + 3 * less) % MOD
            eq = 2 * eq % MOD
        else:
            less = 3 * less % MOD

    print((eq + less) % MOD)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    L = readline().strip()

    eq, less = 2, 1
    for d in L[1:]:
        if d == '1':
            less = (eq + 3 * less) % MOD
            eq = 2 * eq % MOD
        else:
            less = 3 * less % MOD

    print((eq + less) % MOD)
    return


if __name__ == '__main__':
    main()

Solution (Python):
L=input()

N=len(L)
p=10**9+7


ans1=0
for i in range(1,N):
    now=(2*pow(3, (i-1), p))%p
    ans1+=now
    ans1%=p


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

print((1+ans1+dp[-1]+equals[-1])%p)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    L = input()
    n = len(L)

    res = 0
    cnt = 0
    for i in range(n):
        if L[i] == "1":
            rest = n - (i + 1)
            res += pow(2, cnt, mod) * pow(3, rest, mod) % mod
            res %= mod
            cnt += 1

    res += pow(2, cnt, mod)
    print(res % mod)


def resolve2():
    """
    桁DP
    """
    L = input().rstrip()
    n = len(L)

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

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


if __name__ == '__main__':
    resolve2()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)

f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    L = input()
    n = len(L)

    res = 0
    cnt = 0
    for i in range(n):
        if L[i] == "1":
            rest = n - (i + 1)
            res += pow(2, cnt, mod) * pow(3, rest, mod) % mod
            res %= mod
            cnt += 1

    res += pow(2, cnt, mod)
    print(res % mod)


if __name__ == '__main__':
    resolve()

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

n = len(L)

dp = [[0]*2 for j 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 == 0:
                dp[ni][nk] += dp[i][k]
                dp[ni][nk] %= mod
            else:
                dp[ni][nk] += dp[i][k]*2
                dp[ni][nk] %= mod
print((dp[n][0]+dp[n][1])%mod)

Solution (Python):
def solve():
    L = input()
    N = len(L)
    mod = 10**9+7
    dp = [[0]*2 for _ in range(N+1)]
    dp[0][1] = 1
    for i in range(1,N+1):
        if L[i-1]=='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
    ans = sum(dp[-1])%mod
    return ans
print(solve())

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

S = input()[:-1]
L = len(S)
dp = [[0]*2 for _ in range(L+1)]
dp[0][0] = 1
MOD = 10**9+7

for i in range(L):
    if S[i]=='0':
        dp[i+1][0] = dp[i][0]%MOD
        dp[i+1][1] = 3*dp[i][1]%MOD
    else:
        dp[i+1][0] = 2*dp[i][0]%MOD
        dp[i+1][1] = (dp[i][0]+3*dp[i][1])%MOD
    
print(sum(dp[L])%MOD)

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

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

def main():
    L = list(input())
    N = len(L)
    MOD = 10**9+7


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

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

    for i in range(1,N):
        v = sum([dp[i-1][j][0] for j in range(3)]) % MOD
        dp[i][0][0] += v
        dp[i][1][0] += v
        dp[i][2][0] += v
        for j in range(3):
            u = dp[i-1][j][1] % MOD
            if L[i] == "1":
                dp[i][0][1] += u
                dp[i][1][1] += u
                dp[i][2][0] += u
            else:
                dp[i][2][1] += u

    
    print((sum([dp[N-1][i][0]% MOD for i in range(3)]) + sum([dp[N-1][i][1]% MOD for i in range(3)]))% MOD)



if __name__ == "__main__":
  main()

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

if __name__ == "__main__":
  main()

Solution (Python):
L = list(input())
k = len(L)
mod = 10**9+7
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] = 2*dp1[i]
        dp2[i+1] = dp1[i] + 3*dp2[i]
    else:
        dp1[i+1] = dp1[i]
        dp2[i+1] = 3*dp2[i]
    dp1[i+1] %= mod
    dp2[i+1] %= mod

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

Solution (Python):
L=list(input())
L=list(map(int,L))
dp=[2,1]
MOD=10**9+7
for j in range(1,len(L)):
    a,b=dp
    if L[j]==1:
        dp[0]=(a*2)%MOD
        dp[1]=(a+b*3)%MOD
    elif L[j]==0:
        dp[1]=(b*3)%MOD
print(sum(dp)%MOD)

Solution (Python):
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    L = SI()
    keta = len(L)

    def rec(n):
        if n == 1:
            return 3 if L[keta - n] == "1" else 1

        if L[keta - n] == "1":
            return (pow(3, (n-1), MOD) + rec(n-1) * 2) % MOD
        else:
            return rec(n-1) % MOD

    print(rec(keta))


if __name__ == "__main__":
    main()

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

ans = 1
for i, s in enumerate(reversed(L)):
    if s == '1':
        ans = (2 * ans + pow(3, i, MOD)) % MOD
print(ans)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
mod = 10**9 + 7
l = input()
n = len(l)
dp = [[0, 0] for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
    num = l[i - 1]
    if num == "1":
        dp[i][0] = dp[i - 1][0]*2
        dp[i][1] = dp[i - 1][1]*3 + dp[i - 1][0]
    else:
        dp[i][0] = dp[i - 1][0]
        dp[i][1] = dp[i - 1][1]*3
    dp[i][0] %= mod
    dp[i][1] %= mod
print(sum(dp[-1]) % mod)

Solution (Python):
import sys

def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  

L = LI2()
l = len(L)
mod = 10**9+7

A = []
for i in range(l):
    if L[i] == 1:
        A.append(l-i-1)
A.append(0)

ans = 0
for i in range(len(A)):
    ans += pow(3,A[i],mod)*pow(2,i,mod)
    ans %= mod

print(ans)

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



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

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

Solution (Python):
L = input()
n = len(L)
mod = 1000000007
dp = [[0,0] for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    dp[i+1][1] += 3*dp[i][1]%mod
    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 = list(map(int, input()))
mod = 10 ** 9 + 7

ln = len(l)
dp = [0] * 2
dp[1] = 1

for e in l:
    dp_new = [0] * 2
    
    dp_new[1] += dp[1] * (e + 1)

    
    if e == 1:
        dp_new[0] += dp[1]

    
    dp_new[0] += dp[0] * 3

    dp = dp_new
    for i in range(2):
        dp[i] %= mod

ans = sum(dp) % mod

print(ans)

Solution (Python):
def mempow(a,b,m):
    temp = 1
    yield temp
    for i in range(b):
        temp = temp * a % m
        yield temp

L = open(0).read().split()[0]
m = 1000000007
mem2 = []
mem3 = []
m2append = mem2.append
m3append = mem3.append
for x in mempow(2,L.count('1'),m):
    m2append(x)
for x in mempow(3,len(L)-1,m):
    m3append(x)
ans = mem3[len(L)-1]
appeared = 1
for i in range(1,len(L)):
    if L[i] == '1':
        ans = (ans+mem2[appeared]*mem3[len(L)-i-1]) % m
        appeared += 1
ans = (ans+mem2[appeared]) % m
print(ans)

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

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

for e in l:
    dp_new = [[0] * 2 for _ in range(2)]
    for now in range(2):
        for prev in range(2):
            
            if now == e:
                dp_new[now][1] += dp[prev][1] * (now + 1)

            
            if now == 0 and e == 1:
                dp_new[now][0] += dp[prev][1]

            
            dp_new[now][0] += dp[prev][0] * (now + 1)

    dp = dp_new
    for i in range(2):
        for j in range(2):
            dp[i][j] %= mod

ans = 0
for row in dp:
    ans += sum(row)
    ans %= mod

print(ans)

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

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

for e in l:
    dp_new = [[0] * 2 for _ in range(2)]
    for i in range(2):
        
        if i == e:
            dp_new[i][1] += (dp[0][1] + dp[1][1]) * (1 + i)

        
        if i == 0 and e == 1:
            dp_new[0][0] += dp[0][1] + dp[1][1]

        
        dp_new[i][0] += (dp[0][0] + dp[1][0]) * (1 + i)

    dp = dp_new
    for i in range(2):
        for j in range(2):
            dp[i][j] %= mod

ans = 0
for row in dp:
    ans += sum(row)
    ans %= mod

print(ans)

Solution (Python):
def mempow(a,b,m):
    temp = 1
    yield temp
    for i in range(b):
        temp = temp * a % m
        yield temp

L = input()
m = 1000000007
mem2 = []
mem3 = []
m2append = mem2.append
m3append = mem3.append
for x in mempow(2,L.count('1'),m):
    m2append(x)
for x in mempow(3,len(L)-1,m):
    m3append(x)
ans = mem3[len(L)-1]
appeared = 1
for i in range(1,len(L)):
    if L[i] == '1':
        ans = (ans+mem2[appeared]*mem3[len(L)-i-1]) % m
        appeared += 1
ans = (ans+mem2[appeared]) % m
print(ans)

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

s=input()
n=len(s)

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

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]) % mod

    if s[i] == '0':
        dp[i+1][1] += dp[i][1]*2 % mod
    else:
        dp[i+1][0] += dp[i][0]*2 % mod
        dp[i+1][1] += dp[i][1]*2 % mod

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

Solution (Python):
l = input()

ans = 1
mod = 10**9+7
strict = 1

easy = 0

for i in range(len(l)):
    if l[i] == "1":
        easy *= 3
        easy %= mod

        easy = easy + strict
        
        strict *= 2
        
        
        strict %= mod

    else:
        easy *= 3
        
        
        easy %= mod
    



print((easy+strict)%mod)

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

Solution (Python):
l = input()
mod = 10**9+7
n = len(l)
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]
    else:
        dp[i+1][1] = (dp[i][0]+dp[i][1]) % mod
    
    
    if l[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][1] += dp[i][1]*2
        dp[i+1][0] %= mod
        dp[i+1][1] %= mod

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

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, s in enumerate(L):
  dp[i + 1][0] = dp[i][0] * 2 if int(s) else dp[i][0] 
  dp[i + 1][1] = dp[i][0] if int(s) else 0
  dp[i + 1][1] += dp[i][1] * 3
  dp[i + 1][0] %= MOD
  dp[i + 1][1] %= MOD

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

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
import math
import bisect
def input():
    return sys.stdin.readline()[:-1]

l = input()
mod = 10**9+7
from collections import deque
l = deque(l)

def llo(st):
    if len(st)==1 and st[0]=="0":
        return 1
    elif len(st)==1 and st[0]=="1":
        return 3
    tmp = st.popleft()
    if tmp=="0":
        return llo(st)
    else:
        return (pow(3,len(st),mod) + 2*llo(st))%mod



if "0" not in l:
    print(pow(3,len(l),mod))
else:
    ans = llo(l)
    print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
import math
import bisect
def input():
    return sys.stdin.readline()[:-1]

l = input()
mod = 10**9+7
from collections import deque
l = deque(l)

def llo(st):
    if len(st)==1 and st[0]=="0":
        return 1
    elif len(st)==1 and st[0]=="1":
        return 3
    tmp = st.popleft()
    if tmp=="0":
        return llo(st)
    else:
        return (pow(3,len(st),mod) + 2*llo(st))%mod



if "0" not in l:
    print(pow(3,len(l),mod))
else:
    ans = llo(l)
    print(ans)

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

n = len(l)

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

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

for i in range(1,n):
    dp[i][0] = dp[i-1][0]*3
    if l[i]=='1':
        dp[i][0] += dp[i-1][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[n-1][0]+dp[n-1][1]
print(ans%mod)

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

dp1 = [0 for i in range(len(l))]
dp1[0] = 2

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

Solution (Python):
l=list(input())

MOD=10**9+7






lenl=len(l)

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


dp[0][0]=1

dp[0][1]=2

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

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

Solution (Python):
l = input()[::-1]

mod = 10 ** 9 + 7

pows = [1]
for i in range(10 ** 5 + 10):
    pows.append((pows[-1] * 3) % mod)

dp = 1
for i in range(len(l)):
    if l[i] == '1':
        dp = (pows[i] + dp * 2) % mod
print(dp)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    s = readline().rstrip().decode()
    n = len(s)
    
    P = int(1e9)+7
    dp = [[0, 0] for _ in range(n)]
    
    dp[0][0] = 1 
    dp[0][1] = 2 

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

            dp[i][0] %= P
            dp[i][1] %= P
        else:
            
            dp[i][0] += dp[i-1][0] * 3 
            
            dp[i][1] += dp[i-1][1]  

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

    print((dp[n-1][0]+dp[n-1][1])%P)
if __name__ == '__main__':
    main()

Solution (Python):
MOD = 10**9 + 7
l = input()
dp = [1, 0] 
ndp = [0, 0]

for c in l:
    ndp1 = dp[1] * 3
    if c == '1':
        ndp0 = dp[0] * 2
        ndp1 += dp[0]
    else:
        ndp0 = dp[0]
    dp = ndp0 % MOD, ndp1 % MOD
print(sum(dp) % MOD)

Solution (Python):
L = input()
l = len(L)
mod = 10**9 + 7
ans = 1  

d = dict()


def modpow(x, n, mod):
    if x not in d:
        d[x] = [1]
    l = len(d[x])
    ret = d[x][-1]
    for i in range(l, n+1):
        ret *= x
        ret %= mod
        d[x].append(ret)
    return(d[x][n])


ans = modpow(3, l, mod)

r = 0
count = 0

for i in range(l):
    if L[i] == '0':
        r = modpow(3, l-i-1, mod) * modpow(2, count, mod) * 2
        ans -= r
        ans %= mod
    else:
        count += 1
print(ans)

Solution (Python):


L = input()
ans = 0
mod = 10**9+7
L = L[::-1]
N = len(L)
dp = [0 for i in range(N+10)]

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

Solution (Python):

import sys
sys.setrecursionlimit(200000)

MOD = 1000000007  

def h(L, i):
    return pow(3, len(L)-i, MOD)

def g(L, i):
    if len(L) == i:
        return 1
    if L[i] == '1':
        return ((2 * g(L, i+1)) % MOD + h(L, i+1)) % MOD
    return g(L, i+1)

def solve(L: str):
    return g(L, 0)


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

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

Solution (Python):
from sys import stdin
def main():
    
    readline=stdin.readline
    L=readline().strip()
    n=len(L)
    mod=10**9+7

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

    print((dpF[n]+dpT[n])%mod)

if __name__=="__main__":
    main()

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

s = str(input())

dp0 = [0] * (len(s)+1)
dp1 = [0] * (len(s)+1)
dp0[0] = 1

for i in range(1,len(s)+1):
    if s[i-1] == "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

answer = dp0[-1] + dp1[-1]
if answer >= MOD:
    answer -= MOD
print(answer)

Solution (Python):

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

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

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

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

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

Solution (Python):

import sys
try:
    from typing import List
except ImportError:
    pass

MOD = 1000000007  


def solve(L: str):
    a = 1
    b = 1
    for Li in L:
        if Li == "1":
            a *= 3
            a %= MOD
            b *= 2
            b %= MOD
        else:
            a += (a - b) * 2
            a %= MOD
    print(a)


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):
l=input()[::-1]
ans=1
mod=10**9+7
for i in range(len(l)):
  if l[i]=="1":
    ans=((ans*2)+pow(3,i,mod))%mod
print(ans)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    L = SI()
    b = 1
    ans = 1
    for s in L[-1::-1]:
        if s == '1':
            ans = (ans*2 + b) % MOD
        b = (b * 3) % MOD
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    L = SI()
    n = len(L)
    b = 1
    ans = 1
    for i in range(len(L)):
        if L[n-i-1] == '1':
            ans = (ans*2 + b) % MOD
        b = (b * 3) % MOD
    print((ans)%MOD)

if __name__ == '__main__':
    main()

Solution (Python):
l = list(map(int, list(input())))
n = len(l) + 1
MOD = 10**9+7
dp1 = [0 for _ in range(n)]
dp2 = [0 for _ in range(n)]
dp1[0] = 1
for i in range(1, n):
    if l[i-1] == 1:
        dp1[i] = dp1[i-1] * 2
        dp2[i] = dp1[i-1] + dp2[i-1] * 3
    else:
        dp1[i] = dp1[i-1]
        dp2[i] = dp2[i-1] * 3
    dp1[i] %= MOD
    dp2[i] %= MOD
print((dp1[-1] + dp2[-1]) % MOD)

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

ans = 0
t1 = 0
for i in range(ll):
    if l[i] == "0":
        continue
    ans = (ans+pow(2,t1,mod)*pow(3,ll-i-1,mod)%mod)%mod
    t1 += 1

ans = (ans+pow(2,t1,mod))%mod

print(ans)

Solution (Python):
L=list(map(int,input()))
n=len(L)
def power(a,n):
    x=1
    L=list(format(n,'b'))
    l=len(L)
    for i in range(l):
        if int(L[l-i-1])==1:        
            x=(x*a)%(10**9+7)
        a=(a*a)%(10**9+7)
    return x
X=power(3,n-1)%(10**9+7)
count=1
for i in range(1,n):
    if L[i]==1:
        k=n-i-1
        count+=1
        X+=(power(3,k)%(10**9+7))*(power(2,count-1)%(10**9+7))
X+=power(2,count)%(10**9+7)
print(X%(10**9+7))

Solution (Python):
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()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def modpow(a, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res


def main():
    L = input()
    N = len(L)
    
    dp_1 = [0] * N
    
    dp_2 = [0] * N

    dp_1[0] = 1
    dp_2[0] = 2

    for i in range(1, N):
        if L[i] == "1":
            
            dp_2[i] = dp_2[i - 1] * 2

            dp_1[i] = dp_2[i - 1] + dp_1[i - 1] * 3

            dp_2[i] %= MOD
            dp_1[i] %= MOD
        else:
            
            dp_2[i] = dp_2[i - 1]

            dp_1[i] = dp_1[i - 1] * 3

            dp_2[i] %= MOD
            dp_1[i] %= MOD

    ans = dp_1[-1] + dp_2[-1]
    ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
"""
愚直に考えると、
・aを0 ~ Lの範囲まで見る
・各aについてbを0 ~ Lまで動かして、a xor b = a + b　であれば答えに＋１する。
a,b が 2**(100001)までなので、正確なオーダーは知らんが非常に大きく、O(?^2)で到底間に合わない。

無駄な部分として、(a,b)の組で成立するなら(b,a)も可能、みたいなものもあるが、
xor の特徴として
・加算と異なり桁上がりがない
という点を考えてみると、
・a,bの互いの各bitについて両方では1が立っていない（一方のみ１が立ってる or 両方0）
のものを探せばいいことが分かる。
で、a + b <= L みたいな条件（XXX以下の数字について条件を満たす～のような縛り）があるときは桁DPがつかえることがままある

dp[i+1][j] 
→　Lの左からi桁目まで見たときに、問題文の条件を満たすa,bの組の数。
　 jは a xor b (a+b でもある) のi桁目までが、Lのi桁目までより厳密に小さい（j = 1）か否か(j = 0)

遷移

dp[i][1] -> dp[i+1][1] : i-1桁まででa+bがLより小さいことが確定していれば、i桁目は何にしてもよいので、L[i]と ai+biが同じになるように遷移
dp[i][0] -> dp[i+1][1] : i-1桁まででa+bがLより小さいことが確定しておらず、i桁目で小さくなる。L[i] = 1 の場合のみOK
dp[i][0] -> dp[i+1][0] : i-1桁まででa+bがLより小さいことが確定しておらず、i桁目も同じ


"""


L = input()
N = len(str(L))
dp = [[0 for _ in range(2)] for _ in range(N+1)]
dp[0][0] = 1
MOD = 10**9 + 7

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

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


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

Solution (Python):
L = input()
l = len(L)
dp = [[0]*2 for _ in range(100005)]



dp[0][0] = 1
mod = 10**9+7

for i in range(l):
  n = L[i]
  
  if n == "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 n == "0": 
    dp[i+1][1] += dp[i][1] * 2 % mod
  else: 
    dp[i+1][0] += dp[i][0] * 2 % mod
    dp[i+1][1] += dp[i][1] * 2 % mod

print((dp[l][0]+dp[l][1])%mod)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)


INF = float("inf")
MOD = 10 ** 9 + 7

s = input().strip()

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

n = len(s)
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]) % MOD

    if s[i] == "0":
        dp[i + 1][1] += dp[i][1] * 2 % MOD
    else:
        dp[i + 1][0] += dp[i][0] * 2 % MOD
        dp[i + 1][1] += dp[i][1] * 2 % MOD

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

Solution (Python):
def main():
    L = list(map(int,list(input())))
    MOD = 10 ** 9 + 7
    dp = [[0] * 2 for _ in range(len(L) + 5)]
    dp[0][0] = 1
    for i in range(len(L)):
        if L[i] == 0:
            dp[i+1][1] = 3 * dp[i][1]
            dp[i+1][0] = dp[i][0]
        else:
            dp[i+1][0] = 2 * dp[i][0]
            dp[i+1][1] = 3 * dp[i][1] + dp[i][0]

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

    print((dp[len(L)][0] + dp[len(L)][1]) % MOD)


if __name__ == "__main__":
    main()

Solution (Python):
def powmod(x, n,mod):
  if n == 0:
   return 1
  K = 1
  while n > 1:
   if n % 2 != 0:
    K = K * x%mod
    x = x ** 2%mod
    n = (n - 1) // 2
   else:
    x = x ** 2%mod
    n = n // 2%mod

  return K * x 
L=input()
S=len(L)-1
if S==0:
 print(3)
else:
 ans=1
 ct=0
 for i in range(S+1):
  if int(L[i])==1:
   ans+=((powmod(3, S-i,10**9+7)+1)*powmod(2, ct,10**9+7))%(10**9+7)
   ans%=(10**9+7)
   ct+=1
 print(ans)

Solution (Python):
def powmod(x, n,mod):
  if n == 0:
   return 1
  K = 1
  while n > 1:
   if n % 2 != 0:
    K = K * x%mod
    x = x ** 2%mod
    n = (n - 1) // 2
   else:
    x = x ** 2%mod
    n = n // 2%mod

  return K * x 
L=input()
S=len(L)-1
if S==0:
 print(3)
else:
 ans=1
 ct=0
 for i in range(S+1):
  if int(L[i])==1:
   ans+=((powmod(3, S-i,10**9+7)+1)*powmod(2, ct,10**9+7))%(10**9+7)
   ans%=(10**9+7)
   ct+=1
 print(ans)

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

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

ans = pow(3,L,mod)
cnt = 0
for i,li in enumerate(l):
  if li == '0':
    ans -= pow(3,L-1-i,mod)*pow(2,cnt+1,mod)
    ans %= mod
  else:
    cnt += 1
    
print(ans%mod)

Solution (Python):
MOD=10**9+7
L=input()
N=len(L)
ans,lbit=0,0
for i in range(N):
    if L[i]=='0':
        continue
    ans=(ans+(pow(3,N-i-1,MOD)*pow(2,lbit,MOD)%MOD))%MOD
    lbit+=1
print((ans+pow(2,lbit,MOD))%MOD)

Solution (Python):

import sys

sys.setrecursionlimit(10 ** 7)


INF = float("inf")
MOD = 10 ** 9 + 7

s = input().strip()

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

n = len(s)
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]) % MOD

    if s[i] == "0":
        dp[i + 1][1] += dp[i][1] * 2 % MOD
    else:
        dp[i + 1][0] += dp[i][0] * 2 % MOD
        dp[i + 1][1] += dp[i][1] * 2 % MOD

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

Solution (Python):
L   = list(input())
dp  = [[0 for _ in range(2)] for _ in range(100005)]
MOD = 10**9+7

dp[0][0] = 1

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

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

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

if __name__ == "__main__":
    main()

Solution (Python):
MOD = 10 ** 9 + 7
L = input()
N = len(L)
p3 = [1] * N
for i in range(1, N):
    p3[i] = p3[i - 1] * 3 % MOD
p2 = 1
total = 0
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)