Problem:
 Score : 500 points    Problem Statement You are given a positive integer L in base two.
How many pairs of non-negative integers (a, b) satisfy the following conditions?   a + b \leq L  a + b = a \mbox{ XOR } b   Since there can be extremely many such pairs, print the count modulo 10^9 + 7 .   What is XOR?  The XOR of integers A and B , A \mbox{ XOR } B , is defined as follows:   When A \mbox{ XOR } B is written in base two, the digit in the 2^k 's place ( k \geq 0 ) is 1 if either A or B , but not both, has 1 in the 2^k 's place, and 0 otherwise.   For example, 3 \mbox{ XOR } 5 = 6 . (In base two: 011 \mbox{ XOR } 101 = 110 .)

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

mod = 10**9 + 7

l = [int(bit) for bit in input()]
bl = len(l)
inv3 = power(3, mod-2, mod)
pow2 = 1
pow3 = power(3, bl-1, mod)
count = 0

for i in range(bl-1):
  if l[i]:
    count = (count + pow2 * pow3) % mod
    pow2 = pow2 * 2 % mod
  pow3 = pow3 * inv3 % mod
if l[-1]:
  count = (count + pow2 * 3) % mod
else:
  count = (count + pow2) % mod

print(count)

Solution (Python):
s = input()


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

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

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

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

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

L=input()
n=len(L)
dp1=[0]*(n+1); dp2=[0]*(n+1)
dp2[0]=1

for i in range(n):
    if L[i] == "1":
        dp1[i+1] = (dp1[i]*3 + dp2[i]) % mod
        dp2[i+1] = dp2[i]*2 % mod
    else:
        dp2[i+1] = dp2[i] % mod
        dp1[i+1] = dp1[i]*3 % mod
print((dp1[n] + dp2[n])%mod)

Solution (Python):
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

L = list(sr())
MOD = 10 ** 9 + 7
bit_len = len(L)

dp_any = 1 
dp_spe = 2
for i in range(1, bit_len):
    x, y = dp_any, dp_spe
    if L[i] == '1':
        dp_any = x * 3 + y
        dp_spe = y * 2
    else:
        dp_any = x * 3
        dp_spe = y
    dp_any %= MOD
    dp_spe %= MOD

answer = (dp_any + dp_spe) % MOD
print(answer)

Solution (Python):
L=list(input())
mod=10**9+7
N=len(L)
data=[0]*N
data[0]=1
for i in range(1,N):
    data[i]=data[i-1]*3%mod
    
ans=0
num=1
for i in range(N):
    if L[i]=="0":
        continue
    else:
        
        ans=(ans+num*data[N-1-i])%mod
        num=num*2%mod

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

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

ans = 0

MOD = 1000000007
def pow_mod(x, y):
    if y == 0: return 1
    ans = 1
    while y > 1:
        if y % 2 != 0: 
            ans *= x
            ans %= MOD
        x *= x
        x %= MOD
        y //= 2
    return ans * x % MOD

keisuu = 1
for i, b in enumerate(l):
  if b == "1":
    ans += (keisuu * pow_mod(3, len_l - i - 1)) % MOD
    ans %= MOD
    keisuu *= 2
    keisuu %= MOD

ans += keisuu
ans %= MOD

print(ans)

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

Solution (Python):

def main():
    L = input()
    n = len(L)
    t = []
    mod = 10 ** 9 + 7
    for i, v in enumerate(L):
        if v == '1':
            t.append(i)
    r = 1
    p = 1
    for i, v in enumerate(reversed(L)):
        p %= mod
        if v == '1':
            r *= 2
            r += p
            r %= mod
        p *= 3
    print(r % mod)
main()

Solution (Python):
def main():
    MOD = 10 ** 9 + 7
    L = input()
    a, b = 0, 1
    for i in L:
        if i == '1':
            a, b = (b + a * 2) % MOD, b * 3 % MOD
        else:
            a, b = (a * 3) % MOD, (b + a * 2) % MOD
    return b

print(main())

