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

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    def f(n):
        a = str(n)
        l = len(a)
        dp = [[[0]*2 for i in range(2)] for j in range(l+1)]
        dp[0][0][0] = 1
        for i in range(l):
            ni = i+1
            for j in range(2):
                x = 9 if j else int(a[i])
                for k in range(2):
                    for d in range(x+1):
                        nj = j|(d < int(a[i]))
                        nk = k|(d in (4,9))
                        dp[ni][nj][nk] += dp[i][j][k]
        return dp[l][0][1]+dp[l][1][1]

    a,b = LI()
    print(f(b)-f(a-1))
    return


def B():
    D = I()
    n = list(map(int, input()))
    l = len(n)
    dp = [[[0]*2 for i in range(D)] for j in range(l+1)]
    dp[0][0][0] = 1
    for i in range(l):
        ni = i+1
        for j in range(D):
            for k in range(2):
                x = 9 if k else int(n[i])
                for d in range(x+1):
                    nj = (j+d)%D
                    nk = k|(d < int(n[i]))
                    dp[ni][nj][nk] += dp[i][j][k]
                    dp[ni][nj][nk] %= mod
    print((dp[l][0][0]+dp[l][0][1]-1)%mod)
    return


def C():
    n = list(map(int, input()))
    l = len(n)
    dp = [[[0]*2 for j in range(l+1)] for i in range(l+1)]
    dp[0][0][0] = 1
    for i in range(l):
        ni = i+1
        for j in range(l):
            for k in range(2):
                x = 9 if k else n[i]
                for d in range(x+1):
                    nj = j+(d == 1)
                    nk = k|(d < n[i])
                    dp[ni][nj][nk] += dp[i][j][k]
    ans = 0
    for i in range(l+1):
        ans += i*sum(dp[l][i])
    print(ans)
    return


def D():
    n = list(map(int, input()))
    l = len(n)
    D = I()
    dp = [[[0]*2 for i in range(D)] for i in range(l+1)]
    dp[0][0][0] = 1
    for i in range(l):
        for j in range(D):
            for k in range(2):
                x = 9 if k else n[i]
                for d in range(x+1):
                    ni = i+1
                    nj = (j+d)%D
                    nk = k|(d<n[i])
                    dp[ni][nj][nk] += dp[i][j][k]
                    dp[ni][nj][nk] %= mod
    print((sum(dp[l][0])-1)%mod)
    return


def E():
    n,k = LI()
    a = LI()
    m = max(k,max(a)).bit_length()
    f = [0]*m
    for i in a:
        for j in range(m):
            if i&(1<<j):
                f[j] += 1
    dp = [[-float("inf")]*2 for i in range(m+1)]
    dp[0][0] = 0
    for i in range(m):
        ni = i+1
        ki = (k>>(m-i-1))&1
        for j in range(2):
            x = 1 if j else ki
            for d in range(x+1):
                nj = j|(d<ki)
                dp[ni][nj] = max(dp[ni][nj], dp[i][j]+(d*(n-f[m-i-1])+(1-d)*f[m-i-1])*(1<<(m-i-1)))
    print(max(dp[m]))
    return


def F():
    def bit_count(n):
        return bin(n).count("1")
    a,K = LI()
    a = list(map(int, str(a)))
    if len(set(a)) <= K:
        print(0)
        return
    l = len(a)
    m = 1024
    dp = [[[float("inf")]*2 for j in range(m)] for i in range(l+1)]
    dp[0][0][0] = 0
    for i in range(l):
        ni = i+1
        for j in range(m):
            if bit_count(j) > K:continue
            for k in range(2):
                x = 9 if k else a[i]
                for d in range(x+1):
                    nj = j|(1<<d)
                    nk = k|(d<a[i])
                    c = dp[i][j][k]*10+a[i]-d
                    if c < dp[ni][nj][nk]:
                        dp[ni][nj][nk] = c
    ans = float("inf")
    for i in range(m):
        if bit_count(i) <= K:
            mi = min(dp[l][i])
            if mi < ans:
                ans = mi
    dp = [[[float("inf")]*2 for j in range(m)] for i in range(l+1)]
    dp[0][0][0] = 0
    for i in range(l):
        ni = i+1
        for j in range(m):
            if bit_count(j) > K:continue
            for k in range(2):
                x = 0 if k else a[i]
                for d in range(x,10):
                    nj = j|(1<<d)
                    nk = k|(d>a[i])
                    c = dp[i][j][k]*10+d-a[i]
                    if c < dp[ni][nj][nk]:
                        dp[ni][nj][nk] = c
    for i in range(m):
        if bit_count(i) <= K:
            mi = min(dp[l][i])
            if mi < ans:
                ans = mi
    print(ans)
    return


