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

MOD = 1000000007  

def powmod(a, n, m):
    L = [1 for _ in range(n+1)]
    for i in range(n):
        L[i+1] = L[i] * a % m
    return L

def solve(L: str):
    p = len(L)
    pm = powmod(3, p, MOD)
    
    res = 1
    for i, c in enumerate(L[::-1]):
        if c == '0':
            res = res
        else:
            res = (pm[i] + res * 2) % MOD
    print(res)
    return



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

if __name__ == '__main__':
    main()

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

Solution (Python):
def getN():
    return int(input())

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

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

n = input()
MOD = 1000000007

dp0 = [0 for i in range(len(n))]
dpsmall = [0 for i in range(len(n))]
dp0[0] = 2
dpsmall[0] = 1

for ii, c in enumerate(n[1:]):
    
    i = ii + 1
    if c == "1":
        dpsmall[i] = (dpsmall[i-1] * 3 + dp0[i-1]) % MOD
        dp0[i] = (dp0[i-1] * 2) % MOD

    else:
        dpsmall[i] = (dpsmall[i-1] * 3 ) %MOD
        dp0[i] = dp0[i-1]

print((dp0[len(n)-1] + dpsmall[len(n)-1]) % MOD)

Solution (Python):
l=input()
deg=len(l)-1
mod=10**9+7
ans=(3**deg)%mod
x=[]
n=len(l)
for i in range(1,n+1):
    if l[-i]=='1':
        x.append(i)
c=len(x)
ans+=2**c
two=(2**c)%mod
three=1
x_ref=1
for i in range(1,c):
    if two%2==0:
        two=two//2
    else:
        two=(two+mod)//2
    three=(three*3**(x[i-1]-x_ref))%mod
    x_ref=x[i-1]
    ans+=(two%mod)*(three%mod)
    ans%=mod
print(ans)

Solution (Python):

import sys

MOD = 1000000007  

def powmod(a, n, m):
    L = [1 for _ in range(n+1)]
    for i in range(n):
        L[i+1] = L[i] * a % m
    return L

def solve(L: str):
    p = len(L)
    pm = powmod(3, p, MOD)
    
    s = ''
    for i, c in enumerate(L[::-1]):
        if i == 0:
            if c == '1':
                res = 3
            else:
                res = 1
            continue
        
        if c == '0':
            res = res
        else:
            res = (pm[i] + res * 2) % MOD
    print(res)
    return



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

if __name__ == '__main__':
    main()

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

L=input().strip()
mod=10**9+7

if L=="1":
    print(3)
    sys.exit()


LEN=len(L)

ANS=pow(3,LEN-1,mod)


count=1
for i in range(1,LEN-1):
    if L[i]=="1":
        ANS=(ANS+pow(2,count,mod)*pow(3,LEN-i-1,mod)%mod)%mod
        count+=1

    

if L[-1]=="1":
    ANS+=pow(2,count,mod)*3
else:
    ANS+=pow(2,count-1,mod)*2
    
print(ANS%mod)

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

L = input().strip()

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

print(count)

Solution (Python):
L = list(input())
MOD = 10**9 + 7
ans = 1
dp = [1 for i in range(len(L))]
pow3 = [1]
lenL = len(L)
lst = 1
for i in range(lenL):
	lst = lst*3 % MOD
	pow3.append(lst)
for i in range(lenL):
	if i == 0:
		if L[lenL-1] == "0":
			dp[i] = 1
		else:
			dp[i] = 3
	else:
		if L[lenL-i-1] == '0':
			dp[i] = dp[i-1]
		else:
			dp[i] = (pow3[i] + 2*dp[i-1]) % MOD
print(dp[lenL-1])

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

L_split = [0]*len(L)
for i in range(len(L)):
    L_split[i] = int(L[len(L)-1-i])
    
ans = 0
if len(L_split) == 1 and L_split[0] == 0:
    print(1)
else:
    count_1 = 0 
    for i in range(len(L_split)-1,-1,-1):
        if L_split[i] == 1:
            ans += pow(2,count_1,mod_num) * pow(3,i,mod_num)
            ans %= mod_num
            
            count_1 += 1
            
