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 math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9 + 7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))


def main():
    s = S()
    l = len(s)
    d,p = 0,1
    for c in s:
        if c == '1':
            d,p = (d*3+p) % mod, p*2 % mod
        else:
            d,p = d*3 % mod, p

    return (d+p) % mod


print(main())

Solution (Python):
import sys
sys.setrecursionlimit(2*10**5)



L = input()

MOD = 10**9 + 7




class ModInt:
    def __init__(self, x):
        self.x = x % MOD

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

    __repr__ = __str__

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

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

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

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

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

    def __radd__(self, other):
        return ModInt(other + self.x)

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

    def __rmul__(self, other):
        return ModInt(other * self.x)

    def __rtruediv__(self, other):
        return ModInt(other * pow(self.x, MOD - 2, MOD))

    def __rpow__(self, other):
        return ModInt(pow(other, self.x, MOD))


def f(n):
    return (
        ModInt(1) if n == 0 else
        ModInt(3)**(n - 1) + 2 * f(n - 1) if L[-n] == '1' else
        f(n - 1)
    )


ans = f(len(L))


print(ans)

Solution (Python):
l=list(input())
n,m=len(l),1000000007
dp=[[0,1]]+[[0,0] for i in range(n)]
for i in range(n):
	dp[i+1][0] += dp[i][0]*3
	if int(l[i]):
		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] %= m
	dp[i+1][1] %= m
print((dp[n][0]+dp[n][1])%m)

Solution (Python):
import sys
sys.setrecursionlimit(100010)

l = input()
dpf = [1] * (len(l) + 1)
mod = 1000000007
for i in range(len(l)-1, -1, -1):
    dpf[i] = (3 * dpf[i+1]) % mod

def dfs(i):
    if i == len(l):
        return 1
    if l[i] == '0':
        return dfs(i+1)
    return (dpf[i+1] + (dfs(i+1) * 2) % mod) % mod

print(dfs(0))

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

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

print((dp1[N]+dp2[N])%INF)

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

print((dp1[N]+dp2[N])%INF)

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

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


l = lc()

MOD = 10**9 + 7

llen = len(l)

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

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

for i in range(1, llen):
    if l[i] == "0":
        dp[i+1][1] = dp[i][1]
        dp[i+1][0] = 3*dp[i][0]

    else:
        dp[i+1][1] = 2*dp[i][1]
        dp[i+1][0] = 3*dp[i][0] + dp[i][1]

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

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

Solution (Python):

import sys
from operator import itemgetter






















input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())


MOD = 1000000007  

def iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word

if __name__ == '__main__':

    tokens = iterate_tokens()
    L = list(map(int, list(next(tokens))))  
    
    
    
    dp = [[0, 0] for _ in range(100005)]
    dp[0][0] = 1
    
    
    
    for i in range(len(L)):
        
        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[len(L)][0]+dp[len(L)][1])%MOD)

Solution (Python):

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

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


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


def read_float():
    return float(input())


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


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


def read_str_n():
    return list(map(str, input().split()))


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


def mt(f):
    import time

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

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

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(L):
    M = Mod(10**9 + 7)
    dp = [[0] * (len(L)+1) for _ in range(2)]
    dp[0][0] = 1

    for i, l in enumerate(map(int, L)):
        if l == 1:
            dp[0][i+1] = M.mul(dp[0][i], 2)
            dp[1][i+1] = M.add(dp[0][i], M.mul(dp[1][i], 3))
        else:
            dp[0][i+1] = dp[0][i]
            dp[1][i+1] = M.mul(dp[1][i], 3)
    return M.add(dp[0][len(L)], dp[1][len(L)])


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


if __name__ == '__main__':
    main()

Solution (Python):

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

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


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


def read_float():
    return float(input())


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


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


def read_str_n():
    return list(map(str, input().split()))


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


def mt(f):
    import time

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

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

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(L):
    M = Mod(10**9 + 7)
    dp = [[0] * (len(L)+1) for _ in range(2)]
    dp[0][0] = 1
    dp[1][0] = 0

    for i, l in enumerate(map(int, L)):
        if l == 1:
            dp[0][i+1] = M.mul(dp[0][i], 2)
            dp[1][i+1] = M.add(dp[0][i], M.mul(dp[1][i], 3))
        else:
            dp[0][i+1] = dp[0][i]
            dp[1][i+1] = M.mul(dp[1][i], 3)
    return M.add(dp[0][len(L)], dp[1][len(L)])


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


