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
from io import StringIO
import unittest
import os


sys.setrecursionlimit(999999999)



def resolve(test_def_name=""):
    l_s = list(input())
    ans = 0
    target = 0

    one_cnt = 0
    ans = 0
    for cnt, l in enumerate(l_s, 1):

        if l == "1":
            
            pattern1 = pow(2, one_cnt, 1000000007)
            
            pattern0 = pow(3, len(l_s) - cnt, 1000000007)

            ans += pattern0 * pattern1 % 1000000007
            one_cnt += 1

    
    pattern1 = pow(2, one_cnt, 1000000007)
    
    pattern0 = pow(3, 0, 1000000007)
    ans += pattern0 * pattern1 % 1000000007

    print(ans % 1000000007)



class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """10"""
        output = """5"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """1111111111111111111"""
        output = """162261460"""
        self.assertIO(test_input, output)



if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        
        resolve()

    else:
        
        unittest.main()

Solution (Python):
MOD = 10**9+7
L = input().rstrip()
res = 1
cnt = 0
for s in L:
    res *= 3
    if s=="0":
        res -= pow(2,cnt+1,MOD)
    else:
        cnt += 1
    res %= MOD
print(res)

Solution (Python):
MOD = int(1e9) + 7
M = int(1e9) + 7
L = input()
N = len(L)
dp = [[0] * 2 for i in range(N+5)]
dp[0][0] = 1
for i in range(N):
    nd = int(L[i])
    for j in range(2):
        ni = i+1
        nj = j
        if j == 0:
            if nd == 0:
                dp[ni][nj] = dp[i][j]
            else:
                dp[ni][nj] = (dp[i][j] * 2) % MOD
                dp[ni][1] += dp[i][j]
        else:
            dp[ni][nj] += dp[i][j] * 3
            dp[ni][nj] %= MOD
print((dp[N][0] + dp[N][1]) % MOD)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

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

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    L = S()
    dp = [[0 for _ in range(2)] for ___ in range(len(L) + 1)]
    dp[0][0] = 1

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

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

        
        dp[i+1][1] += dp[i][1]
        if int(L[i]) == 0:
            dp[i+1][0] += dp[i][0]

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

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

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


comb = 1
ans = 0
for i, l in enumerate(L):
  if l == '0':
    continue
  ans += comb * pow(3, ll - i - 1, MOD)
  
  comb *= 2
  comb %= MOD

ans += comb
ans %= MOD
print(ans)

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

L = input()

dp1 = [0]*100010 
dp2 = [0]*100010 
dp1[1], dp2[1] = 1, 2

for i in range(1,len(L)):
    for digit_A, digit_B in [[0,0],[0,1],[1,0]]:
            dp1[i+1] += dp1[i]

            if digit_A + digit_B == int(L[i]):
                dp2[i+1] += dp2[i]
            elif digit_A + digit_B < int(L[i]):
                dp1[i+1] += dp2[i]
            
            dp1[i+1] %= MOD
            dp2[i+1] %= MOD

ans = dp1[len(L)] + dp2[len(L)]
print(ans % MOD)

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

L = input()

dp1 = [0]*100010 
dp2 = [0]*100010 
dp1[1], dp2[1] = 1, 2

for i in range(1,len(L)):
    for digit_A, digit_B in [[0,0],[0,1],[1,0]]:
            dp1[i+1] += dp1[i]

            if digit_A + digit_B == int(L[i]):
                dp2[i+1] += dp2[i]
            elif digit_A + digit_B < int(L[i]):
                dp1[i+1] += dp2[i]
            
            dp1[i+1] %= MOD
            dp2[i+1] %= MOD

ans = dp1[len(L)] + dp2[len(L)]
print(ans % MOD)

Solution (Python):
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue



sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))





def main():
    s = list(input())
    l = len(s)
    dp1 = [0 for _ in range(l + 1)]
    dp2 = [0 for _ in range(l + 1)]
    dp1[0] = 1

    for i in range(l):
        if s[i] == "1":
            dp1[i + 1] = dp1[i] * 2
            dp2[i + 1] = dp1[i] + dp2[i] * 3
        else:
            dp1[i + 1] = dp1[i]
            dp2[i + 1] = dp2[i] * 3
        dp1[i + 1] %= MOD
        dp2[i + 1] %= MOD

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


if __name__ == '__main__':
    main()

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

ans = memo[n]
for i in range(n,0,-1):
    if l[i-1] == 0:
        continue
    ans += memo[i-1]*cnt[i+1]
    ans %= mod
print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



L = input()
n = len(L)

cnt_1 = list(accumulate(map(int, list(L))))

ans = pow(2, cnt_1[-1], mod)
for i in range(n):
	if L[i] == "1":
		ans += pow(2, cnt_1[i]-1, mod) * pow(3, n-i-1, mod) % mod
		ans %= mod

print(ans)

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

Solution (Python):
l = input()
MOD = 10**9 + 7
r = len(l)
res = 0
num=0
for i in range(len(l)):
    tmp = r-i-1
    if(l[i]=="1"):
        res += pow(2,num,MOD) * pow(3,tmp,MOD)
        res%=MOD
        num+=1

res += pow(2,num)
print(res%MOD)

Solution (Python):

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

num = 0
res = 0
n = len(L)
for i in range(n):
    length = n - i - 1
    if L[i] == "1":
        res = (res + pow(2, num, MOD) * pow(3, length, MOD))
        num += 1

res = (res + pow(2, num, MOD)) % MOD
print(res)

Solution (Python):






import sys
input = sys.stdin.readline
sys.setrecursionlimit(500000)

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





S = S()
N = len(S)
data = []
for i in range(N):
  if S[i] == "1":
    data.append(N-1-i)
ans = pow(3,data[-1],MOD)
for i in range(len(data)-1):
  x = data[len(data)-2-i]
  ans *= 2
  ans += pow(3,x,MOD)
  ans %= MOD
ans += pow(2,len(data),MOD)
ans %= MOD
print(ans)

Solution (Python):
L = input()
p = 10**9+7
dp=[[0]*2 for i in range(len(L)+1)]
dp[0][0]=1
for digit, i in enumerate(L):
  
  if L[digit] == "0":
    dp[digit + 1][0] = dp[digit][0]
    dp[digit + 1][1] = dp[digit][1]
  else:
    dp[digit + 1][1] = (dp[digit][0] + dp[digit][1]) % p
  
  if L[digit] == "0":
    dp[digit + 1][1] += dp[digit][1]*2 % p
    dp[digit + 1][1] %= p
  else:
    dp[digit + 1][0] += dp[digit][0]*2 % p
    dp[digit + 1][0] %= p
    dp[digit + 1][1] += dp[digit][1]*2 % p
    dp[digit + 1][1] %= p
ans = (dp[len(L)][0]+dp[len(L)][1]) % p
print(ans)

Solution (Python):
mod = 1000000007

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

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

Solution (Python):
l = input()
ans = 1
cnt = 1
mod = 10 ** 9 + 7
for i in l[::-1]:
    if i == "1":
        ans *= 2
        ans += cnt
        ans %= mod
    cnt *= 3
    cnt %= mod
print(ans)

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

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
from functools import reduce, lru_cache
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

sys.setrecursionlimit(1000000)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

class ModInt:
    def __init__(self, x, MOD=1000000007): self.x, self.MOD = x % MOD, MOD
    def __str__(self): return str(self.x)
    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 * other.inverse()) if isinstance(other, ModInt) else ModInt(self.x * pow(other, self.MOD - 2, self.MOD))
    def __pow__(self, other): return ModInt(pow(self.x, other.x, self.MOD)) if isinstance(other, ModInt) else ModInt(pow(self.x, other, self.MOD))
    def __rsub__(self, other): return ModInt(other.x - self.x) if isinstance(other, ModInt) else ModInt(other - self.x)
    def __rtruediv__(self, other): return ModInt(other.x * other.inverse()) if isinstance(other, ModInt) else ModInt(other * pow(self.x, self.MOD - 2, self.MOD))
    def __rpow__(self, other): return ModInt(pow(other.x, self.x, self.MOD)) if isinstance(other, ModInt) else ModInt(pow(other, self.x, self.MOD))
    __repr__, __radd__, __rmul__ = __str__, __add__, __mul__
    def inverse(self): return pow(self.x, self.MOD - 2, self.MOD)

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    L = S()

    dp1 = [ModInt(0) for _ in  range(len(L) + 1)]
    dp2 = [ModInt(0) for _ in  range(len(L) + 1)]
    dp1[0] = ModInt(1)

    for i, bit in enumerate(L):
        if bit == "0":
            dp1[i+1] = dp1[i]
            dp2[i+1] = 3 * dp2[i]
        else:
            dp1[i+1] = 2 * dp1[i]
            dp2[i+1] = 3 * dp2[i] + dp1[i]
    
    print(dp1[-1] + dp2[-1])



if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
from functools import reduce, lru_cache
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

sys.setrecursionlimit(1000000)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

class ModInt:
    def __init__(self, x, MOD=1000000007):
        self.x = x % MOD
        self.MOD = MOD
    def __str__(self): return str(self.x)
    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 * other.inverse()) if isinstance(other, ModInt) else ModInt(self.x * pow(other, self.MOD - 2, self.MOD))
    def __pow__(self, other): return ModInt(pow(self.x, other.x, self.MOD)) if isinstance(other, ModInt) else ModInt(pow(self.x, other, self.MOD))
    def __rsub__(self, other): return ModInt(other.x - self.x) if isinstance(other, ModInt) else ModInt(other - self.x)
    def __rtruediv__(self, other): return ModInt(other.x * other.inverse()) if isinstance(other, ModInt) else ModInt(other * pow(self.x, self.MOD - 2, self.MOD))
    def __rpow__(self, other): return ModInt(pow(other.x, self.x, self.MOD)) if isinstance(other, ModInt) else ModInt(pow(other, self.x, self.MOD))

    __repr__ = __str__
    __radd__ = __add__
    __rmul__ = __mul__

    def inverse(self): return pow(self.x, self.MOD - 2, self.MOD)

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    L = S()

    ans = ModInt(0, MOD)
    bit_count = 0

    for i, bit in enumerate(L):
        if bit == '0':
            continue

        d = len(L) - (i + 1)
        ans += pow(2, bit_count, MOD) * pow(3, d, MOD)

        bit_count += 1


    ans += pow(2, bit_count, MOD)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

L = rs()

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

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

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

ans = 1
p3 = 1
for i in range(-1, -n-1, -1):
    if s[i] == '1':
        ans = ((ans * 2) % MOD + p3) % MOD
    p3 = (p3 * 3) % MOD
print(ans)

Solution (Python):
l=input()
n=len(l)
mod=pow(10,9)+7
import sys
sys.setrecursionlimit(10**7)

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

Solution (Python):
L = input()
L_bi = L
keta = len(L)
mod = 1000000007

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

for i in range(len(L_bi)):
    for j in range(2):
        if j == 1:
            scale = 2
        else:
            scale = 1
        dp[i+1][0] = (dp[i+1][0] + scale*dp[i][0])%mod
        if int(L_bi[i]) > j:
            dp[i+1][0] = (dp[i+1][0] + scale*dp[i][1])%mod
        elif int(L_bi[i]) == j:
            dp[i+1][1] = (dp[i+1][1] + scale*dp[i][1])%mod
print((dp[len(L_bi)][0]+dp[len(L_bi)][1])%mod)

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

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

Solution (Python):












import sys
readline = sys.stdin.readline

L = readline().rstrip()
keta = len(L)
DIV = 10 ** 9 + 7

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

for i in range(1, keta):
  x = L[i] 
  if x == "1":
    dp[i][0] += dp[i - 1][0] * 2
    dp[i][1] += dp[i - 1][0] * 1
    dp[i][0] %= DIV
    dp[i][1] %= DIV
  else:
    dp[i][0] += dp[i - 1][0] * 1
    dp[i][0] %= DIV
  dp[i][1] += dp[i - 1][1] * 3
  dp[i][1] %= DIV

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

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations

from heapq import heapify,heappop,heappush


from functools import reduce,lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    

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

    for i in range(mk-1):
        li=int(L[-1-i])
        ni=i+1
        for j in range(3):
            for k in range(2):
                cur=dp[i][j][k]
                for ai in range(2):
                    for bi in range(2):
                        
                        if ai^bi!=(ai+bi+k)&1:
                            continue
                    
                        nk=0
                        if (ai+bi+k)>=2:
                            nk=1
                        nj=0
                        if j==2 and li<=ai^bi:
                            nj=2
                        elif j==0 and li<ai^bi:
                            nj=2
                        elif j==1 and li<ai^bi:
                            nj=2
                        elif j==1 and li==ai^bi:
                            nj=1

                        
                        dp[ni][nj][nk]+=cur
                        dp[ni][nj][nk]%=mod

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






if __name__ == "__main__":
    main()

Solution (Python):
L=input()

mod=10**9+7

f=2
nf=1

for c in L[1:]:
    x=int(c)

    if x==1:
        nf=3*nf+f
        f=2*f
    else:
        nf=3*nf
    
    nf%=mod
    f%=mod

print((f+nf)%mod)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

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






L = input()

def digit_dp_2(n):
    l = len(n)

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

    for i in range(l):
        d = int(n[i])

        
        for j in range(2):
            
            for d_j in range(2 if j else d + 1):
                if d_j == 0:
                    dp[i + 1][j | (d_j < d)][d_j] += (dp[i][j][0] + dp[i][j][1])
                    dp[i + 1][j | (d_j < d)][d_j] %= mod
                else:
                    dp[i + 1][j | (d_j < d)][d_j] += 2 * (dp[i][j][0] + dp[i][j][1])
                    dp[i + 1][j | (d_j < d)][d_j] %= mod

    return sum(dp[-1][0]) + sum(dp[-1][1])

print(digit_dp_2(L) % mod)

Solution (Python):
L = input()

N = len(L)
mod = int(1e9 + 7)



dp1 = [0] * N

dp2 = [0] * N


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

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

Solution (Python):
L = input()

N = len(L)
mod = int(1e9 + 7)



dp1 = [0] * N

dp2 = [0] * N


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

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

Solution (Python):
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7
N = readline().decode().rstrip()
L = len(N)
dp = [[0]*2 for _ in range(L+1)]
dp[0][0] = 1
for i in range(L):
    nd = int(N[i])
    if nd == 0:
        dp[i+1][0] = dp[i][0]
        dp[i+1][1] = (3 * dp[i][1]) % MOD
    else:    
        dp[i+1][0] = 2 * dp[i][0] % MOD
        dp[i+1][1] = (3 * dp[i][1] + dp[i][0]) % MOD
print(sum(dp[L])%MOD)

Solution (Python):



L = input()

MOD = 10 ** 9 + 7
MAX = 10 ** 5 + 5
p3 = [None] * MAX


def p3_init():
    p3[0] = 1
    for i in range(1, MAX):
        p3[i] = 3 * p3[i - 1] % MOD


def main():
    p3_init()
    n = len(L)
    w = 1
    ans = 0
    for i in range(n):
        if L[i] == "1":
            
            ans = (ans + w * p3[n - i - 1]) % MOD
            
            w = 2 * w % MOD
    ans = (ans + w) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

L = input()
lenl = len(L)
MOD = 10**9 + 7

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

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

print((dp[0][-1] + dp[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 
dp[0][1] = 0 

for i in range(n):
    if l[i] == '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

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

Solution (Python):
L = input()

mod = 10 ** 9 + 7
n = len(L)
dp1 = 1
dp2 = 0

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

print((dp1 + dp2) % mod)

Solution (Python):
L = input()

mod = 10 ** 9 + 7
n = len(L)
dp1 = 2
dp2 = 1

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

print((dp1 + dp2) % mod)

Solution (Python):
L = input()

mod = 10 ** 9 + 7
n = len(L)
dp1 = 0
dp2 = 0

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

dp1 = (dp1 + pow(2, dp2, mod)) % mod
print(dp1)

Solution (Python):
mod=10**9+7
l=input()
bit=[int(i) for i in l]
m=len(bit)












dp=[[0,0] for i in range(m)]
dp[0]=[1,2]
for i in range(m-1):
    dp[i+1][0]=3*dp[i][0]%mod
    if bit[i+1]==0:
        dp[i+1][1]+=dp[i][1]
        dp[i+1][1]%=mod
    else:
        dp[i+1][0]+=dp[i][1]
        dp[i+1][1]+=(2*dp[i][1])
        dp[i+1][0]%=mod
        dp[i+1][1]%=mod
print(sum(dp[m-1])%mod)

Solution (Python):
L = input()
l = len(L)
dp = [[0]*2 for _ in range(100002)]



dp[0][0] = 1
mod = 10**9+7

for i in range(l):
  n = L[i]

  if n == '1':
    dp[i+1][0] += dp[i][0]*2 
    dp[i+1][0] %= mod 

    dp[i+1][1] += dp[i][1]*3 + dp[i][0]
    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[l][0]+dp[l][1])%mod)

Solution (Python):
L = input()
l = len(L)
dp = [[0]*2 for _ in range(100005)]



dp[0][0] = 1
mod = 10**9+7

for i in range(l):
  n = L[i]
  
  if n == "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 n == "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

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

Solution (Python):
import sys

L = sys.stdin.readline().strip()
mod = 10**9 + 7
ls = len(L)


dp = [[0 for i in (True, False)] for _ in range(ls)]

dp[0][False] = 2
dp[0][True] = 1

for i in range(ls-1):
    for j in (True, False):
        if L[i+1] == "1":
            dp[i+1][True] = 3 * dp[i][True] + 1 * dp[i][False]
            dp[i+1][False] = 2 * dp[i][False]
        else:
            dp[i+1][True] = 3 * dp[i][True]
            
            dp[i+1][False] = 1 * dp[i][False]
        dp[i+1][True] %= mod
        dp[i+1][False] %= mod


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