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

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


def resolve():
    L = list(input())
    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[-1][0] + dp[-1][1]) % mod)


if __name__ == '__main__':
    resolve()

Solution (Python):


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

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


res=0
tmp=1
for i in reversed(range(N)):
    if L[N-1-i]=='1':
        res=(res+tmp*pow_k(3,i,p))%p
        tmp=(2*tmp)%p
print((res+tmp)%p)

Solution (Python):
S = input()
C = 10**9+7
T = S[::-1]
N = len(S)
dp = [0]*N
dp[0] = 1+2*(int(T[0]))

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

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

smaller = [0] * N
not_smaller = [0] * N

smaller[0] = 1
not_smaller[0] = 2

for i in range(1, N):
    if L[i] == "1":
        smaller[i] = 3 * smaller[i - 1] + not_smaller[i - 1]
        not_smaller[i] = 2 * not_smaller[i - 1]
    elif L[i] == "0":
        smaller[i] = 3 * smaller[i - 1]
        not_smaller[i] = not_smaller[i - 1]

    smaller[i] %= MOD
    not_smaller[i] %= MOD

ans = (smaller[-1] + not_smaller[-1]) % MOD
print(ans)

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

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

smaller = [0] * N
not_smaller = [0] * N

smaller[0] = 1
not_smaller[0] = 2

for i in range(1, N):
    if L[i] == "1":
        smaller[i] = 3 * smaller[i - 1] + not_smaller[i - 1]
        not_smaller[i] = 2 * not_smaller[i - 1]
    elif L[i] == "0":
        smaller[i] = 3 * smaller[i - 1]
        not_smaller[i] = not_smaller[i - 1]

    smaller[i] %= MOD
    not_smaller[i] %= MOD

ans = (smaller[-1] + not_smaller[-1]) % MOD
print(ans)

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

smaller = [0] * N
not_smaller = [0] * N

smaller[0] = 1
not_smaller[0] = 2

for i in range(1, N):
    if L[i] == "1":
        smaller[i] = 3 * smaller[i - 1] + not_smaller[i - 1]
        not_smaller[i] = 2 * not_smaller[i - 1]
    elif L[i] == "0":
        smaller[i] = 3 * smaller[i - 1]
        not_smaller[i] = not_smaller[i - 1]

    smaller[i] %= MOD
    not_smaller[i] %= MOD

ans = (smaller[-1] + not_smaller[-1]) % MOD
print(ans)

Solution (Python):
L = input()
N = len(L)
MOD = 10**9 + 7
smaller = [0] * N
not_smaller = [0] * N

smaller[0] = 1
not_smaller[0] = 2

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

ans = smaller[-1] + not_smaller[-1]
ans %= MOD
print(ans)

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


ans = 1
three = [1] * (len(L) + 1)
for i in range(len(L)):
  ans *= 3
  ans %= mod
  three[i + 1] = ans
  

x = 1
for i in range(len(L)):
  if L[i] == "0":
    y = x * 2
    
    y *= three[len(L) - i - 1]
    
    
    ans -= y
    ans %= mod
  else:
    x *= 2
    x %= mod
    
print(ans)

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

a=0
b=1
newa=0
newb=0

for i in range(lenl):
    if L[i]=="0":
        a,b=a*3%mod,b%mod
    else:
        a,b=(3*a+b)%mod,2*b%mod
    
print((a+b)%mod)

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] == '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
  dp[i+1][0] %= MOD
  dp[i+1][1] %= MOD

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

Solution (Python):
L = input()
Digit = len(L)
dp = [[0]*2 for _ in range(Digit+1)]
dp[0][0] = 1
mod = 10**9+7

for i in range(Digit):
    next_digit = L[i]
    
    if next_digit == '0':
        
        dp[i+1][0] += dp[i][0]
        

        
        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]%mod
        
        dp[i+1][1] += (3*dp[i][1])%mod
    
    


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

Solution (Python):
import sys
from collections import deque
from functools import lru_cache
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]

