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
input = sys.stdin.readline
sys.setrecursionlimit(10**7)


debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    l = input().rstrip('\n')
    n = len(l)
    
    

    mx = 10**9 + 7
    same = 1 
    diff = 0 

    for i in range(n):
        if l[i] == "1":
            same_tmp = same * 2
            diff_tmp = same * 1 + diff * 3
        else:
            same_tmp = same * 1
            
            diff_tmp = diff * 3
        same = same_tmp % mx
        diff = diff_tmp % mx

        dprint(i, l[i], same, diff)

    print((same + diff) % mx)

solve()

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


def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    
    return [w[0],w[1]]


def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m


L = list(input())
n = len(L)-1



'''
number = 1
many = 0
for i in range(1,n+1):
  if int(L[i]) == 1:
    many += 3**(n-i) * 2**number %div
    number += 1
many += 2**number + 3**n
'''

beki3 = 3**n % mod
many = beki3
beki2 = 2
for i in range(1,n+1):
  beki3 = (beki3%mod)*mod_inv(3,mod)%mod
  if int(L[i]) == 1:
    many += beki3*beki2 %mod
    beki2 = beki2*2 %mod
many += beki2 % mod
print(many%mod)

Solution (Python):
MOD,L,pat1,pat2 = 1000000007,input(),1,0
for i in range(0,len(L)): pat1,pat2 = (pat1*2%MOD,(pat1+pat2*3)%MOD) if L[i] == '1' else (pat1,pat2*3%MOD)
print((pat1+pat2)%MOD)

Solution (Python):
MOD,L,pat1,pat2 = 1000000007,'0'+input(),1,0
for i in range(1, len(L)): pat1, pat2 = (pat1*2%MOD, (pat1+pat2*3)%MOD) if L[i] == '1' else (pat1, pat2*3%MOD)
print((pat1+pat2)%MOD)

Solution (Python):
MOD = 1000000007
L='0'+input()

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

print((pat1+pat2)%MOD)

Solution (Python):
MOD = 1000000007
L='0'+input()

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

print((pat1+pat2)%MOD)

Solution (Python):
L=input()
length=len(L)
inf=10**9+7
a=2
b=1
for i in range(1,len(L)):
	if L[i]=="0":
		b=b*3%inf
		continue
	else:
		b=(b*3+a)%inf
		a=a*2%inf
print((a+b)%inf)

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

Solution (Python):

import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())


N = input()
digits = len(N)
mod = (10**9)+7


DP = [[0]*(digits+1) for _ in range(2)]

DP[1][0] = 1
DP[0][0] = 0


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


print((DP[1][digits] + DP[0][digits]) % mod)

Solution (Python):
L = input()
length = len(L)
a = 2
b = 1
c = 4
for l in L[1:]:
	if l  == '1':
		a = (a * 3) % 1000000007
		b = (b * 3) % 1000000007
		c = (c * 2) % 1000000007
	else:
		a = (a * 3 - c) % 1000000007
		b = (b * 3) % 1000000007
print((a + b)%1000000007)

Solution (Python):
L = list(map(int, input().strip()))

ans = 1
S = 0
mod = 10**9+7
for l in L:
    S += l
    ans = (3*ans - (1 - l)*pow(2, S+1, mod)) % mod

print(ans)

Solution (Python):
from functools import reduce


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


ans = reduce(
    lambda acc, t:
        ModInt(3)**t[0] + 2 * acc if t[1] == '1' else
        acc,
    enumerate(reversed(L)),
    ModInt(1)
)


print(ans)

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

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

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

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

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

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

    dp[i][1] += dp[i - 1][1] * 3 % mod

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

Solution (Python):
n = input()

c = 0
co = 0
nn = len(n)

mmm = [1 for i in range(nn+1)]
mm = [1 for i in range(nn+1)]

for i in range(1,nn+1):
	mmm[i] = mmm[i-1]*2 
	mmm[i] %= (10**9+7)
	mm[i] = mm[i-1]*3 
	mm[i] %= (10**9+7)


for i in range(0,nn):
	if n[i] == "1":
		co += (mm[nn - i - 1])*(mmm[c])
		co %=  (10**9+7)
		c += 1
