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():
    class int_mod:
        def __init__(self,value,mod=10**9+7):
            if value>=0:self.value=value%mod
            else:self.value=((value%mod)+mod)%mod
            self.mod=mod
        def __lt__(self,other):
            if type(other) is int:return self.value<other
            else:return self.value<other.value
        def __le__(self,other):
            if type(other) is int:return self.value<=other
            else:return self.value<other.value
        def __eq__(self,other):
            if type(other) is int:return self.value==other
            else:return self.value<other.value
        def __ne__(self,other):
            if type(other) is int:return self.value!=other
            else:return self.value<other.value
        def __gt__(self,other):
            if type(other) is int:return self.value>other
            else:return self.value<other.value
        def __ge__(self,other):
            if type(other) is int:return self.value>=other
            else:return self.value<other.value
        def __add__(self,other):
            if type(other) is int:return self.__class__(self.value+other,self.mod)
            else:return self.__class__(self.value+other.value,self.mod)
        def __radd__(self,other):
            if type(other) is int:return self.__class__(self.value+other,self.mod)
            else:return self.__class__(self.value+other.value,self.mod)
        def __sub__(self,other):
            if type(other) is int:return self.__class__(self.value-other,self.mod)
            else:return self.__class__(self.value-other.value,self.mod)
        def __rsub__(self,other):
            if type(other) is int:return self.__class__(self.value-other,self.mod)
            else:return self.__class__(self.value-other.value,self.mod)
        def __mul__(self,other):
            if type(other) is int:return self.__class__(self.value*other,self.mod)
            else:return self.__class__(self.value*other.value,self.mod)
        def __rmul__(self,other):
            if type(other) is int:return self.__class__(self.value*other,self.mod)
            else:return self.__class__(self.value*other.value,self.mod)
        def __mod__(self,other):
            if type(other) is int:return self.__class__(self.value%other,self.mod)
            else:return self.__class__(self.value%other.value,self.mod)
        def __rmod__(self,other):
            if type(other) is int:return self.__class__(self.value%other,self.mod)
            else:return self.__class__(self.value%other.value,self.mod)
        def __pow__(self,other):
            if type(other) is int:return self.__class__(pow(self.value,other,self.mod),self.mod)
            else:return self.__class__(pow(self.value,other.value,self.mod),self.mod)
        def __rpow__(self,other):
            if type(other) is int:return self.__class__(pow(self.value,other,self.mod),self.mod)
            else:return self.__class__(pow(self.value,other.value,self.mod),self.mod)
        def __floordiv__(self,other):
            if type(other) is int:return self.__class__(self.value*pow(other,self.mod-2,self.mod),self.mod)
            else:return self.__class__(self.value*pow(other.value,self.mod-2,self.mod),self.mod)
        def __rfloordiv__(self,other):
            if type(other) is int:return self.__class__(self.value*pow(other,self.mod-2,self.mod),self.mod)
            else:return self.__class__(self.value*pow(other.value,self.mod-2,self.mod),self.mod)
        def __iadd__(self,other):
            if type(other) is int:self.value=self.value+other
            else:self.value=self.value+other.value
            return self.__class__(self.value,self.mod)
        def __isub__(self,other):
            if type(other) is int:self.value=self.value-other
            else:self.value=self.value-other.value
            return self.__class__(self.value,self.mod)
        def __imul__(self,other):
            if type(other) is int:self.value=self.value*other
            else:self.value=self.value*other.value
            return self.__class__(self.value,self.mod)
        def __imod__(self,other):
            if type(other) is int:self.value=self.value%other
            else:self.value=self.value%other.value
            return self.__class__(self.value,self.mod)
        def __ipow__(self,other):
            if type(other) is int:self.value=pow(self.value,other,self.mod)
            else:self.value=pow(self.value,other.value,self.mod)
            return self.__class__(self.value,self.mod)
        def __ifloordiv__(self,other):
            if type(other) is int:self.value=self.value*pow(other,self.mod-2,self.mod)
            else:self.value=self.value*pow(other.value,self.mod-2,self.mod)
            return self.__class__(self.value,self.mod)
        def __neg__(self):return self.__class__(-self.value,self.mod)
        def __pos__(self):return self.__class__(+self.value,self.mod)
        def __invert__(self):return self.__class__(~self.value,self.mod)
    
    n=input()
    o,h=int_mod(1),int_mod(2)
    for i in range(1,len(n)):
        if n[i]=="1":
            o=3*o+h
            h*=2
        else:
            o*=3
    print((o+h).value)