if __name__ == '__main__':
    main()

Solution (Python):

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

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


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


def read_float():
    return float(input())


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


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


def read_str_n():
    return list(map(str, input().split()))


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


def mt(f):
    import time

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

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

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(L):
    M = Mod(10**9 + 7)
    dp = [[0] * (len(L)+1) for _ in range(2)]
    dp[0][0] = 1
    dp[1][0] = 0

    for i, l in enumerate(map(int, L)):
        if l == 1:
            dp[0][i+1] = M.mul(dp[0][i], 2)
            dp[1][i+1] = M.add(M.add(dp[0][i], dp[1][i]), M.mul(dp[1][i], 2))
        else:
            dp[0][i+1] = dp[0][i]
            dp[1][i+1] = M.mul(dp[1][i], 3)
    return M.add(dp[0][len(L)], dp[1][len(L)])


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


if __name__ == '__main__':
    main()

Solution (Python):
l=input()
mod,ans=10**9+7,1
for key,i in enumerate(reversed(l)):
  if i=="1":
    ans=(pow(3,key,mod)+2*ans)%mod
print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

L=input()
N=len(L)


dp=list2d(N+1, 2, 0)

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

    
    
    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):
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]

MOD = int(1e9) + 7
bi = input()
l = len(bi)

dp = makelist(l, 2)
dp[0][0] = 1
dp[0][1] = 2
for i in range(1, l):
    if bi[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]

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

Solution (Python):
l = input()
MOD = 10**9 + 7
lower = {0: 1}
equal = {0: 2}


for i, d in enumerate(l):
    if i == 0:
        continue
    if d == "1":
        lower[i] = (3 * lower[i - 1] + equal[i - 1]) % MOD
        equal[i] = (2 * equal[i - 1]) % MOD
    else:
        lower[i] = (3 * lower[i - 1]) % MOD
        equal[i] = equal[i - 1] % MOD

print((lower[len(l) - 1] + equal[len(l) - 1]) % MOD)

Solution (Python):

import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd

MOD = 1000000007  

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

    for i, c in enumerate(L):
        
        if c == '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 c == '0':
            dp[i+1][1] += dp[i][1]
        else:
            dp[i+1][0] += dp[i][0]
            dp[i+1][1] += dp[i][1]

        
        if c == '0':
            dp[i+1][1] += dp[i][1]
        else:
            dp[i+1][0] += dp[i][0]
            dp[i+1][1] += dp[i][1]

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

    return sum(dp[-1]) % MOD


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    L = next(tokens)  
    result = solve(L)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Solution (Python):
L = input()

MOD = 10**9 + 7

d = [0] * len(L)
in_d = [0] * len(L)

for i in range(len(L)):
    if i == 0:
        d[i] = 1
        in_d[i] = 2
        continue

    
    if L[i] == '1':
        d[i] = (d[i-1]*3 + in_d[i-1]*1) % MOD
        in_d[i] = in_d[i-1]*2 % MOD
    else:
        d[i] = d[i-1]*3 % MOD
        in_d[i] = in_d[i-1]*1 % MOD

d[-1] = (d[-1] + in_d[-1]) % MOD
print(d[-1])

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

print(DP[0][1])

Solution (Python):
l = input()

mod = 10 ** 9 + 7
ans = 1
one = 1
zero = 0
for i in l:
    if i == "1":
        zero = 1 * one + 3 * zero
        one *= 2
        ans = one + zero
    else:
        one = one
        zero = 3 * zero
        ans = one + zero
    one %= mod
    zero %= mod
    ans %= mod
print(ans % mod)

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

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

n = len(L)
for i in range(n):
  if L[i] == "0":
    dp[i + 1][0] = dp[i][0]
    dp[i + 1][1] = dp[i][1]
  else:
    dp[i + 1][1] = (dp[i][0] + dp[i][1]) % MOD

  if L[i] == "0":
    dp[i + 1][1] += dp[i][1] * 2 % MOD
  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 makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]