Solution (Python):
l=list(input())
mod=pow(10,9)+7
n=len(l)

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


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

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

def input():
    return sys.stdin.readline().rstrip()

def main():
    L=input()
    n=len(L)
    dp=[[0]*2 for _ in range(n+1)]
    dp[0][0]=1
    for i in range(n):
        dp[i+1][1]=dp[i][1]*3%MOD
        if L[i]=='1':
            dp[i+1][0]=dp[i][0]*2%MOD
            dp[i+1][1]+=dp[i][0]
        else:
            dp[i+1][0]=dp[i][0]
    print(sum(dp[n])%MOD)

if __name__ == '__main__':
    main()

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

Solution (Python):
l = input()
n = len(l)
mod = 10 ** 9 + 7
memo = [1]
memo2 = [1]

for i in range(n):
    memo.append(memo[-1] * 3 % mod)
    memo2.append(memo2[-1] * 2 % mod)

i = 1
j = -1
ans = 0

for c in l:
    if c == '1':
        j += 1
        ans += (memo[n-i] ) * memo2[j]
        ans %= mod
    i+=1
ans += memo2[j+1]
ans %= mod
print(ans)

Solution (Python):
l = input()
p = 10 ** 9 + 7
dp = [0, 1]
for i in l:
    dp2 = [j % p for j in dp]
    if i == "0":
        dp[0] = dp2[0] * 3
        dp[1] = dp2[1]
    else:
        dp[0] = dp2[0] * 3 + dp2[1]
        dp[1] = dp2[1] * 2
print(sum(dp) % p)

Solution (Python):
def main():
    L = input()
    MOD = 10 ** 9 + 7
    dp = [[0] * 2 for _ in range(10 ** 6 + 5)]
    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]) % MOD
        
        
        if L[i] == '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[len(L)][0] + dp[len(L)][1]) % MOD
    print(ans)
    

if __name__ == "__main__":
    main()

Solution (Python):

import re
import math
import fractions
import random
from heapq import heappop,heappush
import time
import sys
input = sys.stdin.readline

mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
 

 

L=input()
dp=[[0,0] for _ in range(len(L)+5)]
dp[0][0]=1

ans=0
for a in range(len(L)-1):
    c=L[a]
    
    if c=="0":
        dp[a+1][0]=dp[a][0]
        dp[a+1][1]=dp[a][1]
    else:
        dp[a+1][1]=dp[a][1]+dp[a][0]
    
    if c=="0":
        dp[a+1][1]+=dp[a][1]*2
    else:
        dp[a+1][0]+=dp[a][0]*2
        dp[a+1][1]+=dp[a][1]*2
    dp[a+1][0]%=mod
    dp[a+1][1]%=mod
print((dp[len(L)-1][0]+dp[len(L)-1][1])%mod)