main()

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

dp = [[0,0] for i in range(n+1)]
mod = 10**9 + 7
dp[0][0] = 1

for i in range(n):

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

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

Solution (Python):
L = input()
MOD = 10**9 + 7
now = 1
ans = 1
for b in L[:: -1]:
    if b == '1':
        ans = (ans * 2 + now) % MOD
    else:
        ans = ans % MOD
    now = now * 3 % MOD
print(ans % MOD)

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

dpAll = [0] * (N + 1)
dpLess = [0] * (N + 1)

dpAll[0] = 1
dpLess[0] = 1

for d, b in enumerate(L[:: -1], start=1):
    dpAll[d] = dpAll[d - 1] * 3
    if b == '1':
        dpLess[d] = dpLess[d - 1] * 2 + dpAll[d - 1]
    else:
        dpLess[d] = dpLess[d - 1]
    dpAll[d] %= MOD
    dpLess[d] %= MOD

print(dpLess[N] % MOD)

Solution (Python):
L=list(map(int,list(input())))
n=len(L)
mod=10**9+7
table=[None]*n
table[0]=1
for i in range(1,n):
    table[i]=3*table[i-1]%mod
ans=0
k=1
for i in range(n):
    if L[i]==1:
        ans=(ans+k*table[n-i-1])%mod
        k=k*2%mod
ans+=k    
print(ans%mod)

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

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
sys.setrecursionlimit(1000000)
MOD = 10**9 + 7

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

main()

Solution (Python):

L = input()

n = 1
a = 0

for i in L:

    on = n
    oa = a

    if i == "0":
        n = on
        a = 3 * oa

    else:
        n = on * 2
        a = 3 * oa + on

    a %= 10 ** 9 + 7
    n %= 10 ** 9 + 7

print ((a+n) % (10 ** 9 + 7))

Solution (Python):
l = int(input())
a = list(str(l))
n = len(a)
mod = 10**9 + 7
san = [1]
for i in range(n-1):
    san.append((san[i]*3)%mod)
ans = san[-1]
count = 1
for i in range(1,n):
    if a[i] == "1":
        count *= 2
        count %= mod
        ans += (count*san[-(i+1)])%mod
        ans %= mod
ans = (ans+count*2)%mod
print(ans)

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


def f(index, l):
    if index == len(l):
        return 1
    if l[index] == '1':
        return ( pow(3, len(l)-1-index, MOD) + 2 * f(index+1, l) ) % MOD
    else:
        return f(index+1, l) % MOD


def main():
    l = input()
    print(f(0, l))


main()

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


def f(index, l):
    if index == len(l):
        return 1
    if l[index] == '1':
        return ( 3 ** (len(l)-1-index) + 2 * f(index+1, l) ) % MOD
    else:
        return f(index+1, l) % MOD


def main():
    l = input()
    n = len(l)
    one = 0
    ans = 0
    for i in range(n):
        if l[i] == '1':
            ans += pow(2, one, MOD) * pow(3, n-1-i, MOD)
            ans %= MOD
            one += 1
    ans += pow(2, one, MOD)
    ans %= MOD
    print(ans)

main()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import product
    L=input()
    dp=[1,0]
    for d in range(len(L)):
        ndp=[0,0]
        Ld=int(L[d])
        for lt,a,b in product(range(2),repeat=3):
            nlt=lt
            if(a==1 and b==1): continue
            if(lt==0 and (a==1 or b==1) and Ld==0): continue
            if(a==0 and b==0 and Ld==1): nlt=1
            ndp[nlt]+=dp[lt]
            ndp[nlt]%=MOD
        dp=ndp
    print(sum(dp)%MOD)
resolve()

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

Solution (Python):
L = str(input())
L = list(L)
N = len(L)
if '0' not in L:
    L = ['0']*(N+1)
    L[0] = '1'
    N += 1
else:
    for i in range(N):
        t = L[N-i-1]
        if t == '0':
            L[N-i-1] = '1'
            break
        else:
            L[N-i-1] = '0'