print((co + mmm[c])%(10**9+7))

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

Solution (Python):
L = input()
n = 1
p = (1, 0)  
mod = 10 ** 9 + 7

for i in range(len(L)):
    if L[len(L) - 1 - i] == '1':
        k = (p[0] * (3 ** (i - p[1]))) % mod
        n = (n * 2 + k) % mod
        p = (k, i)

print(n)

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

L = input()
n = 1
p = (1, 0)  
mod = 10 ** 9 + 7

for i in range(len(L)):
    if L[len(L) - 1 - i] == '1':
        k = (p[0] * (3 ** (i - p[1]))) % mod
        n = n * 2 + k
        n %= mod
        p = (k, i)

print(n)

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

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

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

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

Solution (Python):
L=input()
length=len(L)
inf=10**9+7
a=2
b=1
for i in range(1,len(L)):
	if L[i]=="0":
		b=b*3%inf
		continue
	else:
		b=(b*3+a)%inf
		a=a*2%inf
print((a+b)%inf)

Solution (Python):
l=input()
n=len(l)
mod=1000000007
dp=[0]*n
dp[0]=2
ans=[0]*n
ans[0]=1
for i in range(1,n):
  if l[i]=='0':
    dp[i]=(dp[i-1])%mod
    ans[i]=(ans[i-1]*3)%mod
  else:
    dp[i]=(dp[i-1]*2)%mod
    ans[i]=(ans[i-1]*3+dp[i-1])%mod
print((ans[n-1]+dp[n-1])%mod)

Solution (Python):
import sys
import numpy as np
MOD = 1000000007


def main():
    bits = input()
    ans = 1
    pow3 = 1
    for i, b in enumerate(reversed(bits)):
        if b == '1':
            ans = ((ans * 2 % MOD) + pow3) % MOD
        pow3 = (pow3 * 3) % MOD
    print(ans)


main()

Solution (Python):
L = input()
MOD = 10 ** 9 + 7
n = len(L)
sl = set(range(n))
dp = [[0] * (n + 1) for _ in range(2)]
dp[0][0] = 1
for i in range(n):
    if L[i] == '1':
        dp[0][i + 1] = dp[0][i] * 2
        dp[1][i + 1] = dp[1][i] * 3 + dp[0][i]
    elif L[i] == '0':
        dp[0][i + 1] = dp[0][i]
        dp[1][i + 1] = dp[1][i] * 3
    dp[0][i + 1] %= MOD
    dp[1][i + 1] %= MOD
ans = (dp[0][-1] + dp[1][-1]) % MOD
print(ans)

Solution (Python):
import sys

from collections import deque

from collections import defaultdict

import heapq

import bisect





s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    
    S = i2s()
    N = len(S)
    MOD = int(1e+9) + 7
    dp1 = [0] * (N+1)  
    dp2 = [0] * (N+1)  
    dp1[0] = 1
    for i, s in enumerate(S):
        n11 = dp1[i]
        n12 = dp2[i]
        n21 = 0
        n22 = 0
        if s == '0':
            n21 += n11  
            n22 += n12 * 3  
        else:
            
            
            
            n21 += n11 * 2
            n22 += n11 * 1 + n12 * 3
        dp1[i+1] = n21 % MOD
        dp2[i+1] = n22 % MOD
    n = (dp1[N] + dp2[N]) % MOD
    print(n)

main()

Solution (Python):

submit=True
MOD=(10**9)+7
if submit:
    L=raw_input()
    
    
    dp=[[0,0] for _ in range(len(L))]

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

    for i,c in enumerate(L):
        if i==0:continue
        if c=='1':
            dp[i][0]=dp[i-1][0]*3 
            dp[i][0]+=dp[i-1][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]*1
        dp[i][0]%=MOD
        dp[i][1]%=MOD
    print((dp[len(L)-1][0]+dp[len(L)-1][1])%MOD)
else:
    ans=0
    L=0b1010
    for a in range(1000):
        for b in range(1000):
            if a+b<=L and a+b==a^b:
                ans+=1
    print(ans)

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

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

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

dp_less = [0 for i in range(0, len(l))]
dp_eq = [0 for i in range(0, len(l))]