def main():
    L = input().strip()
    N = len(L)
    dp = [[0] * (N + 1) for _ in range(2)]
    dp[0][0] = 1
    for i, a in enumerate(L):
        if a == "0":
            dp[0][i + 1] = dp[0][i]
            dp[1][i + 1] = (3 * dp[1][i]) % mod
        else:
            dp[0][i + 1] = (2 * dp[0][i]) % mod
            dp[1][i + 1] = (dp[0][i] + 3 * dp[1][i]) % mod

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys
import itertools

import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


L = input()

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

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

Solution (Python):


import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7
L = readline().decode().rstrip()
S = len(L)











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

for i,l in enumerate(L,1):
    if l == '0':
        dp[i][0] = dp[i-1][0] % MOD
        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):
def pow_mod(x, y, mod=10**9 + 7):
    if y == 0:
        return 1
    res = 1
    for i in range(y.bit_length()):
        if y & (1 << i):
            res *= x
            res %= mod
        x *= x
        x %= mod
    return res


def calc(r):
    if r <= 1:
        return 3
    return pow_mod(3, r-1) * 2

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

count = [0] * (n+1)
for i in range(1, n+1):
    count[i] = calc(i) + count[i-1]

ans = 0
cnt = 0
u = n
for i in range(n):
    u -= 1
    if i == n-1:
        if l[i] == "1":
            ans += 3 * pow_mod(2, cnt) % mod
            ans %= mod
        else:
            ans += pow_mod(2, cnt) % mod
            ans %= mod
        continue
    if l[i] == "1":
        
        ans += count[u] % mod * pow_mod(2, cnt) % mod
        ans %= mod
        
        cnt += 1
        pass
    else:
        pass