L = ''.join(L)
dic2 = {}
dic3 = {}
sum = 0
for i in range(N):
    t = L[N-i-1]
    if i == 0:
        dic2[0] = 1
        dic3[0] = 1
    else:
        dic2[i] = (dic2[i-1] * 2)%(10**9+7)
        dic3[i] = (dic3[i-1] * 3)%(10**9+7)
num1 = 0
for i in range(N):
    t = int(L[i])
    if t == 1:
        sum += dic3[N-i-1] * dic2[num1]
        sum = sum % (10**9+7)
        num1 += 1
print(sum)

Solution (Python):


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

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

ans = 0
m2 = 0
m3 = len(l)

for i in range(n):
    m3 -= 1
    if l[i] == "1":
        ans = (ans + M2[m2] * M3[m3]) % mod
        
        m2 += 1
ans = (ans + M2[m2] * M3[m3]) % mod

print(ans)

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

Solution (Python):

mod=1000000007
s=input()
chk=ans=0

for i,j in enumerate(s):
    if j=='0': continue
    chk+=1
    rest=len(s)-i-1
    ans+=pow(2,chk-1,mod) * pow(3,rest,mod) % mod
    ans%=mod
ans+=pow(2,chk,mod)
print(ans%mod)

Solution (Python):
import sys
import itertools
from itertools import accumulate
def main():
    input = sys.stdin.readline
    def inputs():
        return [int(x) for x in input().split()]
    A1= tuple(input())
    dp = [[0]*2 for _ in range(len(A1)+1)]
    dp[0][0]=1
    for i in range(len(A1)):
        if A1[i]=="1":
            dp[i+1][0]=max(dp[i+1][0],dp[i][0]*2)%(10**9+7)
            dp[i+1][1]=max(dp[i+1][1],dp[i][1]*3+dp[i][0])%(10**9+7)
        else:
            dp[i+1][0]=max(dp[i+1][0],dp[i][0])%(10**9+7)
            dp[i+1][1]=max(dp[i+1][1],dp[i][1]*3)%(10**9+7)
    
    print((dp[len(A1)-1][0]+dp[len(A1)-1][1])%(10**9+7))
main()

Solution (Python):

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

Solution (Python):


l = input()
le =len(l)
dp = [[0]*le for _ in range(2)]
mod = 10**9 + 7
dp[0][-1] = 1
dp[1][-1] = int(l[-1])*2
for i in range(2,le+1):
    if int(l[-i])==1:
        dp[1][-i] = 2*(dp[1][-i+1] + dp[0][-i+1])%mod
        dp[0][-i] = pow(3,i-1,mod)
    else:
        dp[1][-i] = 0
        dp[0][-i] = (dp[1][-i+1] + dp[0][-i+1])%mod

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

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


def power_func(a,n,mod=mod):
    bi=str(format(n,"b"))
    res=1
    for i in range(len(bi)):
        res=(res*res) %mod
        if bi[i]=="1":
            res=(res*a) %mod
    return res

N = input()
up = True
M = ''
for l in range(len(N)):
    if up:
        if N[len(N)-l-1] == '0':
            M += '1'
            up = False
        else:
            M += '0'
    else:
        M += N[len(N)-l-1]
if up:
    M += '1'
M = M[::-1]
L = len(M)

c = 0
ans = 0
for l in range(L):
    if int(M[l]) == 1:
        ans += power_func(3, L-l-1) * power_func(2, c) % mod
        c += 1
        ans %= mod

print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from functools import lru_cache

MOD = 10**9 + 7

S = [int(x) for x in readline().rstrip().decode('utf-8')]
LS = len(S)

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

for i,x in enumerate(S,1):
    if x == 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):
MOD = 10 ** 9 + 7
L = list(input())
N = len(L)

dp0 = 0
dp1 = 1
for l in L:
    if l == '0':
        dp0 = (dp0 * 3) % MOD
    else:
        dp0 = (dp0 * 3 + dp1) % MOD
        dp1 = (dp1 * 2) % MOD

print ((dp0 + dp1) % MOD)

Solution (Python):


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

lst = [-1] * N
def calc(x): 
    if x == 0:
        return 1
    tmp_ans = 1
    tmp = 1
    for i in range(1, x):
        tmp = (tmp * (x + 1 - i))//i
        tmp_ans += pow(2, i, MOD) * tmp
        tmp_ans %= MOD

    tmp_ans += pow(2, x, MOD)
    tmp_ans %= MOD
    return tmp_ans

def calc1(x):
    return pow(3, x, MOD)