dp_eq[0] = 2
dp_less[0] = 1

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

print((dp_eq[-1] + dp_less[-1]) % mod)

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

s = 0
ret = 0
for k, v in enumerate(L) :
    if v == '1' :
        ret += pow(2, s, MOD) * pow(3, N-k-1, MOD)
        ret %= MOD
        s += 1

ret += pow(2, s, MOD)

print(ret % MOD)

Solution (Python):

import copy
import random
import bisect 
import fractions 
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) 

L = str(input())
n = len(L)
dp = [[0,0] for i 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] + dp[i][1]*2) % mod
    else:
        dp[i+1][0] = dp[i][0] * 2 % mod
        dp[i+1][1] = (dp[i][0] + dp[i][1] + dp[i][1]*2) % mod


print(sum(dp[n]) % mod)

Solution (Python):

import copy
import random
import bisect 
import fractions 
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) 

L = str(input())
n = len(L)
dp = [[0,0] for i 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] + dp[i][1]*2) % mod
    else:
        dp[i+1][0] = dp[i][0] * 2 % mod
        dp[i+1][1] = (dp[i][0] + dp[i][1] + dp[i][1]*2) % mod


print(sum(dp[n]) % mod)

Solution (Python):

import copy
import random
import bisect 
import fractions 
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) 

L = str(input())
n = len(L)
dp = [[0,0] for i 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][1] + dp[i][1]*2) % mod
    else:
        dp[i+1][0] = (dp[i+1][0] + dp[i][0]*2) % mod
        dp[i+1][1] = (dp[i+1][1] + dp[i][1]*2) % mod


print(sum(dp[n]) % mod)

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

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

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

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

dp = [[0, 0] for _ in range(100002)]
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):
MOD = int(10 ** 9 + 7)
L = input()
dp1 = [0] * len(L)

dp2 = [0] * len(L)

dp1[0] = 1

dp2[0] = 2
for i, s in enumerate(L):
    if i == 0:
        continue
    
    if s == "1":
        
        dp2[i] = dp2[i - 1] * 2
        
        dp1[i] = dp1[i - 1] * 3 + dp2[i - 1] * 1
    else:
        
        dp2[i] = dp2[i - 1] * 1
        dp1[i] = dp1[i - 1] * 3
    dp1[i] %= MOD
    dp2[i] %= MOD
n = len(L)
print((dp1[n - 1] + dp2[n - 1]) % MOD)

Solution (Python):
s=input()
l=len(s)
ok=0
ng=1
mod=10**9+7
for i in range(l):
  if s[i]=='1':
    ok=(ng+ok*3)%mod
    ng=(ng*2)%mod
  elif s[i]=='0':
    ok=(ok*3)%mod
    ng=ng%mod
print((ok+ng)%mod)

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

print((dp1[n] + dp2[n]) % MOD)

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

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


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

for i in range(1, len(L)):
    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][0] %= mod
    dp[i+1][1] %= mod
print(sum(dp[len(L)]) % mod)

Solution (Python):
a=b=1;M=10**9+7
for i,s in enumerate(input()[::-1]):
 if'0'<s:a=(2*a+b)%M
 b=b*3%M
print(a)

Solution (Python):
a,M=1,10**9+7
for i,s in enumerate(input()[::-1]):
 if'0'<s:a=(2*a+pow(3,i,M))%M
print(a)

Solution (Python):
s=input()
n=len(s)
a=b=0
M=10**9+7
for i in range(n):
  if'0'<s[i]:
    a=(a+pow(2,b,M)*pow(3,n-i-1,M))%M
    b+=1
print((a+pow(2,b,M))%M)

Solution (Python):
def main():
  s=input()
  n=len(s)
  a,b,M=0,1,10**9+7
  p=[1]
  for i in range(n-1):
    p.append(p[i]*3%M)
  for i,t in enumerate(map(int,s)):
    if t:
      a=(a+b*p[~i])%M
      b=b*2%M
  print((a+b)%M)
main()