ans += pow(2,count_1,mod_num)
ans %= mod_num
print(ans)

Solution (Python):
l=input()
a=len(l)
mod=10**9+7
ans=3**a%mod
t=0
for i,j in enumerate(l,1):
    if(j=="0"):
        ans-=pow(3,a-i,mod)*pow(2,t+1,mod)
    else:
        t+=1
print(ans%(10**9+7))

Solution (Python):
S = input()
MOD = 10 ** 9 + 7
dp = 1

n = 1
for c in reversed(S):
  if c == '1':
    dp = 2 * dp + n
  n *= 3
print(dp % MOD)

Solution (Python):
def inpl(): return list(map(int, input().split()))
L = input()
MOD = 10**9 + 7

OK = [0]*(len(L))
NG = [0]*(len(L))

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):
L = input()
ans = 0
n = len(L)
def power_func(a,n,p):
  bi=str(format(n,"b"))
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

count = 0
for i in range(len(L)):
    if i == 0:
        ans += (power_func(3,n-1,1000000007) + 2)
        ans %= 1000000007
        count += 1
    else:
        if L[i] == "1":
            ans += (power_func(3,n-1,1000000007)+1)*(power_func(2,count,1000000007))
            ans %= 1000000007
            count += 1
    n -= 1
print(ans%1000000007)

Solution (Python):

import sys
INF = float("inf")

MOD = 1000000007  


def solve(L: int):

    if L == 1:
        print(3)
        return

    strL = str(L)

    lesser_count = 1
    over_count = 2
    for i, c in enumerate(strL[1:]):
        lesser_count *= 3
        lesser_count %= MOD
        if c == "1":
            lesser_count += over_count
            lesser_count %= MOD
            over_count *= 2
            over_count %= MOD
    print((lesser_count + over_count) % MOD)

    return


def main():

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


if __name__ == '__main__':
    main()

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


L = input()
n1 = L.count('1')

m=0
d=[]
for i, c in enumerate(reversed(L)):
    if c=='1':
        m+=1
        d.append((i, n1-m))

mod = 10**9+7
s = modpow(2, n1, mod)
for dd in d:
    s += (modpow(3,dd[0],mod) * modpow(2,dd[1],mod)) % mod

print(s % mod)

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

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

N = len(L)

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

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

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

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













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

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

ans = 0
cnt = 0
for i in range(k):
    if l[i] == "1":
        left = pow(2, cnt, mod)
        right = pow(3, (k-i-1), mod)
        ans += left*right % mod
        ans %= mod
        cnt += 1
ans += pow(2, cnt, mod)
ans %= mod
print(ans)

Solution (Python):
def main():
    x = [int(s) for s in input()]
    x = x[::-1]
    print(solve(x))

def solve(x):
    M = 10 ** 9 + 7

    dp1 = [0 for _ in x]
    dp2 = [0 for _ in x]

    dp1[0] = 3
    dp2[0] = 3 if x[0] else 1

    for i in range(1, len(x)):
        dp1[i] = (dp1[i-1] * 3) % M
        if x[i]:
            dp2[i] = (dp1[i-1] % M + (dp2[i-1] * 2) % M) % M
        else:
            dp2[i] = dp2[i-1]

    return dp2[-1]

main()

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