ans = calc1(N - 1) + 2




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

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    a,b,c = LI()
    ans = 10 ** 5
    ans = min(ans, a + b)
    ans = min(ans, a + c)
    ans = min(ans, c + b)
    print(ans)
    return


def B():
    n = II()
    w = LI()
    ans = inf
    for i in range(n):
        ans = min(ans, abs(sum(w[:i]) - sum(w[i:])))
    print(ans)
    return


def C():
    n, m = LI()
    a = IR(m)+[inf]
    dp = [0] * (n + 3)
    dp[0] = 1
    for i in range(n + 1):
        if a[bisect_left(a, i + 1)] != i + 1:
            dp[i + 1] += dp[i] % mod
        if a[bisect_left(a, i + 2)] != i + 2:
            dp[i + 2] += dp[i] % mod
    print(dp[n] % mod)
    return


def D():
    h, w = LI()
    s = SR(h)
    dp = [[0] * w for _ in range(h)]
    for x in range(w):
        for y in range(h):
            if s[y][x] == ".":
                dp[y][x] += 1
    for y in range(h):
        x = 0
        q = 0
        while 0 <= x < w:
            if s[y][x] == ".":
                dp[y][x] += q
                q += 1
            else:
                q = 0
            x += 1
        x = w - 1
        q = 0
        while 0 <= x < w:
            if s[y][x] == ".":
                dp[y][x] += q
                q += 1
            else:
                q = 0
            x -= 1
    for x in range(w):
        y = 0
        q = 0
        while 0 <= y < h:
            if s[y][x] == ".":
                dp[y][x] += q
                q += 1
            else:
                q = 0
            y += 1
        y = h - 1
        q = 0
        while 0 <= y < h:
            if s[y][x] == ".":
                dp[y][x] += q
                q += 1
            else:
                q = 0
            y -= 1
    print(max(map(lambda x: max(x), dp)))
    return


def E():
    l = S()
    dp = [1, 2]
    for i in range(1,len(l)):
        less = dp[0] % mod
        equal = dp[1] % mod
        if l[i] == "1":
            dp[0] = less * 3 + equal
            dp[1] = equal * 2
        else:
            dp[0] = less * 3
            dp[1] = equal
    print(sum(dp) % mod) 


if __name__ == '__main__':
    E()

Solution (Python):
l=input()
mod=10**9+7
n,m=1,0
for i in l:
    if i=="1":
        m=(m*3+n)%mod
        n=n*2%mod
    else:
        m=m*3%mod
print((n+m)%mod)

Solution (Python):
L=input()
n=len(L)
mod=10**9+7
dp1=[0]*(n+1)
dp2=[0]*(n+1)

dp1[0]=1

for i in range(n):
    if L[i]=='1':
        dp1[i+1]=2*dp1[i]
        dp2[i+1]=dp1[i]+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):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)

from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque












def comb(n, r, mod, comb_list):
    ans = comb_list[n]
    ans *= pow(comb_list[r], mod - 2, mod)
    ans %= mod
    ans *= pow(comb_list[n - r], mod - 2, mod)
    ans %= mod
    return ans


def main():
    data = list(map(int, list(input())))
    length = len(data)
    mod = 10 ** 9 + 7

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

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

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

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





if __name__ == '__main__':
    main()

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

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

Solution (Python):
def solve(string):
    a, b, m = 0, 1, 10**9 + 7
    for l in string:
        a, b = ((3 * a + b) % m, 2 * b % m) if l == "1" else (3 * a % m, b)
    return str((a + b) % m)


if __name__ == '__main__':
    print(solve(input()))

Solution (Python):
def solve(string):
    m = 10**9 + 7
    a, b = 0, 1
    for l in string:
        a, b = ((3 * a + b) % m, 2 * b % m) if l == "1" else (3 * a % m, b)
    return str((a + b) % m)


if __name__ == '__main__':
    print(solve(input()))

Solution (Python):
def solve(string):
    m = 10**9 + 7
    a, b = 0, 1
    for l in string:
        a, b = ((3 * a + b) % m, 2 * b % m) if int(l) else (3 * a % m, b)
    return str((a + b) % m)


if __name__ == '__main__':
    print(solve(input()))

Solution (Python):
def solve(string):
    m = 10**9 + 7
    a, b = 1, 2
    for l in string[1:]:
        a, b = ((3 * a + b) % m, 2 * b % m) if int(l) else (3 * a % m, b)
    return str((a + b) % m)