Solution (Python):
def main():
  s=input()
  n=len(s)
  a,b,M=0,1,10**9+7
  p=[1]
  for i in range(n-1):
    p.append(p[i]*3%M)
  for i,t in enumerate(map(int,s)):
    if t:
      a=(a+b*p[~i])%M
      b=b*2%M
  print((a+b)%M)
main()

Solution (Python):
s=input()
n=len(s)
a=0
b=1
M=10**9+7
for i in range(n):
  if'0'<s[i]:
    a=(a+b*pow(3,n-i-1,M))%M
    b=b*2%M
print((a+b)%M)

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

Solution (Python):
L = input()

def calc(L):
    result = 0
    for i in range(0, L + 1):
        for j in range(0, L - i + 1):
            if i + j == i ^ j:
                result += 1
    return result




M = 10**9+7

def solve(L):
    if L == 0:
        return 1
    result = 1
    t = 0
    for c in L:
        if c == "1":
            t += 1
            result = (result * 3) % M
        else:
            result = (result * 3 - 2 ** t * 2) % M

    return result

print(solve(L))

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


rl = lambda: map(int,input().split())
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7

L = input().rstrip('\n')
N = len(L)

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10**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 sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def calc_comb(zeros, ones, length):
    return (pow(2,ones,MOD) * pow(3,(length - ones - zeros),MOD)) % MOD

def main():
    
    L = SI()

    count_one = 0
    count_zero = 0
    comb = 0
    for char in L:
        if char == '0':
            count_zero += 1
        elif char == '1':
            count_one += 1
            comb += calc_comb(count_zero + 1, count_one -1, len(L))
            comb %= MOD

    comb += calc_comb(count_zero, count_one, len(L))  
    comb %= MOD

    print(comb)

main()

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

just = 1
lower = 0
for x in l:
    if x == '1':
        lower = (lower * 3 + just) % mod
        just = (just * 2) %mod
    else:
        lower = (lower * 3) %mod
        just = just %mod

print((just + lower) %mod)