Solution (Python):
p = 10**9+7
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x
    if m%2==0:
        return (pow(x,m//2)**2)%p
    else:
        return (x*pow(x,(m-1)//2)**2)%p
L = input().strip()
N = len(L)
C = [0 for _ in range(N)]
for i in range(1,N):
    if L[i-1]=="1":
        C[i] = C[i-1]+1
    else:
        C[i] = C[i-1]
tot = 0
for i in range(N):
    if L[i]=="1":
        tot = (tot+pow(3,N-1-i)*pow(2,C[i]))%p
if L[N-1]=="0":
    tot = (tot+pow(2,C[N-1]))%p
else:
    tot = (tot+pow(2,C[N-1]+1))%p
print(tot)

Solution (Python):
a = input()
s = len(a)
MOD = 10**9 + 7
dp = [0]*100010
ep = [0]*100010

dp[0] = 1

for i in range(s):
    ep[i+1]+= 3*ep[i]
    if a[i] == '1':
        dp[i+1] += 2*dp[i]
        ep[i+1] += dp[i]
    else:
        dp[i+1]+=dp[i]
    
    ep[i+1]%=MOD
    dp[i+1]%=MOD
ans = (dp[s]+ep[s])%MOD
print(ans)

Solution (Python):
ll = list(input())

dp1 = [0 for i in range(len(ll))]
dp2 = [0 for i in range(len(ll))]
for idx, l in enumerate(ll):
    if l == "1":
        if idx == 0:
            dp1[0] = 2
            dp2[0] = 1
        else:
            dp1[idx] = dp1[idx-1] * 2
            dp2[idx] = dp2[idx-1] * 3 + dp1[idx-1]
            dp1[idx] %= 10**9+7
            dp2[idx] %= 10**9+7
    else:
        dp1[idx] = dp1[idx-1]
        dp2[idx] = dp2[idx-1] * 3
        dp2[idx] %= 10**9+7

print((dp1[-1] + dp2[-1]) % (10**9+7))

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

L = input()
N = len(L)

ans = 0
c = 0

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

print(ans)

Solution (Python):
L=input()
L=L+"0"
L=L[::-1]
pow3=[0 for i in range(110000)]
pow3[0]=1
mod=10**9+7
for i in range(1,100010):
    pow3[i]=pow3[i-1]*3%mod

a=1
for i in range(len(L)):
    if L[i]=="1":
        a=(a*2+pow3[i-1])%mod
print(a%mod)

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

Solution (Python):
S=input()
L=[0]*len(S)
for i in range(len(S)):
    L[i]=int(S[i])

mod=10**9+7    
    
N=len(S)
power=[1]*(N+3)
for i in range(1,N+3):
    power[i]=(power[i-1]*3)%mod

    

ans=1
for i in range(N):
    if L[N-1-i]==1:
        ans=(2*ans+power[i])%mod
print(ans%mod)

Solution (Python):

n = list(input())
n = n[::-1]
if n.count('1') == len(n):
    n = list('0' * len(n) + '1')
else:
    for i in range(len(n)):
        if n[i] == '0':
            n[i] = '1'
            point = i
            break
    for i in range(point):
        n[i] = '0'

n = n[::-1]

count = 0
ans = 0
mod = 10 ** 9 + 7

for i in range(len(n)):
    a = pow(2, count, mod)
    b = pow(3, len(n)-i-1, mod) 
    tmp = (a * b) % mod
    if n[i] == '1':
        count += 1
        ans += tmp
        ans %= mod

print(ans)

Solution (Python):

n = list(input())
n = n[::-1]
if n.count('1') == len(n):
    n = list('0' * len(n) + '1')
else:
    for i in range(len(n)):
        if n[i] == '0':
            n[i] = '1'
            point = i
            break
    for i in range(point):
        n[i] = '0'

n = n[::-1]

count = 0
ans = 0
mod = 10 ** 9 + 7

for i in range(len(n)):
    a = pow(2, count, mod)
    b = pow(3, len(n)-i-1, mod) 
    tmp = (a * b) % mod
    if n[i] == '1':
        count += 1
        ans += tmp
        ans %= mod

print(ans)

Solution (Python):

n = list(input())
n = n[::-1]
if n.count('1') == len(n):
    n = list('0' * len(n) + '1')
else:
    for i in range(len(n)):
        if n[i] == '0':
            n[i] = '1'
            point = i
            break
    for i in range(point):
        n[i] = '0'

n = n[::-1]


count = 0
ans = 0
mod = 10 ** 9 + 7

for i in range(len(n)):
    a = pow(2, count, mod)
    b = pow(3, len(n)-i-1, mod)
    if n[i] == '0':
        a, b = 0, 0 
    tmp = (a * b) % mod
    
    if n[i] == '1':
        count += 1
        count %= mod
        ans += tmp
        ans %= mod

print(ans)

Solution (Python):
MOD = 10**9+7
T = [1]*(10**5+1)
D = [1]*(10**5+1)
for i in range(10**5):
  T[i+1] = T[i]*3 % MOD
  D[i+1] = D[i]*2 % MOD
L = input()
n = len(L)
ans = 1
count = 0
for i in range(n):
  if L[i] == "1":
    ans += (T[n-1-i]+1)*D[count]
    ans %= MOD
    count += 1
print(ans)

Solution (Python):
mod=1e9+7

if __name__ == '__main__':
    L=input()
    N=len(L)
    DP1=[0]*(N)
    DP2=[0]*(N)
    DP1[0]=1
    DP2[0]=2

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

    print(int((DP2[N-1]+DP1[N-1])%mod))

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


def main():
  L = input().strip()
  l = len(L)
  assert l > 0

  dp1 = [-1] * l
  dp2 = [-1] * l
  dp1[0] = 1
  dp2[0] = 2
  for k in range(1, l):
    dp1[k] = dp1[k - 1] * 3 % MOD

    if L[k] == '1':
      dp1[k] += dp2[k - 1]
      dp2[k] = dp2[k - 1] * 2 % MOD
    else:
      dp2[k] = dp2[k - 1]

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


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

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

ans = [2, 1]
for l in L:
  ans[1] *= 3
  ans[1] %= MOD
  if l == '1':
    ans[1] += ans[0]
    ans[0] *= 2
    ans[0] %= MOD

print(sum(ans) % MOD)

Solution (Python):
L=input()
DIV=10**9+7
dp=[[0 for i in range(2)] for j in range(len(L))]

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

for i in range(1,len(L)):
  x=int(L[i])
  dp[i][0]=(dp[i-1][0]*2*(x==1)+dp[i-1][0]*1*(x==0))%DIV
  dp[i][1]=(dp[i-1][0]*1*(x==1)+dp[i-1][1]*3)%DIV

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

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

dp=[[0 for i in range(2)] for j in range(len(L))]





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

for i in range(1,len(L)):
  x=int(L[i])
  dp[i][0]=(dp[i-1][0]*2*(x==1)+dp[i-1][0]*1*(x==0))%DIV
  dp[i][1]=(dp[i-1][0]*1*(x==1)+dp[i-1][1]*3)%DIV

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

Solution (Python):
L = [int(i) for i in input()]
l = len(L)



mod = 10 ** 9 + 7
answer = 0
mod_pow = [0] * (l + 1)
prev = 1
mod_pow[0] = 1


for i in range(1, l + 1):
    prev *= 3
    prev %= mod
    mod_pow[i] = prev

prev = 1
for i, j in enumerate(L, 1):
    if j == 0:
        continue
    answer += prev * mod_pow[l - i]
    answer %= mod
    prev *= 2
    prev %= mod

answer += prev
answer %= mod
print(answer)

Solution (Python):
L = [int(i) for i in input()]
l = len(L)


def mod_pow(a, p, mod):
    if p == 0:
        return 1
    elif p % 2 == 1:
        return a * mod_pow(a, p - 1, mod)
    else:
        return (mod_pow(a, p // 2, mod) % mod) ** 2 % mod




mod = 10 ** 9 + 7
answer = 0
prev = 1

for i, j in enumerate(L, 1):
    if j == 0:
        continue
    answer += prev * mod_pow(3, l - i, mod)
    answer %= mod
    prev *= 2
    prev %= mod

answer += prev
answer %= mod
print(answer)

Solution (Python):
MOD = 10**9+7
l = input()
dp0 = 0; dp1 = 1

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

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

MOD = 10 ** 9 + 7

if L[0] == "1":
  e = [2]
  l = [1]
else:
  e = [1]
  l = [0]
  
for i in range(1, N):
  if L[i] == "1":
    de = (e[-1] * 2) % MOD
    dl = (e[-1] * 1 + l[-1] * 3) % MOD
  else:
    de = (e[-1] * 1) % MOD
    dl = (e[-1] * 0 + l[-1] * 3) % MOD
  e.append(de)
  l.append(dl)


print((e[-1] + l[-1]) % MOD)

Solution (Python):
mod = 10 ** 9 + 7
x = 1
y = 0
for c in input():
	if c == "1":
		y *= 3
		y %= mod
		y += x
		y %= mod
		x *= 2
		x %= mod
	else:
		y *= 3
		y %= mod
print((x + y) % mod)

Solution (Python):
def examC():
    N, M = LI()
    A = [I() for _ in range(M)]
    A.append(N+1)
    fib = [1]*(N+2)
    for i in range(1,N):
        fib[i+2] = fib[i+1] + fib[i]
    fib[0] = 0

    ans = fib[A[0]]%mod
    for i in range(M):
        ans *= fib[A[i+1]-A[i]-1]
        ans %=mod
    print(ans)
    return

def examD():
    H, W = LI()
    S = [SI() for _ in range(H)]
    width = [[0]*W for _ in range(H)]
    height = [[0]*W for _ in range(H)]
    for i in range(H):
        cur = 0; keep = []
        for j in range(W):
            if S[i][j]==".":
                cur +=1
                keep.append(j)
            else:
                for k in keep:
                    width[i][k] = cur
                cur = 0; keep = []
        if keep:
            for k in keep:
                width[i][k] = cur
    for j in range(W):
        cur = 0; keep = []
        for i in range(H):
            if S[i][j]==".":
                cur +=1
                keep.append(i)
            else:
                for k in keep:
                    height[k][j] = cur
                cur = 0; keep = []
        if keep:
            for k in keep:
                height[k][j] = cur
    ans = 0
    for i in range(H):
        for j in range(W):
            cur = width[i][j] + height[i][j]
            if ans<cur:
                ans = cur
    print(ans-1)
    return

def examE():
    L = SI()
    N = len(L)
    Loc0 = [-1]*N; cur = 0
    for i in range(N):
        if L[i]=="0":
            Loc0[i] = cur
            cur +=1
    ans = pow(3,N,mod)

    for i in range(N):
        if Loc0[i]>=0:
            now = pow(2,(i-Loc0[i]+1),mod)*pow(3,(N-i-1),mod)
            ans -=now%mod
            if ans<0:
                ans +=mod
    print(ans)

    return

def examE2(L):

    N = int(L,2)
    ans = 0
    for a in range(N+1):
        for b in range(N+1):
            cur = a^b
            if cur!=a+b:
                continue
            if cur>N:
                continue
            ans +=1
    print(ans)

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examE()

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

Solution (Python):


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

l = input()
L = len(l)

dp1 = [0]*(L+1) 
dp2 = [0]*(L+1) 
dp1[0] = 1
dp2[0] = 0
for i in range(L):
    if l[i] == '1':
        dp1[i+1] += dp1[i]*2
        dp1[i+1] %= mod
        dp2[i+1] += dp1[i]
        dp2[i+1] %= mod
        dp2[i+1] += 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

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

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

S=list(input())
N=len(S)

P=1
ans=0
for i in range(N):
    if S[i]=="1":
        ans+=(P*pow(3,N-1-i,mod))
        P*=2
        P%=mod
print((ans+P)%mod)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

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

p3 = [1]
for _ in range(len(l)+5):
    p3.append((p3[-1]*3)%mod)

def dfs(k,f):
    if k == n:
        return 1
    if not f:
        return p3[n-k]
    if l[k] == "1":
        return (dfs(k+1,False)+dfs(k+1,True)*2)%mod
    else:
        return dfs(k+1,True)%mod

print(dfs(0,True))

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

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

p3 = [1]
for _ in range(len(l)+5):
    p3.append((p3[-1]*3)%mod)

def dfs(k,f):
    if k == n:
        return 1
    if not f:
        return p3[n-k]
    if l[k] == "1":
        return (dfs(k+1,False)+dfs(k+1,True)*2)%mod
    else:
        return dfs(k+1,True)%mod

print(dfs(0,True))

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

S = [0]*(N+1)
for i in range(N):
    if L[i] == "1":
        S[i+1] = S[i] + 1
    else:
        S[i+1] = S[i]

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

ans += pow(2, S[-1], mod)
print(ans%mod)

Solution (Python):

import sys

MOD = 1000000007  

def solve(L: str):
    N = len(L)

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

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

    print((dp[N][0]+dp[N][1])%MOD)
    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)
mod = 10**9+7
pow3 = [1]
for i in range(1,n):
    x = (3*pow3[i-1])%mod
    pow3.append(x)
ans = 0
for i in range(1,n+1):
    if L[-i] == '1':
        if i == 1:
            ans = 3
        else:
            ans = ans*2 % mod
            ans = (ans + pow3[i-1])%mod
    else:
        if i == 1:
            ans = 1
print(ans)

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

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

DP1 = [0]
DP2 = [1]

for i in L:
    if i == '1':
        x = (DP1[-1]*3+DP2[-1])%MOD
        y = (DP2[-1]*2)%MOD
        DP1.append(x)
        DP2.append(y)
    else:
        x = (DP1[-1]*3)%MOD
        DP1.append(x)
print((DP1[-1]+DP2[-1])%MOD)

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




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

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

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

Solution (Python):
l = input()

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

mod = 10**9+7

dp[0][0] = 1

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

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

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
MOD = 10**9+7
l = [int(i) for i in sys.stdin.readline().strip()]

dp0 = [0] * (len(l) + 1)

dp1 = [0] * (len(l) + 1)
dp0[0] = 1
for i, _l in enumerate(l, 1):
    if _l == 0:
        dp0[i] = dp0[i-1]
        dp1[i] = dp1[i-1] * 3
    else:
        dp0[i] = dp0[i-1] * 2
        dp1[i] = dp1[i-1] * 3 + dp0[i-1]
    dp0[i] %= MOD
    dp1[i] %= MOD
res = dp0[-1] + dp1[-1]
res %= MOD
print(res)

Solution (Python):
n=int(input())
num=len(str(n))-1
l=[]
ans=1
mod=10**9+7
for i in range(num):
  ans=(ans*3)%mod
  l.append(ans)
w=str(n)
now=2
for i in range(1,num):
  if w[i]=="0":
    pass
  else:
    ans=(ans+now*l[-i-1])%mod
    now=(now*2)%mod
if w[-1]=="0":
  ans=(ans+now)%mod
else:
  ans=(ans+3*now)%mod
if n==1:
  print(3)
else:
  print(ans)

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

sure = 1
possible = 2
for bit in L:
    if bit == '1':
        sure = (sure * 3 + possible) % mod
        possible = possible * 2 % mod
    else:
        sure = sure * 3 % mod

ans = (sure + possible) % mod
print(ans)

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

x = len(L)
L = int(L, 2)
sure = 1
possible = 2
for i in range(2, x+1):
    if (L >> (x-i)) & 1:
        sure = (sure * 3 + possible) % mod
        possible = possible * 2 % mod

    else:
        sure = sure * 3 % mod
        
ans = (sure + possible) % mod
print(ans)

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

x = len(L)
L = int(L, 2)
DP1 = [0] * (x+1)  
DP2 = [0] * (x+1)  
DP1[1] = 1
DP2[1] = 2
for i in range(2, x+1):
    if (L >> (x-i)) & 1:
        DP1[i] = (DP1[i-1] * 3 + DP2[i-1]) % mod
        DP2[i] = DP2[i-1] * 2 % mod

    else:
        DP1[i] = DP1[i-1] * 3 % mod
        DP2[i] = DP2[i-1]
ans = (DP1[x] + DP2[x]) % mod
print(ans)

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

con = 10 ** 9 + 7


def main():
	L = list(input())
	L = L[::-1]
	N = len(L)
	
	DP1 = [0] * (N + 1)
	DP2 = [0] * (N + 1)
	DP2[0] = 3
	for i in range(1, N + 1):
		DP2[i] = (3 * DP2[i - 1]) % con
	if L[0] == "1":
		DP1[0] = 3
	else:
		DP1[0] = 1

	
	for i in range(1, N):
		if L[i] == "1":
			DP1[i] = (DP1[i - 1] * 2 + DP2[i - 1]) % con
		else:
			DP1[i] = DP1[i - 1]
	print(DP1[N - 1])


if __name__ == '__main__':
	main()