print(ans%mod)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
l=list(input())
n=len(l)
p=10**9+7
ans=0
d=0
def f(n,k,q):
    if k==0:
        return 1
    elif k%2==0:
        return ((f(n,k//2,q))**2)%q
    else:
        return (n*f(n,k-1,q))%q

for i in range(n):
    if l[i]=="1":
        x=n-i-1
        ans+=(f(3,x,p)*f(2,d,p))%p
        d+=1
    else:
        continue

ans+=f(2,d,p)
print(ans%p)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
l=list(input())
n=len(l)
p=10**9+7
ans=0
d=0
def f(n,k,q):
    if k==0:
        return 1
    elif k%2==0:
        return ((f(n,k//2,q))**2)%q
    else:
        return (n*f(n,k-1,q))%q

for i in range(n):
    if l[i]=="1":
        x=n-i-1
        ans+=(f(3,x,p)*f(2,d,p))%p
        d+=1
    else:
        continue

ans+=f(2,d,p)
print(ans%p)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
l=list(input())
n=len(l)
p=10**9+7
ans=0
d=0
def f(n,k,q):
    if k==0:
        return 1
    elif k%2==0:
        return ((f(n,k//2,q))**2)%q
    else:
        return (n*f(n,k-1,q))%q

for i in range(n):
    if l[i]=="1":
        x=n-i-1
        ans+=(f(3,x,p)*f(2,d,p))%p
        d+=1
    else:
        continue

ans+=f(2,d,p)
print(ans%p)

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

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

L = input()
n = len(L)

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

Solution (Python):
import sys

L = list(sys.stdin.readline().strip())
mod = 10**9 + 7
ls = len(L)


dp = [[0 for i in (True, False)] for _ in range(ls)]

dp[0][False] = 2
dp[0][True] = 1
 
for i in range(ls-1):
    for j in (True, False):
        if L[i+1] == "1":
            dp[i+1][True] = 3 * dp[i][True] + 1 * dp[i][False]
            dp[i+1][False] = 2 * dp[i][False]
        else:
            dp[i+1][True] = 3 * dp[i][True]
            
            dp[i+1][False] = 1 * dp[i][False]
        dp[i+1][True] %= mod
        dp[i+1][False] %= mod
 
print(sum(dp[ls-1]) % mod)

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


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

a = 1
b = 0

for i in range(N):
    if L[i] == 1:
        b += pow(3,N-i-1,mod)*a
        b %= mod
        a *= 2
        a %= mod

print((a+b) % mod)

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

dp = [[0,0] for i in range(N+1)]
dp[0][0] = 1
for i,a in enumerate(L):
    a = int(a)
    for less in range(2):
        for d in range(2):
            if less==0 and d > a: continue
            nl = int(less or d < a)
            dp[i+1][nl] += dp[i][less] * (d+1)
    dp[i+1][0] %= MOD
    dp[i+1][1] %= MOD

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

Solution (Python):
p = 10**9+7
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x
    if m%2==0:
        return (pow(x,m//2)**2)%p
    else:
        return (x*(pow(x,(m-1)//2)**2)%p)%p
L = list(map(int,list(input().strip())))
N = len(L)
A = []
for i in range(N):
    if L[i]==1:
        A.append(i)
cnt = 0
for i in range(len(A)):
    j = A[i]
    k = i
    n = N-1-j
    cnt = (cnt+pow(2,k)*pow(3,n))%p
cnt = (cnt+pow(2,len(A)))%p
print(cnt)

Solution (Python):
L = str(input());MOD = pow(10,9)+7
N = len(L) 

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



dp[0][1] = 1

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

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

mod = 10**9 + 7

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

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

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

Solution (Python):
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  
def LS2(): return list(sys.stdin.readline().rstrip())  


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

ans = 0
a = 1

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

print((ans+a) % mod)

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

Solution (Python):
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
mod=10**9+7
L = input()
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] = (2+1)*dp1[i-1]+1*dp2[i-1]
        dp2[i]= 2*dp2[i-1]
    elif L[i]=="0":
        dp1[i]=(2+1)*dp1[i-1]
        dp2[i]=dp2[i-1]
    dp1[i]%=mod
    dp2[i]%=mod
print((dp1[n-1]+dp2[n-1])%mod)

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)

INF = 10**18
import bisect
import statistics
mod = 10**9+7


L = input()
n = len(L)
L = "@" + L


dp = [[0,0] for i in range(n+1)]
dp[0][0] = 1

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

Solution (Python):













import sys


readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(L):
    M = 10**9 + 7
    ans = 1
    m = 0
    for b in map(int, L):
        m *= 3
        if b == 1:
            m += ans
            ans *= 2

        ans %= M
        m %= M
    ans += m
    ans %= M
    return ans


def main():
    L = read_str()
    print(slv(L))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys


readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        error_print(e - s, 'sec')
        return ret

    return wrap


def ref(L):
    L = int(L, base=2)
    ans = 0
    for a in range(L+1):
        for b in range(L+1):
            if (a + b <= L) and (a ^ b == a + b):
                
                ans += 1
    return ans



@mt
def slv(L):
    M = 10**9 + 7
    ans = 1
    m = 0
    for b in map(int, L):
        m *= 3
        if b == 1:
            m += ans
            ans *= 2

        ans %= M
        m %= M
    ans += m
    ans %= M
    return ans


def main():
    L = read_str()
    print(slv(L))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys


readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        error_print(e - s, 'sec')
        return ret

    return wrap


def ref(L):
    L = int(L, base=2)
    ans = 0
    for a in range(L+1):
        for b in range(L+1):
            if (a + b <= L) and (a ^ b == a + b):
                
                ans += 1
    return ans



@mt
def slv(L):
    M = 10**9 + 7
    ans = 1
    m = 0
    for b in map(int, L):
        m *= 3
        if b == 1:
            m += ans
            ans *= 2

        ans %= M
        m %= M
    return (m + ans) % M


def main():
    L = read_str()
    print(slv(L))


if __name__ == '__main__':
    main()

Solution (Python):
L = input()
n = len(L)
csum_1 = [0] * n
csum_0 = [0] * n
now1 = 0
now0 = 0
for i in range(n):
    if L[i] == '1':
        now1 += 1
    else:
        now0 += 1
    csum_1[i] = now1
    csum_0[i] = now0

mod = 10**9+7
ans = 0

for i in range(n):
    if L[i] == '1':
        p = 1
        
        if i >= 1:
            p *= pow(2,csum_1[i-1],mod)
        
        
        p *= pow(3,n-i-1,mod)
        
        ans += p
        ans %= mod

p = pow(2,csum_1[-1],mod)

ans = (ans+p)%mod
print(ans)

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

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

L=input()
N = len(L)
ans = 0
num = 0 
cum_one_cnt = [0]*(N+1)
for i in range(N):
    length = N-i-1
    if L[i] == "1":
        ans += pow(3, length, MOD) * pow(2, num, MOD) % MOD
        ans %= MOD
        num += 1 


ans += pow(2, num, MOD)
print(ans%MOD)

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

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

for i in range(len(l)):
  dp[i+1][1]+=(dp[i][1]*3)%mod

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


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

Solution (Python):
"""
桁DPを使う
dp[i][j][k] => 合計値のi桁目がjになるようなABの組み合わせの数。kは未満フラグ
jが1のとき、その桁ではAが1でBが0のパターンと、Aが0でBが1のパターンが考えられる。
したがってdp[i+1][1] += dp[i][j]*2という遷移となる。
jが0のとき、その桁では必ずAもBも0となる。
したがってdp[i+1][0] += dp[i][j]という遷移となる。
"""
mod = 10**9 +7
L = input()
N = len(L)
dp = [[[0]*(2) for _ in range(2)]for _ in range(N)]
dp[0][0][1] = 1
dp[0][1][0] = 2

for i in range(N-1):
    x = int(L[i+1])
    for j in range(2):
        for k in range(2):
            if k == 0:
                r = x+1
            else:
                r = 2
            for l in range(r):
                if k == 0 and l == x:
                    flag = 0
                else:
                    flag = 1
                if l == 0:
                    dp[i+1][l][flag] += dp[i][j][k]
                else:
                    dp[i+1][l][flag] += dp[i][j][k]*2
                dp[i+1][l][flag] %= mod
ans = sum(dp[-1][1])+sum(dp[-1][0])
print(ans%mod)

Solution (Python):
from pprint import pprint

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

for i in range(1, nl + 1):
    li = i - 1

    
    dp[i][1] = dp[i - 1][1] * 3 % MOD

    
    if L[li] == '1':
        dp[i][1] += dp[i - 1][0]  

    
    if L[li] == '1':
        dp[i][0] = dp[i - 1][0] * 2 % MOD  
    else:
        dp[i][0] = dp[i - 1][0]  

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

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

Solution (Python):


L=input()

N=len(L)

dp=[[0 for i in range(2)] for j in range(N)]
dp[0][0]=1
dp[0][1]=2


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



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

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

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

L = input()
N = len(L)

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

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

for i in range(N-1):
    x = int(L[i+1])
    for j in range(2):
        for k in range(2):
            if k == 0:
                r = x+1
            else:
                r = 2
            for l in range(r):
                if k==0 and l==x:
                    f = 0
                else:
                    f = 1
                if l==0:
                    dp[i+1][l][f] += dp[i][j][k]
                else:
                    dp[i+1][l][f] += dp[i][j][k]*2
                dp[i+1][l][f] %= mod
ans = sum(dp[-1][0])+sum(dp[-1][1])
ans %= mod
print(ans)

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

Solution (Python):
import sys

input = sys.stdin.readline
P = 10 ** 9 + 7


def solve(L, N):
    dp = [[0, 0] for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(N):
        n = L[i]
        for j in range(2):
            max_d = 1 if j == 1 else n
            for d in range(max_d + 1):
                next_j = int(j or d < n)
                dp[i + 1][next_j] += (d + 1) * dp[i][j]

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

    return (dp[N][0] + dp[N][1]) % P


def main():
    L = list(map(int, input().rstrip()))

    N = len(L)
    ans = solve(L, N)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline
P = 10 ** 9 + 7


@nb.njit("i8(i8[:],i8)", cache=True)
def solve(L, N):
    dp = np.zeros(shape=(N + 1, 2), dtype=np.int64)
    dp[0][0] = 1
    for i in range(N):
        n = L[i]
        for j in range(2):
            max_d = 1 if j == 1 else n
            for d in range(max_d + 1):
                next_j = int(j or d < n)
                dp[i + 1][next_j] += (d + 1) * dp[i][j]

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

    return (dp[N][0] + dp[N][1]) % P


def main():
    L = np.array(list(map(int, input().rstrip())), dtype=np.int64)

    N = len(L)
    ans = solve(L, N)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
"""
制約がヒントっぽいな。
桁DPで解ける

dp[i][j][k] => 2進数表記でa+bの左からi桁目まで見る。i桁目がjになるような場合の数。kは未満フラグ。配るDPで解く。

"""
L = input()
N = len(L)
mod = 10**9 +7
dp = [[[0]*2 for _ in range(2)]for _ in range(N)]
dp[0][1][0] = 2
for i in range(1,N):
    dp[i][1][1] = 2

for i in range(N-1):
    x = int(L[i+1])
    for j in range(2):
        for k in range(2):
            for l in range(2):
                if not k and l > x:
                    continue
                if k or l < x:
                    nxFlag = 1
                else:
                    nxFlag = 0
                if l == 0:
                    dp[i+1][l][nxFlag] += dp[i][j][k]
                else:
                    dp[i+1][l][nxFlag] += dp[i][j][k]*2
                dp[i+1][l][nxFlag]%=mod
ans = (sum(dp[-1][1])+sum(dp[-1][0])+1)%mod
print(ans)

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

dpT = [0]*N
dpF = [0]*N

dpT[0] = 1
dpF[0] = 2

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

print((dpT[-1]+dpF[-1])%mod)

Solution (Python):
import sys

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

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


mod = 10**9 + 7


def main():
    L = in_s()
    N = len(L)

    dp1 = [0] * N
    dp2 = [0] * N

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

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

    ans = dp1[-1] + dp2[-1]
    ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

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

l = input()
p = len(l)
dp = [[0, 0] for _ in range(p)]
dp[0] = [1, 2]

for i, s in enumerate(l[1:], start = 1):
    if s == "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])
print(ans % MOD)

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

Solution (Python):
mod = 10**9+7
L = input()
l = len(L)
DP = [[0,0] for _ in range(l)] 
DP[0][0] = 2
DP[0][1] = 1
for i in range(1,l):
    if L[i] == '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][0]+DP[i-1][1]*3) % mod
print((DP[l-1][0]+DP[l-1][1]) % mod)

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

if __name__ == "__main__":
    main()

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    L=list(input())
    N=len(L)
    
    
    dpl=[0]*(N+1)
    dpt=[0]*(N+1)
    dpt[0]=1
    
    
    for i in range(N):
        if L[i]=="1":
            dpl[i+1]=(dpl[i]*3+dpt[i])%mod
            dpt[i+1]=(dpt[i]*2)%mod
        else:
            dpl[i+1]=(dpl[i]*3)%mod
            dpt[i+1]=dpt[i]
            
    ans=(dpl[-2]+dpt[-2])%mod
    print(ans)
            
            
            

main()

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



N=[int(i) for i in L]
keta=len(N)
dp=[[0 for i in range(2)] for j in range(keta+1)]
dp[0][0] = 1




for i in range(keta):
    for smaller in [0,1]:
        if 1:
            for x in range(2 if smaller else (N[i]+1)):
                dp[i + 1][smaller | ((x == 0)&(N[i]==1))]+= dp[i][smaller]*(2 if x==1 else 1)
                dp[i + 1][smaller | ((x == 0)&(N[i]==1))] %=mod
print((dp[keta][0]+ dp[keta][1])%mod)