def G():
    n = list(map(int, input()))
    l = len(n)
    dp = [[0]*2 for i in range(l+1)]
    dp[0][0] = 1
    for i in range(l):
        ni = i+1
        for j in range(2):
            x = 1 if j else n[i]
            for d in range(x+1):
                nj = j|(d<n[i])
                dp[ni][nj] += (1+d)*dp[i][j]
                dp[ni][nj] %= mod
    print(sum(dp[l])%mod)
    return


def H():

    return


def I_():

    return


def J():

    return


def K():

    return


if __name__ == "__main__":
    G()

Solution (Python):


mod=10**9+7
l=input()
n=len(l)
dp1,dp2=[0]*n,[0]*n
dp1[0],dp2[0]=1,2
for i in range(1,n):
	if l[i]=="1":
		dp1[i]=(3*dp1[i-1]+dp2[i-1])%mod
		dp2[i]=(2*dp2[i-1])%mod
	else:
		dp1[i]=(3*dp1[i-1])%mod
		dp2[i]=dp2[i-1]%mod
print((dp1[n-1]+dp2[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):
def main():
    import sys
    
    mod = 10**9+7
    L = input()[::-1]
    K = len(L)
    S = 1
    
    for i in range(K):
        if L[i] == "1":
            S = (2*S + pow(3,i,mod))%mod
    
    print(S)
    
main()

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

Solution (Python):
from sys import stdin

L = stdin.readline().rstrip()
inf = 10 ** 9 + 7
ones = 3
if L[-1] == '0':
    ans = 1
else:
    ans = 3

if len(L) == 1:
    print(ans)
    exit()

for i in range(2, len(L) + 1):
    if L[-i] == '1':
        ans = (ones + 2 * ans) % inf
    ones = (3 * ones) % inf

print(ans)

Solution (Python):
L = input()

dp_equal = 1 
dp_less = 0  

MOD = 10**9+7
        
for s in L:
    next_equal = 0
    next_less = 0
    
    if s == '0':
        next_equal += dp_equal
        next_less += dp_less 
    else:
        next_less += dp_equal + dp_less
        
    
    if s == '0':
        next_less += dp_less * 2
    else:
        next_equal += dp_equal * 2
        next_less += dp_less  * 2
    
    dp_equal, dp_less = next_equal % MOD, next_less % MOD
    
print((dp_equal + dp_less) % MOD)

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

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

    if s==1:
        dp[0][i+1]+=dp[1][i]
        dp[1][i+1]+=2*dp[1][i]
    else:
        dp[1][i+1]+=dp[1][i]
    dp[0][i+1]%=mod
    dp[1][i+1]%=mod


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

Solution (Python):
l = input()

a = 1
mod = 10 ** 9 + 7
for i, s in enumerate(l[: : -1]): 
  if s == "1":
      a = (2 * a + pow(3, i, mod)) % mod

print(a)

Solution (Python):
l = input()

a = 1
mod = 10 ** 9 + 7
for i, s in enumerate(l[: : -1]): 
  if s == "1":
      a = (2 * a + pow(3, i, mod)) % mod

print(a)

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

Solution (Python):
import sys
input = sys.stdin.readline
L = input().rstrip("\n")
mod = 1000000007

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

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

Solution (Python):
L = input()

MOD = 10 ** 9 + 7
LEN = len(L)
ans = 0
cnt = 0

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

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

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

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

pow2 = [1]
pow3 = [1]
for i in range(len(L)):
    pow2.append((pow2[-1]*2) % mod)
    pow3.append((pow3[-1]*3) % mod)

one=[]
for i in range(len(L)):
    if L[i] == "1":
        one.append(i)

total = 0
for i in range(len(one)):
    n = one[i]
    total += pow2[i] * pow3[len(L) - n - 1]
    total = total%mod

total += pow2[len(one)]
total =total%mod
print(total)

Solution (Python):






L = input()
lenL = len(L) 
ans = 3 ** (lenL - 1)
mod = 10 ** 9 + 7

pow_2 = [1] * (lenL+1)
pow_3 = [1] * (lenL+1)

for i in range(1, lenL+1):
	pow_2[i] = pow_2[i-1] * 2 % mod
	pow_3[i] = pow_3[i-1] * 3 % mod

num_one_leftside = 1
for i in range(1, lenL):
	if L[i] == '1':
		ans += pow_2[num_one_leftside] * pow_3[lenL - i - 1]
		ans %= mod


		num_one_leftside += 1

ans += pow_2[num_one_leftside]
ans %= mod

print(ans)

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

l = input()
n = len(l)

dp = [[0] * 2 for _ in range(n + 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] * 3
    else:
        dp[i + 1][0] += dp[i][0] * 2
        dp[i + 1][1] += dp[i][0]
        dp[i + 1][1] += dp[i][1] * 3
    dp[i + 1][0] %= mod
    dp[i + 1][1] %= mod

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

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

Solution (Python):
MOD = 1000000007

L = input().strip()
length = len(L)

dp1 = [-1] * length
dp2 = [-1] * length


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

for i in range(1, length) :
    dp1[i] = dp1[i - 1] * 3 % MOD  

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

print((dp1[-1] + dp2[-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):
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]

L=input()
a=0
x=10**9+7
def bp(a,n):
        r=1
        while(n):
           if n%2:
              r=r*a%x
           a=a*a%x
           n>>=1
        return r
c=len(L)
y=0
for i in range(c):
 if L[i]=="1":
  a+=(bp(3,c-1-i)*bp(2,y))%x
  a%=x
  y+=1
print((a+2**y)%x)

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

for l in L[1:]:
    ans = [0, 0]
    if l == "1":
        ans[0] = ans_last[0] * 2 % mod
        ans[1] = (ans_last[0] + ans_last[1] * 3) % mod
    else:
        ans[0] = ans_last[0]
        ans[1] = (ans_last[1] * 3) % mod

    ans_last = ans
print(sum(ans_last) % mod)

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

for l in L[1:]:
    ans = [0, 0, 0]
    if l == "1":
        ans[0] = ans_last[0] * 2 % mod
        ans[1] = (ans_last[1] * 2 + ans_last[2] * 2) % mod
        ans[2] = (ans_last[0] + ans_last[1] + ans_last[2]) % mod
    else:
        ans[0] = ans_last[0]
        ans[1] = (ans_last[1] * 2 + ans_last[2] * 2) % mod
        ans[2] = (ans_last[1] + ans_last[2]) % mod
    ans_last = ans
print(sum(ans_last) % mod)

Solution (Python):
L = input()
digits = len(L)
MOD = 10**9 + 7
ans = pow(2, L.count('1'), MOD)
counter = 0
for i, d in enumerate(L, 1):
    if d == '1':
        ans = (ans + (pow(3, digits - i, MOD) * pow(2, counter, MOD)) % MOD) % MOD
        counter += 1
print(ans)

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

L = input()

N = len(L)

dp = [[0]*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] = 2 * dp[i-1][0]
        dp[i][1] = dp[i-1][0] + 3 * dp[i-1][1]
    elif L[i-1] == "0":
        dp[i][0] = dp[i-1][0]
        dp[i][1] = 3 * dp[i-1][1]
    
    dp[i][0] %= mod
    dp[i][1] %= mod

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

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

Solution (Python):



""" convenient functions




"""

import sys
sys.setrecursionlimit(10**7)
from itertools import accumulate, combinations, permutations, product 

from math import factorial, ceil, floor
def factorize(n):
    """return the factors of the Arg and count of each factor
    
    Args:
        n (long): number to be resolved into factors
    
    Returns:
        list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
    """
    fct = []  
    b, e = 2, 0  
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
def combinations_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    
    if n < 0 or r < 0:
        raise Exception('combinations_count(n, r) not defined when n or r is negative')
    if n - r < r: r = n - r
    if r < 0: return 0
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combinations_with_replacement_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    if n < 0 or r < 0:
        raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
    elif n == 0:
        return 1
    else:
        return combinations_count(n + r - 1, r)
from bisect import bisect_left, bisect_right
from collections import deque, Counter, defaultdict 
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest 
from copy import deepcopy, copy 
from operator import itemgetter


from functools import reduce
def chmin(x, y):
    """change minimum
    if x > y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current minimum value
        y (long): potential minimum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x > y:
        x = y
        return (x, True)
    else:
        return (x, False)
def chmax(x, y):
    """change maximum
    if x < y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current maximum value
        y (long): potential maximum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x < y:
        x = y
        return (x, True)
    else:
        return (x, False)

from fractions import gcd 
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)



INF = 10 ** 18
MOD = 10 ** 9 + 7
modpow = lambda a, n, p = MOD: pow(a, n, p) 
def modinv(a, p = MOD):
    
    
    return modpow(a, p-2, p)
def modinv_list(n, p = MOD):
    if n <= 1:
        return [0,1][:n+1]
    else:
        inv_t = [0,1]
        for i in range(2, n+1):
            inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
        return inv_t
def modfactorial_list(n, p = MOD):
    if n == 0:
        return [1]
    else:
        l = [0] * (n+1)
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l[i] = tmp
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    
    
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if len(fac_list) <= n:
        a = factorial(n) % p
        b = factorial(k) % p
        c = factorial(n-k) % p
    else:
        a = fac_list[n]
        b = fac_list[k]
        c = fac_list[n-k]
    return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
def modadd(a, b, p = MOD):
    return (a + b) % MOD
def modsub(a, b, p = MOD):
    return (a - b) % p
def modmul(a, b, p = MOD):
    return ((a % p) * (b % p)) % p
def moddiv(a, b, p = MOD):
    return modmul(a, modpow(b, p-2, p))

""" initialize variables and set inputs

    
    

    
    
    
    
    

    
    
    
    

    
    
"""


r = lambda: sys.stdin.readline().strip()
r_int = lambda: int(r())
R = lambda: list(map(int, r().split()))
Rfloat = lambda: list(map(float, r().split()))
Rtuple = lambda: tuple(map(int, r().split()))
Rmap = lambda: map(int, r().split())

""" how to treat input







"""





L = r() 
length = len(L)
pow_three = [0] * length

for i in range(length):
    if i == 0:
        tmp = 1
        pow_three[0] = tmp
    else:
        tmp *= 3
        tmp %= MOD
        pow_three[i] = tmp

ans = 0
maxi = 1
for i, j in enumerate(L):
    if j == "1":
        ans += maxi * pow_three[length-1-i]
        ans %= MOD
        maxi *= 2
        maxi %= MOD
    else:
        continue

ans += maxi
ans %= MOD

print(ans)


"""memo: how to use defaultdict of list

Dic = defaultdict(list)

Dic[x].append(y)

for k, v in Dic.items():
"""

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

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

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

Solution (Python):
MOD = 10**9+7
dp_1 = 1
dp_2 = 0

for c in input():
    t_1 = (dp_1*(int(c)+1)) % MOD
    t_2 = (dp_2*3+dp_1*int(c)) % MOD
    dp_1 = t_1
    dp_2 = t_2

print((dp_1+dp_2) % MOD)

Solution (Python):


import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

MOD = 10**9+7


def solve3():
    L = input()[:-1]
    
    dp_1 = 1
    dp_2 = 0

    for c in L:
        t_1 = (dp_1*(int(c)+1)) % MOD
        t_2 = (dp_2*3+dp_1*int(c)) % MOD
        dp_1 = t_1
        dp_2 = t_2

    print((dp_1+dp_2) % MOD)


solve3()

Solution (Python):


import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

MOD = 10**9+7


def solve3():
    L = input()[:-1]
    
    dp = [0]*2
    dp[0] = 1  

    for c in L:
        tmp = [0]*2
        tmp[0] = (dp[0]*(int(c)+1)) % MOD
        tmp[1] = (dp[1]*3+dp[0]*int(c)) % MOD
        dp = tmp

    print(sum(dp) % MOD)


solve3()

Solution (Python):


import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

MOD = 10**9+7


def solve2():
    L = input()[:-1]
    int_L = int(L, 2)
    ans = 1  
    for l in range(1, int_L+1):  
        bit_cnt = bin(l).count("1")  
        ans += pow(2, bit_cnt, MOD)
        ans %= MOD
    print(ans)


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

    for i, c in enumerate(L):
        dp[i+1][0] = dp[i][0]*(int(c)+1)
        dp[i+1][1] = dp[i][1]*3+dp[i][0]*int(c)

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


solve3()

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

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

Solution (Python):


L = input()
lenL = len(L)
dp1 = [0] * lenL  
dp2 = [0] * lenL  
dp1[0] = 1 
dp2[0] = 2 

mod = 10**9 + 7
for i in range(1,lenL):
    
    dp1[i] = (3 * dp1[i-1]) % mod  
    if L[i] == '1':
        dp2[i] = (dp2[i] + 2 * dp2[i-1]) % mod  
        dp1[i] = (dp1[i] + dp2[i-1]) % mod  
    else:
        dp2[i] = dp2[i-1]  

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

Solution (Python):


L = input()
lenL = len(L)
dp1 = [0] * lenL  
dp2 = [0] * lenL  
dp1[0] = 1 
dp2[0] = 2 

mod = 10**9 + 7
for i in range(1,lenL):
    
    dp1[i] = (3 * dp1[i-1]) % mod  
    if L[i] == '1':
        dp2[i] = (dp2[i] + 2 * dp2[i-1]) % mod  
        dp1[i] = (dp1[i] + dp2[i-1]) % mod  
    else:
        dp2[i] = dp2[i-1]  

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

Solution (Python):


L = input()
lenL = len(L)
dp1 = [0] * lenL  
dp2 = [0] * lenL  
dp1[0] = 1 
dp2[0] = 2 

mod = 10**9 + 7
for i in range(1,len(L)):
    
    dp1[i] = (dp1[i] + 3 * dp1[i-1]) % mod  
    if L[i] == '1':
        dp2[i] = (dp2[i] + 2 * dp2[i-1]) % mod  
        dp1[i] = (dp1[i] + dp2[i-1]) % mod  
    else:
        dp2[i] = (dp2[i] + dp2[i-1]) % mod  

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

Solution (Python):


L = input()
lenL = len(L)
dp1 = [0] * lenL  
dp2 = [0] * lenL  
dp1[0] = 1 
dp2[0] = 2 

mod = 10**9 + 7
for i in range(1,len(L)):
    
    dp1[i] = (dp1[i] + 3 * dp1[i-1]) % mod  
    if L[i] == '1':
        dp2[i] = (dp2[i] + 2 * dp2[i-1]) % mod  
        dp1[i] = (dp1[i] + dp2[i-1]) % mod  
    else:
        dp2[i] = (dp2[i] + dp2[i-1]) % mod  

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

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

dp=[]
for _ in L:
  dp.append([-1,-1])
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] %mod
    dp[i][1] = dp[i-1][1]
  elif L[i] == "1":
    dp[i][0] = (3*dp[i-1][0]+dp[i-1][1]) %mod
    dp[i][1] = 2*dp[i-1][1] %mod
    

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

Solution (Python):

l = str(input())

mod = int(1e9) + 7

dp1 = 0 
dp2 = 1 

for i in l: 
    if i == "0": 
        dp1 = (dp1 * 3) % mod
    else:
        dp1 = (dp1 * 3 + dp2) % mod 
        dp2 = (dp2 * 2) % mod 

res = (dp1 + dp2) % mod 

print(res)

Solution (Python):
MOD = int(1e9) + 7

L = str(input())
dp_k = 0
dp_u = 1

for l in L:
    if l == "0":
        dp_k = (dp_k * 3) % MOD
    else:
        dp_k = (dp_k * 3 + dp_u) % MOD 
        dp_u = (dp_u * 2) % MOD 

print((dp_k + dp_u) % MOD)

Solution (Python):
l = input()
dp1 = [0] * (len(l)+1)
dp2 = [0] * (len(l)+1)
 
dp1[1] = 1
dp2[1] = 2
if l == '1':
  print(3)
  exit()
for i in range(1, len(l)):
  if l[i] == '0':
    dp1[i+1] = 3 * dp1[i]
    dp1[i+1] %= 1000000007
    dp2[i+1] = dp2[i]
  else:
    dp1[i+1] = 3 * dp1[i] + dp2[i]
    dp1[i+1] %= 1000000007
    dp2[i+1] = 2 * dp2[i]
    dp2[i+1] %= 1000000007
print((dp1[len(l)] + dp2[len(l)]) % 1000000007)

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

Solution (Python):



INF = 10**9+7
def ri():
    return int(input())

def rl():
    return list(input().split())

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

def main():
    l = input()

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

    for i, d in enumerate(l[1:]):
        if d == '1':
            dp[i+1][0] = 2*dp[i][0] % INF
            dp[i+1][1] = dp[i][0] % INF + 3*dp[i][1] % INF
        else:
            dp[i+1][0] = dp[i][0] % INF
            dp[i+1][1] = 3*dp[i][1] % INF
    ans = (dp[len(l)-1][0]+dp[len(l)-1][1]) % INF
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
L = input()

MOD = 10**9+7

ans = 0

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

for i in range(n-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
    dp[i+1][0] %= MOD
    dp[i+1][1] %= MOD

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

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

L = input()
N = len(L)

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


for i, num in enumerate(L, 1):
    if num == '1':
        dp[i][0] = dp[i - 1][0] * 2
        dp[i][0] %= MOD

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

Solution (Python):

L=raw_input()
l=len(L)

mod=10**9+7

ans=0
cnt=0	
for i, x in enumerate(L):
	if x=="1":
		nokori_keta=l-i-1
		ans+=pow(2,cnt,mod)*( pow(3,nokori_keta,mod ))
		cnt+=1

t=1
for x in L:
	if x=="1":
		t*=2
		t%=mod

print (ans+t)%mod

Solution (Python):
import sys
input=sys.stdin.readline
from collections import deque
from heapq import heappush,heappop
import re

def int_raw():
    return int(input())
 
def ss_raw():
    return input().split()
 
def ints_raw():
    return tuple(map(int, ss_raw()))


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


DIV = 10**9+7

def ncr(n, r, mod=DIV):
	r = min(r, n-r)
	ret = 1
	for i in range(1, r+1):
		ret = ret * (n-i+1) % mod
		ret = ret * mod_inv(i, mod) % mod
	return ret


def main():
    L = input().rstrip("\n")
    n = len(L)
    dp = [[0]*2 for _ 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)%DIV
            dp[i+1][0] = (dp[i][0]*3+ dp[i][1]) % DIV
        else:
            dp[i+1][1]=dp[i][1]
            dp[i+1][0]=(dp[i][0]*3)%DIV
    return (dp[n][0]+dp[n][1])%DIV

print(main())

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

memo = dict()
memo[0] = 1
def pow3(n):
	if n in memo:
		return memo[n]
	if n%2 == 0:
		tmp = pow3(n//2)
		memo[n] = tmp*tmp%MOD
		return memo[n]
	memo[n] = 3 * pow3(n-1)%MOD
	return memo[n]

def cul(i, p):
	cur = (1<<i)%MOD
	cur *= pow3(p)
	return cur % MOD

def solve(L):
	n = len(L)
	if L == "0":
		return 1
	if not "0" in L:
		return pow3(n)

	num_1 = 0
	pos = []
	for i in range(n):
		if L[i] == "1":
			num_1 += 1
			pos.append(n-i-1)

	ans = (2**num_1)%MOD
	for i, p in enumerate(pos):
		ans += cul(i, p)
		ans %= MOD

	return ans

def main():
	L = input()
	print(solve(L))


if __name__ == '__main__':
	main()

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

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

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

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

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





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

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

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

  dp[0][i+1] += (3 * dp[0][i]) % modulo





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

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

m3=1
m3_list=[]
for i in range(len(L)):
  m3_list.append(m3)
  m3 = (3*m3)%mod                   
m3_list.reverse()
  
sum=0
cnt_2=1
for i in range(len(L)):  
  if L[i] == "1":
    
    sum += cnt_2*m3_list[i]
    sum %= mod
    cnt_2 = (cnt_2*2)%mod
    
sum += cnt_2
sum %= mod
print(sum)

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