MOD = 1000000007
def repeatSquares(x, n):  
    res = 1
    while n != 0:
        if n % 2 == 1:
            res *= x
            res %= MOD  
        x *= x
        n //= 2
        x %= MOD      
    return res

bi = input()

ans = 0
l = len(bi)

if l > 1:
    for i in range(2, l+1):
        tmp = repeatSquares(3, l - i)

        ans += tmp * 2
        ans %= MOD
    ans += 1


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

    ans += tmp[-1][0] + tmp[-1][1]
    ans %= MOD
else:
    ans = int(bi) * 2 + 1
    
print(ans)

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

N = len(L)
dp = [[None, None] for _ in range(N+1)]
SMALL, POSBL = 1, 0
dp[0][POSBL] = 1
dp[0][SMALL] = 0

for i in range(1, N+1):
    pp, ps, ss = (2, 1, 3) if L[i-1] == '1' else (1, 0, 3)
    dp[i][POSBL] = (dp[i-1][POSBL] * pp) % MOD
    dp[i][SMALL] = (dp[i-1][SMALL] * ss + dp[i-1][POSBL] * ps) % MOD

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

Solution (Python):
n = int(input(), 2)  + 1
MOD = 10**9 + 7
B = [[3, 0], [1, 2]]
A = [[1, 2], [0, 3]]
ans = [[1, 0], [0, 1]]

while True:
    if n == 1:
        break
    if n % 2 == 1:
        ans = [[(ans[0][0]*A[0][0] + ans[0][1]*A[1][0]) % MOD, (ans[0][0]*A[0][1] + ans[0][1]*A[1][1]) % MOD], \
               [(ans[1][0]*A[0][0] + ans[1][1]*A[1][0]) % MOD, (ans[1][0]*A[0][1] + ans[1][1]*A[1][1]) % MOD]]
        n = (n-1)//2 + 1
    else:
        ans = [[(ans[0][0]*B[0][0] + ans[0][1]*B[1][0]) % MOD, (ans[0][0]*B[0][1] + ans[0][1]*B[1][1]) % MOD], \
               [(ans[1][0]*B[0][0] + ans[1][1]*B[1][0]) % MOD, (ans[1][0]*B[0][1] + ans[1][1]*B[1][1]) % MOD]]
        n = n//2
print(ans[0][0] % MOD)

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

L = input()

lower = 0
just = 1

for b in L:
    lower *= 3
    if b == '1':
        lower += just
        just *= 2
    lower %= MOD
    just %= MOD

print((lower+just)%MOD)

Solution (Python):
MOD = 10**9 + 7
L = input().rstrip()
if L == "1":
    print(3)
    exit()
n = len(L)

ans = 0
l_num = L.count("1")
dp_t = [[0] * n for _ in range(2)]
dp_l = [[0] * n for _ in range(2)]
dp_t[1][0] = 2
dp_l[0][1] = 1
dp_l[1][1] = 2
for i in range(1, n):
    if L[i] == "0":
        dp_t[0][i] += dp_t[0][i-1] + dp_t[1][i-1] 
    elif L[i] == "1":
        dp_t[1][i] += (dp_t[0][i-1] + dp_t[1][i-1]) * 2
        dp_l[0][i] += dp_t[0][i-1] + dp_t[1][i-1]
    dp_l[0][i] += dp_l[0][i-1] + dp_l[1][i-1]
    dp_l[1][i] += (dp_l[0][i-1] + dp_l[1][i-1]) * 2

    dp_l[1][i] %= MOD
    dp_l[0][i] %= MOD
    dp_t[1][i] %= MOD
    dp_t[0][i] %= MOD

print((dp_t[1][n-1] + dp_t[0][n-1] + dp_l[1][n-1] + dp_l[0][n-1]) % MOD)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    L = SI()
    lower = 0
    equal = 1
    for x in L:
        if x == '1':
            lower = (lower * 3 + equal) % MOD
            equal = equal * 2 % MOD
        else:
            lower = lower * 3 % MOD
    ans = (lower + equal) % MOD
    return ans

print(main())

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

Solution (Python):
from itertools import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