Solution (Python):
import sys
sys.setrecursionlimit(10**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 sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def calc_comb(zeros, ones, length):
    return (pow(2,ones,MOD) * pow(3,(length - ones - zeros),MOD)) % MOD

def main():
    
    L = SI()

    count_one = 0
    count_zero = 0
    comb = 0
    for char in L:
        if char == '0':
            count_zero += 1
        elif char == '1':
            count_one += 1
            comb += calc_comb(count_zero + 1, count_one -1, len(L))
            comb %= MOD

    comb += calc_comb(count_zero, count_one, len(L))  
    comb %= MOD

    print(comb)

main()

Solution (Python):
words = lambda t : list(map(t, input().split()))

MOD = 10**9 + 7

l = list(input())

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

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



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

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

Solution (Python):
L=input()
mo=10**9+7
def f(n):  
    s=len(n)
    dp=[[0]*2 for _ in range(s+1)]  
    
    dp[0][0]=1
    for i in range(1,s+1):
        d=n[i-1]
        if d=='1':
            dp[i][1]+=dp[i-1][1]*3 + dp[i-1][0]
            dp[i][0]+=dp[i-1][0]*2
        else:
            dp[i][1]+=dp[i-1][1]*3
            dp[i][0]+=dp[i-1][0]
        dp[i][1]%=mo
        dp[i][0]%=mo
    return sum(dp[s])%mo
print(f(L))

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

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

Solution (Python):











import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    L = ST()
    N=len(L)
    
    dp = [[0] * 2 for _ in range(N + 1)]
    dp[0][0] = 1

    for i, s in enumerate(L, start=1):
        
        if s == "0":
            dp[i][1] += dp[i - 1][1]
            dp[i][0] += dp[i - 1][0]
        else:
            dp[i][1] += dp[i - 1][1] + dp[i - 1][0]
        
        
        if s == "1":
            dp[i][1] += dp[i - 1][1] * 2
            dp[i][0] += dp[i - 1][0] * 2
        else:
            dp[i][1] += dp[i - 1][1] * 2
        dp[i][0] %= mod
        dp[i][1] %= mod


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


if __name__ == '__main__':
    main()

Solution (Python):
b = list(reversed(list(input())))

MOD = 10 ** 9 + 7

n = len(b)

if n == 1:
    print(3)
    exit()

dp = [0] * n

dp[n-1] = 2
for i in range(n-2, -1, -1):
    if b[i] == '1':
        dp[i] = ( dp[i+1] * 2 ) % MOD
    else:
        dp[i] = dp[i+1]

dp.append(1)



ans = dp[0]
x = 1

for i in range(n):
    if b[i] == '1':
        ans += x * dp[i+1]
        ans %= MOD
    x = (x * 3) % MOD

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def solve(l):
    for i in range(l,L):
        if S[i] == '1': return (2*solve(i+1) + pow(3,L-1-i,mod)) %mod
    return 1
mod = 10**9+7
S = input()
L = len(S)
print(solve(0))

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9 + 7

def solve(l):
    tmp = 0
    tmpS = ''
    for i in range(l,L):
        if S[i] == '1':
            return (2*solve(i+1) + pow(3,L-1-i,mod))%mod
    else:
        return 1

S = input()
L = len(S)
print(solve(0)%mod)

Solution (Python):
L = input()
waru = 1000000007
lis1 = 1
lis2 = 2
for i in range(1,len(L)):
    if L[i] == "0":
        lis1 = (lis1*3) % waru
        lis2 = lis2 % waru
    elif L[i] == "1":
        lis1 = (lis1*3+lis2) % waru
        lis2 = (lis2*2) % waru

print((lis1+lis2) % waru)

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

if L[-1] == "0":
    OK, NG = 1, 2
else:
    OK, NG = 3, 0

for i in range(len(L)-2, -1, -1):
    if L[i] == "1":
        OK, NG = (3*OK + NG)%MOD, 2*NG%MOD
    else:
        OK, NG = OK%MOD, (2*OK + 3*NG)%MOD

print(OK)

Solution (Python):
def e_sum_equals_xor(L, MOD=10**9 + 7):
    
    num_bit1, ans = 0, 0
    for i in range(len(L)):
        length = len(L) - i - 1
        if L[i] == '1':
            
            
            
            
            
            
            ans += pow(3, length, MOD) * pow(2, num_bit1, MOD)
            num_bit1 += 1
    ans += pow(2, num_bit1, MOD)
    return ans % MOD

L = input()
print(e_sum_equals_xor(L))

Solution (Python):


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

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

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


if __name__ == "__main__":
    solve()

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

Solution (Python):
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

MOD = 10 ** 9 + 7
L = sys.stdin.readline().rstrip()



dp = np.zeros((len(L) + 1, 2), dtype=int)
dp[1][0] = 1  
dp[1][1] = 2  
for i in range(1, len(L)):
    
    dp[i + 1][0] += dp[i][0] * 3
    if L[i] == '1':
        
        dp[i + 1][0] += dp[i][1]
        
        dp[i + 1][1] += dp[i][1] * 2
    elif L[i] == '0':
        
        dp[i + 1][1] += dp[i][1]
    dp[i + 1] %= MOD
print(dp[-1].sum() % MOD)

Solution (Python):
import sys
input = sys.stdin.readline
def solve():
    mod = 10**9+7
    L = input()
    N = len(L)-1
    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):
from functools import reduce


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


ans = reduce(
    lambda acc, t: (
        ModInt(3)**t[0] + 2 * acc if t[1] == '1' else
        acc
    ),
    enumerate(reversed(L)),
    ModInt(1)
)


print(ans)

Solution (Python):
L = input()
dp1 = [0, 1]
dp2 = [0, 2]
for i in range(1, len(L)):
	if L[i] == '0':
		newdp1 = dp1[-1] * 3
		newdp2 = dp2[-1] 
		dp1.append(newdp1%1000000007)
		dp2.append(newdp2%1000000007)
	else:
		newdp1 = dp1[-1] * 3 + dp2[-1]
		newdp2 = dp2[-1] * 2
		dp1.append(newdp1%1000000007)
		dp2.append(newdp2%1000000007)
print((dp1[-1]+dp2[-1])%1000000007)

Solution (Python):

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

dp = [[0, 0] for _ in range(10**5 + 2)]
dp[0][1] = 1
for i in range(n):
    dp[i + 1][0] += dp[i][0] * 3
    if s[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

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

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)