def mod_pow(x,n):
    if n==0:return 1
    if n%2:return (x*mod_pow(x,n-1))%mod
    return (mod_pow(x,n//2)**2)%mod

ans = 0
C=0
for i in range(N):
    if L[i]=="0":continue
    ans += mod_pow(2,C)*mod_pow(3,N-1-i)
    ans %= mod
    C+=1
ans += mod_pow(2,C)
ans %= mod
print(ans)

Solution (Python):
L = input()
l = len(L)
a = 1
for i in range(l):
    a = 3 * a
    a = a % 1000000007
b = 2
c = 0
j = l-2
while(j >= 0):
    d = 0
    if L[l-1-j] == "0":
        d = 2 * b % 1000000007
    else:
        b = (2 * b) % 1000000007
    c = (3 * c) % 1000000007
    c = (d + c) % 1000000007
    j -= 1
a = (a - c) % 1000000007
print(a)

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

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

for i,c in enumerate(S):
    dp[i+1][0] = dp[i][0]*2 if int(c) else dp[i][0]
    dp[i+1][1] = dp[i][0] if int(c) else 0
    dp[i+1][1] += dp[i][1]*3
    dp[i+1][0] %= MOD
    dp[i+1][1] %= MOD
print(sum(dp[-1])%MOD)

Solution (Python):
L = input()

length = len(L)
cnt = 1
mod = 10**9+7
scale = 1

for l in reversed(L):
    if l == "0":
        pass
    else:
        cnt = divmod(cnt * 2 + scale, mod)[1]
    scale = divmod(scale*3, mod)[1]

print(cnt)

Solution (Python):
l = input()
M = 1000000007
d = len(l)

def modpow2(n):
    if n == 0:
        return 1 
    elif n % 2 == 0:
        return (modpow2(n // 2) ** 2) % M
    else:
        return ((modpow2(n // 2) ** 2) * 2) % M

answer = 3
c = 1
for i in range(1, d):
    if l[i] == '1':
        c += 1
        answer = (answer * 3) % M    
    else:
        answer = ((answer * 3) - modpow2(c + 1)) % M
print(answer)

Solution (Python):

import sys

MOD = 1000000007  

def solve(L: str):
    n = len(L)
    memo = [0] * (n + 1)
    memo[0] = 1
    for i in range(1, n + 1):
        memo[i] = memo[i - 1] * 3 % MOD
    cum = [0] * (n + 1)
    cum[0] = 1
    for i in range(1, n + 1):
        cum[i] = (cum[i - 1] * 2) % MOD

    ret = 0
    cnt = 0
    for i in range(n):
        c = L[i]
        if c == '1':
            rest = n - i - 1
            ret = (ret + memo[rest] * cum[cnt]) % MOD
            cnt += 1
            
    ret = (ret + cum[cnt]) % MOD
    print(ret)
    return


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

if __name__ == '__main__':
    main()

Solution (Python):
def pow_mod(x, n, p):
    ans = 1 % p
    while n > 0:
        if n % 2:
            ans = ans * x % p
        n //= 2
        x = x * x % p
    return ans

MOD = 10**9 + 7
L = int(input(),2)
K = L + 1
s = bin(K)[:1:-1]
M = s.count('1')
N = len(s)
ans = 0
for i in range(N):
    if s[i] == '0':
        continue
    else:
        M -= 1
        ans += pow_mod(2,M,MOD)*pow_mod(3,i,MOD) % MOD
        ans %= MOD
print(ans)

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

Solution (Python):
L=input()
mod=10**9+7
S=L[::-1]
s=1
t=1
for i in range(len(S)):
    if S[i]=='1':
        s=2*s+t
        s%=mod
    t=2*t+t
    t%=mod
print(s%mod)

Solution (Python):
mod=10**9+7
L=input()
N=len(L)
two=[1]*(1+N)
three=[1]*(1+N)
for i in range(1,1+N):
    two[i]=two[i-1]*2%mod
    three[i]=three[i-1]*3%mod
def freecalc(i,cnt):
    return three[i]*two[cnt]%mod
ans=0
cnt=0
for i,s in enumerate(L):
    if s=="1":
        ans=(ans+freecalc(N-i-1,cnt))%mod
        cnt+=1
print((ans+pow(2,cnt))%mod)

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

dp = [[0] * 2 for _ in range(len(L)+1)]
dp[0][0] = 1
for i in range(len(L)):
    for smaller in range(1):
        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):
MOD = int(1e9 + 7)

def main():
    L = input()
    N = len(L)
    dp = [0] * (N + 1)
    dp[1] = 1
    for i in range(2, N + 1):
        dp[i] = (dp[i-1] * 3) % MOD
    ans = 1
    for i in range(1, N+1):
        if L[-i] == "1":
            ans = (ans * 2 + dp[i]) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
mod = 1000000007
L = input()
ans = 1
n = len(L)
i = n - 1
while i >=0:
    n0 = 0
    n1 = 0
    while L[i] == '0':
        n0 += 1
        i -= 1
    while L[i] == '1':
        n1 += 1
        i -= 1
        if i < 0:
            break
    ans *= pow(2, n1, mod)
    ans += (pow(3, n1, mod) - pow(2, n1, mod)) * pow(3, n - i - 1 - n1, mod)
    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):

import heapq
import math
import sys

MOD = 1000000000 + 7

binary = input()
digit_num = len(binary)

all_one = 1
along = 1

for i in range(0, digit_num):
    d = binary[digit_num - i - 1]
    if d == '0':
        pass
    else:
        assert d == '1'
        along = (all_one + 2 * along) % MOD
    all_one = (all_one * 3) % MOD

print(along)

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

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

r = (r + pow(2, one, mod)) % mod

print(r)

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

L = input()
N =len(L)
powlis =[1]
foo = 1
for _ in range(N):
    foo = foo *3 %p
    powlis.append(foo)

foo = 2
ans = powlis[N-1]
for i,n in enumerate(L[1:-1]):
    i += 2
    if n == "1":
        ans += (foo* powlis[N-i])%p
        foo = (foo*2) %p
if L[-1]=="1" and N!=1:
    ans = (ans + foo*3)%p
else:
    ans = (ans +foo)%p
print(ans)

Solution (Python):
l = input()

a3 = [1]
a2 = [1]

for i in range(len(l)+5):
    a3.append((a3[-1]*3)%(10**9+7))
    a2.append((a2[-1]*2)%(10**9+7))

ans = 0
a = 0
for i in range(len(l)):
    if l[i]=='1':
        ans += (a3[len(l)-i-1]*a2[a])
        a+=1
    if i==len(l)-1:
        ans += a2[a]
    ans %= 10**9+7

print(ans)

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

Solution (Python):
L = int(input(),2)

mod = 10**9+7

res = 0
bi = 1

thr = [1]
for i in range(1000002):
    thr.append(thr[-1]*3%mod)

for i in range(1000001,0,-1):
    if ((L>>i)&1) == 1:
        res = (res+(thr[i]*bi)%mod)%mod
        bi = bi*2%mod
if (L&1) == 1:
    res += 3*bi
else:
    res += bi
print(res%mod)

Solution (Python):
MOD=10**9+7
l=input()
ans1=2
ans2=1

for i in range(1,len(l)):
    if l[i]=="0":
        ans2*=3
    if l[i]=="1":
        ans2=ans1+ans2*3
        ans1*=2
    ans1%=MOD
    ans2%=MOD
print((ans1+ans2)%MOD)

Solution (Python):
L = list(map(int, input()))
N = len(L)

tab2 = [None] * (N + 2)
tab2[0] = tmp = 1
for i in range(N + 1):
    tmp = (tmp * 2) % (10 ** 9 + 7)
    tab2[i + 1] = tmp

tab3 = [None] * (N + 1)
tab3[0] = tmp = 1
for i in range(N):
    tmp = (tmp * 3) % (10 ** 9 + 7)
    tab3[i + 1] = tmp

ans = tab3[-1]
cnt = 0
for i, Li in enumerate(L):
    if Li == 1:
        cnt += 1
    else:
        ans = (ans - tab3[N - 1 - i] * tab2[cnt + 1]) % (10 ** 9 + 7)
        
print(ans)

Solution (Python):
from functools import lru_cache
Mod = 10**9+7

l = [int(t) for t in list(input())]
n = len(l)

@lru_cache(maxsize=10000)
def f(x):
  if x == 0:
    return 1
  elif x%2 == 1:
    return (3*f(x-1))%Mod
  else:
    return (f(x//2)**2)%Mod

@lru_cache(maxsize=10000)
def g(x):
  if x == 0:
    return 1
  elif x%2 == 1:
    return (2*g(x-1))%Mod
  else:
    return (g(x//2)**2)%Mod



s = 0
k = 0
for i in range(n):
  if l[i] == 0:
    continue
  s = (s + f(n-1-i)*g(k))%Mod
  k += 1
s = (s + g(k))%Mod
print(s)

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

idx = 0
ones = 0

prime = 1000000007

pattern = pow(3, length, prime)

for s in l:
    idx += 1
    if s == "1":
        ones += 1
    else:
        pattern -= (pow(2, ones + 1, prime) * pow(3, length - idx, prime)) % prime

print(pattern % prime)

Solution (Python):
MOD = 1000000007

l = str(input())
c = [1]
for i in range(len(l) + 1):
	c.append((c[-1] * 3) % MOD)

l = l[::-1]
ans = 1
for i, e in enumerate(l):
	if e == '1':
		ans = (ans * 2 + c[i]) % MOD
print(ans)

Solution (Python):
MOD = 1000000007
L = input()
n = len(L)
ans = 0
one = 0
for i in range(n):
    c = L[i]
    if c == '1':
        m = n - i - 1
        
        t = pow(3, m, MOD) * pow(2, one, MOD)
        
        ans += t
        ans %= MOD
        one += 1
t = pow(2, one)
ans += t
ans %= MOD
print(ans)

Solution (Python):
s = input()
mod = 10**9 + 7
total = 0

n = len(s)
cnt_left_one = [0] * (n + 1)
for i in range(1, n + 1):
    if s[i - 1] == '1':
        cnt_left_one[i] = cnt_left_one[i - 1] + 1
    else:
        cnt_left_one[i] = cnt_left_one[i - 1]


total += pow(2, cnt_left_one[n], mod)

for k in range(0, n):
    if s[k] == '0':
        continue
    total += pow(2, cnt_left_one[k], mod) * pow(3, n - 1 - k, mod)

print(total % mod)

Solution (Python):
mod = 1000000007

L = input()

threes = [1] * (len(L) + 1)
for i in range(1, len(L) + 1):
    threes[i] = threes[i-1] * 3 % mod

ans1 = 1
ans2 = 0
for i in range(len(L)):
    if L[i] == "0":
        continue
    ans2 += ans1 * threes[len(L) - i - 1] % mod
    ans2 %= mod
    ans1 *= 2
    ans1 %= mod
print((ans1 + ans2) % mod)

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

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

s = input()
L = int(s, 2)

lg = len(s)

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


for i in range(lg):
    if (L >> (lg - 1 - i)) & 1:
        dp[i + 1][0] += dp[i][0] * 2
        dp[i + 1][0] %= mod
        

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

        dp[i + 1][1] += dp[i][1] * 3
        

        dp[i + 1][1] %= mod
    else:
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][0] %= mod
        

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

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

Solution (Python):
l=input()
s=len(l)
mod=1000000007
count=1
for i in range(s):
    if l[s-i-1]=='1':
        count=count*2+pow(3,i,mod)
        count=count%mod
print(count)

Solution (Python):
L = input()[::-1]
M = len(L)



mod = 10**9 + 7

power3 = [1]*(M+1)
for i in range(1,M):
  power3[i] = (3*power3[i-1])%mod


  
dp = [1]* (M) 

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


print(dp[M-1])

Solution (Python):
import sys


MOD = 10 ** 9 + 7
fin = sys.stdin.readline
L = fin().rstrip("\n")

num_bits = len(L)

prefix_num_comb = [[[0] * 2 for _ in range(2)] for _ in range(num_bits)]
prefix_num_comb[0][0][False] = 1
prefix_num_comb[0][1][True] = 2

for i in range(1, num_bits):
    bit = L[i]
    if bit == '1':
        prefix_num_comb[i][1][True] = (prefix_num_comb[i - 1][0][True] + prefix_num_comb[i - 1][1][True]) * 2
        prefix_num_comb[i][1][True] %= MOD
        prefix_num_comb[i][0][False] = sum(prefix_num_comb[i - 1][0]) + sum(prefix_num_comb[i - 1][1])
        prefix_num_comb[i][0][False] %= MOD
        prefix_num_comb[i][1][False] = (prefix_num_comb[i - 1][0][False] + prefix_num_comb[i - 1][1][False]) * 2
        prefix_num_comb[i][1][False] %= MOD
    else:
        prefix_num_comb[i][1][False] = (prefix_num_comb[i - 1][0][False] + prefix_num_comb[i - 1][1][False]) * 2
        prefix_num_comb[i][1][False] %= MOD
        prefix_num_comb[i][0][False] = prefix_num_comb[i - 1][0][False] + prefix_num_comb[i - 1][1][False]
        prefix_num_comb[i][0][False] %= MOD
        prefix_num_comb[i][0][True] = prefix_num_comb[i - 1][0][True] + prefix_num_comb[i - 1][1][True]
        prefix_num_comb[i][0][True] %= MOD

print((sum(prefix_num_comb[-1][0]) + sum(prefix_num_comb[-1][1])) % MOD)

Solution (Python):
L = input().strip()
t = L.count('1')
N = len(L)
L = [1 if l == '1' else 0 for l in L]
mod = 10**9+7
pre = 0
ans = pow(2, t, mod)
for i, l in enumerate(L):
    if not l:
        continue
    ans = (ans + pow(2, pre, mod)*pow(3, N - i - 1, mod)) % mod
    pre += 1
print(ans)

Solution (Python):
L=input()

S = [1]
s = 1
for i in range(len(L)):
    s = (s*3)%(10**9+7)
    S.append(s)
S2 = [1]
s2 = 1
for i in range(len(L)):
    if L[i]=="1":
        s2=(s2*2)%(10**9+7)
        S2.append(s2)


ans = 0
count = 0
for i in range(len(L)):
    if L[i]=="1":
        ans = (ans+S2[count]*S[len(L)-i-1])%(10**9 + 7)
        count+=1

print((ans+S2[count])%(10**9 + 7))

Solution (Python):
l = input()
M = 10**9+7
n = len(l)
ans = 1
dp = [1]
for i in range(n):
    ans*=3
    ans%=M
    dp.append(dp[i]*3%M)
cnt = 1
t = 0
for i in range(n):
    if l[i]=='1':
        cnt*=2
        cnt%=M
    if l[i]=='0':
        t=cnt*2*dp[n-i-1]
        t%=M
        ans+=(M-t)
        ans%=M
print(ans)

Solution (Python):
L = input()

MOD = 10**9 + 7

N = len(L)
dp = [0 for _ in range(N + 1)]
dp[0] = 1
for i in range(1, N + 1):
    dp[i] = (3 * dp[i - 1]) % MOD

ans = 0
c = 1
for i in range(N):
    if L[i] == '1':
        ans = (ans + c * dp[N - i - 1]) % MOD
        c = (c * 2) % MOD

ans = (ans + c) % MOD

print(ans)

Solution (Python):











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

dp[0][0] = 1
for i,ni in enumerate(n): 
    ni = int(ni)
    dp[i+1][1] += 3*dp[i][1]
    dp[i+1][1] %= MOD
    if ni == 1:
        dp[i+1][1] += dp[i][0]
        dp[i+1][0] += 2*dp[i][0]
    else:
        dp[i+1][0] += 1*dp[i][0]
    dp[i+1][1] %= MOD
    dp[i+1][0] %= MOD
        



print(sum(dp[len(n)])%MOD)

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

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

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

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

res = 0
cum_one = 0
for i in range(len(L)):
    if L[i] == '1':
        res += pow(2, cum_one, LARGE) * pow(3, len(L) - i - 1, LARGE)
        res = res % LARGE
        cum_one += 1

res += pow(2, cum_one, LARGE)
res = res % LARGE
print(res)

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

Solution (Python):
S = [int(i) for i in input()]
n = len(S)
p = int(1e9) + 7

DP = [[0] * 2 for i in range(n + 1)]
DP[0][1] = 1

for i in range(n):
    DP[i + 1][0] += DP[i][0] * 3 % p
    if S[i] == 1:
        DP[i + 1][0] += DP[i][1] % p
        DP[i + 1][1] += DP[i][1] * 2 % p

    else:
        DP[i + 1][1] += DP[i][1] % p

print(sum(DP[n]) % p)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    p,q,r = LI()
    print(p+q+r-max(p,q,r))
    return


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


def C():
    n,m = LI()
    f = [1 for i in range(n+10000)]
    for i in range(m):
        a = I()
        f[a] = 0
    dp = [0 for i in range(n+10000)]
    dp[0] = 1
    for i in range(n):
        if f[i+1]:
            dp[i+1] += dp[i]
            dp[i+1] %= mod
        if f[i+2]:
            dp[i+2] += dp[i]
            dp[i+2] %= mod
    print(dp[n])
    return


def D():
    h,w = LI()
    s = SR(h)
    vi = [[0 for j in range(w)] for i in range(h)]
    ho = [[0 for j in range(w)] for i in range(h)]
    q = deque()
    for y in range(h):
        for x in range(w):
            if s[y][x] == "
                l = len(q)
                while q:
                    i,j = q.pop()
                    vi[i][j] = l
            else:
                q.append((y,x))
        l = len(q)
        while q:
            i,j = q.pop()
            vi[i][j] = l
    for x in range(w):
        for y in range(h):
            if s[y][x] == "
                l = len(q)
                while q:
                    i,j = q.pop()
                    ho[i][j] = l
            else:
                q.append((y,x))
        l = len(q)
        while q:
            i,j = q.pop()
            ho[i][j] = l
    ans = 0
    for y in range(h):
        for x in range(w):
            ans = max(ans,vi[y][x]+ho[y][x]-1)
    print(ans)
    return


def E():
    b = S()
    l = len(b)
    for i in range(l):
        b[i] = int(b[i])
    dp = [[0 for j in range(2)] for i in range(1000002)]
    dp[0][0] = 1
    for i in range(l):
        for j in range(2):
            x = 1 if j else b[i]
            for d in range(x+1):
                if d:
                    dp[i+1][j or d < b[i]] += 2*dp[i][j]
                    dp[i+1][j or d < b[i]] %= mod
                else:
                    dp[i+1][j or d < b[i]] += dp[i][j]
                    dp[i+1][j or d < b[i]] %= mod
    ans = 0
    for j in range(2):
        ans += dp[l][j]
        ans %= mod
    print(ans)
    return


def F():
    n = I()

    return


if __name__ == "__main__":
    E()

Solution (Python):
import sys, math, collections, heapq, itertools
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0: a, b = b, a % b
    return b
  
def solve():
    file = sys.stdin.readline 
    INF = 10 ** 25
    mod = 7 + 10 ** 9
    L = file()
    length = len(L)
    DP = [[0, 0] for i in range(length-1)]
    DP[0][0] = 2
    DP[0][1] = 1
    for i in range(1, length-1):
        if L[i] == "1":
            DP[i][0] = (DP[i-1][0] * 2) % mod
            DP[i][1] = (DP[i-1][0] + DP[i-1][1] * 3) % mod
        else:
            DP[i][0] = DP[i-1][0]
            DP[i][1] = (DP[i-1][1] * 3) % mod
    print(sum(DP[length - 2]) % mod)

    return 0
  
if __name__ == "__main__":
    solve()

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

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


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

def F(i):
  
  if i == L_size:
    return 1
  result = 0
  c = int(L[i])
  if c == 0:
    
    result += F(i+1)
  else:
    
    result += 2*F(i+1)
    
    result += pow_3[L_size - i - 1]
  result %= MOD
  return result



L = input()
L_size = len(L)

answer = F(0)
print(answer)

Solution (Python):
mod = 10**9+7
L = input()
ans = 0
n = len(L)
c1 = 0
for c in L:
    n -= 1
    if c=="1":
        ans += pow(3, n, mod) * pow(2, c1, mod)
        c1 += 1
        ans %= mod
ans += pow(2, c1, mod)
ans %= mod
print(ans)

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

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

MOD = 10**9 + 7
ans = 0
cnt = 0
for i in range(B):
    if L[i] == '1':
        ans += (pow(2, cnt, MOD) * pow(3, B-i-1, MOD))
        cnt += 1
ans += pow(2, cnt, MOD)
print(ans % MOD)

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

MOD = 10**9 + 7
ans = 0
cnt = 0
for i in range(B):
    if L[i] == '1':
        ans += (pow(2, cnt, MOD) * pow(3, B-i-1, MOD))
        cnt += 1
ans += pow(2, cnt, MOD)
print(ans % 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):
l = input()
dp0 = 0
dp1 = 1
MOD = 10 ** 9 + 7
for c in l:
    if c == '0':
        dp0 = dp0 * 3 % MOD
    else:
        dp0 = (dp0 * 3 + dp1) % MOD
        dp1 = dp1 * 2 % MOD
    
print((dp0 + dp1) % MOD)