if __name__ == '__main__':
    print(solve(input()))

Solution (Python):
def solve(string):
    m = 10**9 + 7
    a, b = 1, 2
    for l in string[1:]:
        a, b = ((3 * a + b) % m, (2 * b) % m) if int(l) else (3 * a % m, b)
    return str((a + b) % m)


if __name__ == '__main__':
    print(solve(input()))

Solution (Python):
s=input().strip()
mod=10**9+7
r,l = 1,1
for c in s[::-1]:
    r, l = 3*r % mod, (r+2*l) % mod if int(c) else l
print(l)

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

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

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

for i, b in enumerate(L):
    dp[i + 1][1] += 3 * dp[i][1]
    dp[i + 1][1] %= MOD

    if b == '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

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

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


l = S()
pop_cnt = 0
ans = 0
for i in range(len(l)):
    if l[i] == '1':
        ans = (ans + pow(2, pop_cnt, mod) * pow(3, len(l) - i - 1, mod)) % mod
        pop_cnt += 1
ans = (ans + pow(2, pop_cnt, mod)) % mod


print(ans)

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

pow_3=[1]
for _ in range(2*10**5):
  pow_3.append((pow_3[-1]*3)%MOD)
  
pow_2=[1]
for _ in range(2*10**5):
  pow_2.append((pow_2[-1]*2)%MOD)
  
count = L.count('1')
ans = pow_2[count]

for i in range(len(L)-1,-1,-1):
  if L[i]=='1':
    count -= 1
    m = pow_3[len(L)-i-1]*pow_2[count]
    ans += m
    ans %= MOD
print(ans)

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

S = input()
N = len(S)

ans = 0
cnt = 0
length = N - 1
for s in S:
    if s == '1':
        ans += pow(2, cnt, mod) * pow(3, length, mod)
        ans %= mod
        cnt += 1
    length -= 1
ans += pow(2, cnt, mod)
ans %= mod

print(ans)

Solution (Python):
def main():

    L = input()
    mod = pow(10, 9) + 7
    n = len(L)
    prefix = 0

    pows3 = [1]
    for _ in range(n):
        pows3.append((pows3[-1] * 3) % mod)
    p2 = 1
    ans = 0
    for i in range(n):
        if L[i] == "1":
            ans += (pows3[n-1-i]*p2) % mod
            ans %= mod
            prefix += 1
            p2 *= 2
            p2 %= mod
    ans += p2
    ans %= mod
    return ans

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

Solution (Python):
def main():

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

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

Solution (Python):
L = input()
p = 10 ** 9 + 7
l = len(L)
ones = 0
cnt = 1
two = [1] * l
three = [1] * l
for i in range(1, l):
  two[i] = two[i - 1] * 2 % p
  three[i] = three[i - 1] * 3 % p
for i, b in enumerate(L):
  if b == '1':
    left = two[ones]
    right = (three[l - 1 - i] + 1) % p
    cnt += left * right
    cnt %= p
    ones += 1
print(cnt)

Solution (Python):
L = input()
p = 10 ** 9 + 7
l = len(L)
ones = 0
cnt = 1
two = [1] * l
three = [1] * l
for i in range(1, l):
  two[i] = two[i - 1] * 2 % p
  three[i] = three[i - 1] * 3 % p
for i, b in enumerate(L):
  if b == '1':
    left = two[ones]
    right = (three[l - 1 - i] + 1) % p
    cnt += left * right
    cnt %= p
    ones += 1
print(cnt)

Solution (Python):

s = input()
n = len(s)
mod = 10 ** 9 + 7
left = [1]
stand = [1]
right = [1]
for i in range(1,n):
  right.append(right[-1] * 3 % mod)
  if s[i] == '1':
    left.append(left[-1] * 2 % mod)
    stand.append(1)
  else:
    left.append(left[-1])
    stand.append(0)
right.reverse()
ans = 0
for i in range(n):
  ans += left[i] * right[i] * stand[i]
  ans %= mod



ans += left[-1] * 2
ans %= mod
print(ans)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
from collections import *
from math import atan2, pi
from bisect import *
mod = 10**9+7

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

Solution (Python):
l = input()

dp = [[0, 0]] * len(l)

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

MOD = 1000000007

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

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