L = input()
N = len(L)
dp =[[0]*2 for i in range(N+1)]
dp[0][0] = 1
for i in range(N):
    bit = int(L[i])
    dp[i+1][0] = (dp[i][0]*(1+bit)) % mod
    dp[i+1][1] = (dp[i][0]*(bit)+dp[i][1]*3)%mod

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

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

Solution (Python):
l = input().strip()
MOD = pow(10, 9) + 7
ans = 0
tmp = 0
for ll in range(len(l)):
  if l[ll] == '1':
    ans += pow(2, tmp, MOD) * pow(3, len(l)-ll-1, MOD) % MOD
    tmp += 1

print((ans+pow(2, tmp, MOD))%MOD)

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

Solution (Python):
import sys

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    L = str(input().strip())
    N = len(L)

    ans = pow(3, N, MOD)
    k = 1
    for i, b in enumerate(L, start=1):
        if b == '0':
            sub = k * 2 * pow(3, N-i, MOD) % MOD
            ans = (ans - sub) % MOD
        if b == '1':
            k = k * 2 % MOD
    return ans


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

Solution (Python):




MOD = 1000000007


L = str(input())
dp_known = 0
dp_unknown = 1

for l in L:
  if l=="0":
    dp_known = (dp_known*3) % MOD
  else:
    dp_known = (dp_known*3+dp_unknown) % MOD
    dp_unknown = (dp_unknown*2) % MOD
print((dp_known+dp_unknown) % MOD)

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

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

print((a+b)%MOD)

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

Solution (Python):
import sys

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    L = str(input().strip())
    N = len(L)

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


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

Solution (Python):
def qpow(b,t,m):
  f=format(t,'b')[::-1]
  arr=[b]
  tmp=b
  for i in range(1,len(f)):
    tmp=(tmp**2)%m
    arr.append(tmp)
  ans=1
  for i in range(len(f)):
    if f[i]=='1':
      ans=(ans*arr[i])%m
  return ans    

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

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

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

N = 100010
binL = input().zfill(N)

dp = [[0]*2 for _ in range(N+1)]
dp[0][0] = 1
for i, Li in enumerate(binL):
    Li = int(Li)
    for j in range(2):
        for a, b in [(0,0), (0,1), (1,0)]:
            if j == 0 and a+b > Li: continue
            j2 = j or (a+b<Li)
            dp[i+1][j2] += dp[i][j]
            dp[i+1][j2] %= MOD

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

Solution (Python):
l = input()
l = int(l, 2)
MOD = 10**9+7

dp = [[0 for i in range(2)] for i in range(100001)]
dp[100000][0] = 1


for i in range(99999, -1, -1):
  mask = 1<<i
  num = 0

  if dp[i+1][1]!=-1:
    dp[i][1] = (dp[i][1]+dp[i+1][1]*2)%MOD
    dp[i][1] = (dp[i][1]+dp[i+1][1])%MOD
  if dp[i][0]!=-1:
    if l&mask:
      dp[i][0] = (dp[i][0]+dp[i+1][0]*2)%MOD
      dp[i][1] = (dp[i][1]+dp[i+1][0])%MOD
    else:
      dp[i][0] = (dp[i][0]+dp[i+1][0])%MOD

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

Solution (Python):
l = input()
mod = 10 ** 9 + 7
ans = 1
for key, i in enumerate(reversed(l)):
    if i == "1":
        ans = (pow(3,key,mod) + 2 * ans) % mod
print(ans)

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

Solution (Python):
l = input()
mod = 10 ** 9 + 7
ans = 1
for key, i in enumerate(reversed(l)):
    if i == "1":
        ans = (pow(3,key,mod) % mod + 2 * ans) % mod
print(ans)

Solution (Python):

from sys import stdin




def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


MOD = 10**9 + 7
L = _s()

ans = 3**(len(L) - 1) % MOD



sumL = L.count('1')
ans = (ans + 2**(sumL) % MOD) % MOD

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

print(int(ans))

Solution (Python):
l = reversed(list(input()))
mod = 10 ** 9 + 7
ans = 1
for key, i in enumerate(l):
    if i == "1":
        ans = (pow(3,key,mod) % mod + 2 * ans) % mod
print(ans)

Solution (Python):
l=input()
n=len(l)
Mod=10**9+7
ans=0
count=1
for i in range(n):
    if l[i]=='1':
        ans=(ans+count*pow(3,n-1-i,Mod))%Mod
        count=(count*2)%Mod
ans=ans+count
print(ans%Mod)

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

dp = [(0, 1)]
if not len(L) == 1:
    for l in L[1:]:
        if l == '0':
            dp0 = (dp[-1][0] * 3 + 1) % MOD
            dp1 = (dp[-1][1]) % MOD
        else:
            dp0 = (dp[-1][0] * 3 + dp[-1][1] + 1) % MOD
            dp1 = (dp[-1][1] * 2) % MOD
        dp.append((dp0, dp1))

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

Solution (Python):
import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input
L = input()
N = len(L)
MOD = 10 ** 9 + 7
bits = [1, 2]
acc = [1, 3]
for _ in range(N):
    nex = bits[-1] * 3 % MOD
    bits.append(nex)
    acc.append((acc[-1] + nex) % MOD)
ans = acc[N-1]
cnt = 1
for i, b in enumerate(L):
    if i == 0:
        continue
    now = N-i-1
    if b == '1':
        ans += acc[now] * pow(2, cnt, MOD) % MOD
        cnt += 1
    ans %= MOD
ans += pow(2, cnt, MOD)
ans %= MOD
print(ans)

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

L = input()
L = L[::-1]
len_L = len(L)
ans = 1
count = 0
array_3 = [1]
for _ in range(len(L)):
    array_3.append((array_3[-1] * 3) % M)
for i, c in enumerate(L):
    if c == "1":
        ans *= 2
        ans += array_3[i]
        ans %= M

print(ans)

Solution (Python):
m=10**9+7;L=input();N=len(L);a=0;o=0
for i in range(N):
 if L[i]=="1":
  a+=(pow(3,N-1-i,m)*pow(2,o,m))%m;a%=m;o+=1
a+=pow(2,o,m);a%=m;print(a)

Solution (Python):

l = input()

mod = 10 ** 9 + 7
ans = 1
one = 1
zero = 0
for i in l:
    if i == "1":
        zero = 1 * one + 3 * zero
        one *= 2
        ans = one + zero
    else:
        one = one
        zero = 3 * zero
        ans = one + zero

print(ans % mod)

Solution (Python):



M = 1000000007


def main():
  a = [int(c) for c in input().strip()][::-1]
  n = [1]
  c = 1

  for _ in range(len(a)):
    n.append((n[-1] * 3) % M)

  for i, v in enumerate(a):
    if v == 1:
      c = (n[i] + c * 2) % M

  print(c)


if __name__ == '__main__':
  main()

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

sys.setrecursionlimit(20000000)
mod = 10**9 + 7
l = [int(i) for i in input()]
ko = [[0,0] for i in range(len(l)+1)]
ko[0][0] = 1
for i in range(len(l)):
        if l[i] == 1:
                ko[i+1][0] = ko[i][0]*2
                ko[i+1][1] = ko[i][1]*3+ko[i][0]
        elif l[i] == 0:
                ko[i+1][1] = ko[i][1]*3
                ko[i+1][0] = ko[i][0]
        ko[i+1][1]%=mod
        ko[i+1][0]%=mod
print(sum(ko[len(l)])%mod)

Solution (Python):

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

Solution (Python):
def main():

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

    cnt = 1
    j = n.count("1")

    for digit, num in enumerate(n[::-1], 1):
        if num == "1":
            j -= 1
            cnt += (pow(3, digit - 1, mod) + 1) * pow(2, j, mod)
            cnt %= mod

    print(cnt)


main()

Solution (Python):
L = list(input())
dp = [[0, 0] for _ in range(len(L))]
dp[0][0] = 2
dp[0][1] = 1

for i in range(len(L)-1):
  if L[i+1] == "1":
    dp[i+1][0] = dp[i][0] * 2
    dp[i+1][1] = dp[i][0] + dp[i][1] * 3
  else:
    dp[i+1][0] = dp[i][0]
    dp[i+1][1] = dp[i][1] * 3
  if i%1000 == 0:
    dp[i+1][0] %= 1000000007
    dp[i+1][1] %= 1000000007
print((dp[len(L)-1][0]+dp[len(L)-1][1])%1000000007)

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