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

-----Constraints-----
 - L is given in base two, without leading zeros.
 - 1 \leq L < 2^{100\ 001}

-----Input-----
Input is given from Standard Input in the following format:
L

-----Output-----
Print the number of pairs (a, b) that satisfy the conditions, modulo 10^9 + 7.

-----Sample Input-----
10

-----Sample Output-----
5

Five pairs (a, b) satisfy the conditions: (0, 0), (0, 1), (1, 0), (0, 2) and (2, 0).

Difficulty: interview

Starter code:

Solutions:
MOD = 10**9 + 7

s = str(input())

dp0 = [0] * (len(s)+1)
dp1 = [0] * (len(s)+1)
dp0[0] = 1

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

answer = dp0[-1] + dp1[-1]
if answer >= MOD:
    answer -= MOD
print(answer)


import sys

import numba as nb
import numpy as np

input = sys.stdin.readline
P = 10 ** 9 + 7


@nb.njit("i8(i8[:],i8)", cache=True)
def solve(L, N):
    dp = np.zeros(shape=(N + 1, 2), dtype=np.int64)
    dp[0][0] = 1
    for i in range(N):
        n = L[i]
        for j in range(2):
            max_d = 1 if j == 1 else n
            for d in range(max_d + 1):
                next_j = int(j or d < n)
                dp[i + 1][next_j] += (d + 1) * dp[i][j]

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

    return (dp[N][0] + dp[N][1]) % P


def main():
    L = np.array(list(map(int, input().rstrip())), dtype=np.int64)

    N = len(L)
    ans = solve(L, N)

    print(ans)


def __starting_point():
    main()

__starting_point()

l=input()
n=len(l)
mod=pow(10,9)+7
import sys
sys.setrecursionlimit(10**7)
#dp1,dp2=[0]*n,[0]*n
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)

L = input()
n = len(L)
mod = 1000000007
dp = [[0,0] for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    dp[i+1][1] += 3*dp[i][1]%mod
    dp[i+1][1] %= mod
    if L[i] == "1":
        dp[i+1][0] += 2*dp[i][0]
        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
# for i in range(n+1): print(dp[i])
print(ans)

l = list(map(int, input()))
mod = 10 ** 9 + 7

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

for e in l:
    dp_new = [[0] * 2 for _ in range(2)]
    for now in range(2):
        for prev in range(2):
            # same -> same
            if now == e:
                dp_new[now][1] += dp[prev][1] * (now + 1)

            # same -> small
            if now == 0 and e == 1:
                dp_new[now][0] += dp[prev][1]

            # small -> small
            dp_new[now][0] += dp[prev][0] * (now + 1)

    dp = dp_new
    for i in range(2):
        for j in range(2):
            dp[i][j] %= mod

ans = 0
for row in dp:
    ans += sum(row)
    ans %= mod

print(ans)


"""

AtCoder Beginner Contest 129  E - Sum Equals Xor

XORは桁上がりがないので、A xor B がA+Bより大きくなることはない（最大でもA+Bまで）
なので、 A xor B = A + B が成立するのは、AとBを二進数でみたときに、両方1が立っているbitがないこと。

桁DPの文脈で考えると、
dp1,2[i] : AやBの左からi文字目までを決めたときに、
・dp2 : その時点でのA+BがL以下になることがわかっている（左からi番目までについて、A+Bのp桁目は0だが、Lのp桁目は1、みたいなのが存在する（先頭～p-1までは一致））AとBの組の個数
・dp1 : その時点ではA+BがL以下になるか分からないAとBの組の個数（その時点まではLのi桁目までと一致する組の数）



遷移について、
Lのi桁目が
・0の場合
 - dp1 : dp2から遷移するとL以下になることが確定するので、dp2から遷移してくることはない＆A+Bのiビット目に1が立つとLを上回るので、0になるしかなく、i桁目は両方0の１通りで遷移
 - dp2 : dp1から遷移してきてi番目に0をいれても、L以下になるか確定しないので、dp1からの遷移はない。一方で。dp2から遷移してくる場合、既にL以下であることが確定しているので、A,B = 1,1以外の３パターンをとれる
・1の場合
 - dp1 : dp2から遷移してくるのを考えると、dp2の時点で既にL以下になるのが確定しているので、dp2からは遷移できない。一方で、dp1から遷移してくる場合、i桁目までLと同じになるので、A,Bの一方が1で他方が0の２通りをとれる
 - dp2 : dp1から遷移して A,B=0,0 をとればL以下が確定＆dp2から遷移して 1,1 以外の3通りの遷移

"""


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

dp1 = [0] * (N+1)
dp2 = [0] * (N+1)
dp1[0] = 1


for i in range(N):
    if L[i] == "0":
        dp1[i+1] = dp1[i] # (0,0)
        dp2[i+1] = dp2[i] * 3 # (1,1)以外の3つ
    else:
        dp1[i+1] = dp1[i] * 2 # (1,0), (0,1)
        dp2[i+1] = dp2[i] * 3 + dp1[i] # dp2から遷移してくる場合は(1,1)以外の3つ、dp1から遷移してくる場合は1にならないとよいので(0,0)

    dp1[i+1] %= MOD
    dp2[i+1] %= MOD

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

S=input()
c=len(S)
mod=1000000007
p=1
ans=pow(3,c-1,mod)
for i in range(1,c):
  if S[i]=="1":
    ans+=pow(2,p,mod)*pow(3,c-i-1,mod)
    p+=1
print((ans+pow(2,p,mod))%mod)

def main():
  s=input()
  n=len(s)
  mod=10**9+7
  dp=[[0]*2 for i in range(10**5+5)]
  
  dp[0][0]=1
  for i in range(n):
    # a+b=0
    if s[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

    # a+b=1
    if s[i]=='0':
      dp[i+1][1]+=dp[i][1]*2; dp[i+1][1]%=mod
    else:
      dp[i+1][0]+=dp[i][0]*2; dp[i+1][0]%=mod
      dp[i+1][1]+=dp[i][1]*2; dp[i+1][1]%=mod

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

def __starting_point():
  main()
__starting_point()

MOD = 10 ** 9 + 7
L = input()
N = len(L)
total = 0
one_count = 0
pow2, pow3 = [1], [1]
p2, p3 = 1, 1
for i in range(N):
    p2 = p2 * 2 % MOD
    p3 = p3 * 3 % MOD
    pow2.append(p2)
    pow3.append(p3)
for i in range(N):
    if L[i] == "1":
        total = (total + pow2[one_count] * pow3[N - i - 1]) % MOD
        one_count += 1
print(((total + pow2[one_count] * pow3[N - i - 1]) % MOD))


MOD = 10 ** 9 + 7

L = list(input())

N = len(L)

OK = [0] * (N + 1)
JUST = [0] * (N + 1)
JUST[0] = 1

for i in range(N):
    if L[i] == '1':
        OK[i + 1] = (OK[i] * 3 + JUST[i]) % MOD
        JUST[i + 1] = (JUST[i] * 2) % MOD
    else:
        OK[i + 1] = (OK[i] * 3) % MOD
        JUST[i + 1] = (JUST[i]) % MOD

print ((OK[-1] + JUST[-1]) % MOD)

L=input()
N=len(L)
dp=[[0,0]for _ in range(N)]
dp[0][0]=1 #以下が確定（0）
dp[0][1]=2 #以下が確定してない（1,0）と逆
mod=10**9+7
for i in range(1,N):
  #以下モードは3倍に配給パターンが増える
  dp[i][0]+=3*dp[i-1][0]
  dp[i][0]%=mod
  if L[i]=='0':
    #(0,0)を配給し、そのまま
    dp[i][1]+=dp[i-1][1]
  else:
    #(0,0)を配給すれば、以下モードに移る
    dp[i][0]+=dp[i-1][1]
    #(1,0)(0,1)を配給する
    dp[i][1]+=dp[i-1][1]*2
  dp[i][0]%=mod
  dp[i][1]%=mod
print(sum(dp[-1])%mod)

s=input()
n=len(s)
mod=10**9+7
dp=[[0]*2 for i in range(n+5)]
# dp[i][j]
#  : 右からi桁目までチェックしたときに
#     j=0:Lと一致している
#     j=1:L未満であることが確定している

dp[0][0]=1
for i in range(n):
  # i桁目がa+b=0のケース（つまりi桁目はa=b=0）
  if s[i]=='0':
    dp[i+1][0]=dp[i][0]
    dp[i+1][1]=dp[i][1]
  else:
    dp[i+1][1]=(dp[i][1]+dp[i][0])%mod
    
  # i桁目がa+b=1のケース（つまりi桁目はa=0,b=1 or a=1,b=0）
  if s[i]=='0':
    dp[i+1][1]+=dp[i][1]*2
    dp[i+1][1]%=mod
  else:
    dp[i+1][0]+=dp[i][0]*2
    dp[i+1][0]%=mod
    dp[i+1][1]+=dp[i][1]*2
    dp[i+1][1]%=mod
  
print((dp[n][0]+dp[n][1])%mod)

import sys

input = sys.stdin.readline
P = 10 ** 9 + 7


def solve(L, N):
    dp = [[0, 0] for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(N):
        n = L[i]
        for j in range(2):
            max_d = 1 if j == 1 else n
            for d in range(max_d + 1):
                next_j = int(j or d < n)
                dp[i + 1][next_j] += (d + 1) * dp[i][j]

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

    return (dp[N][0] + dp[N][1]) % P


def main():
    L = list(map(int, input().rstrip()))

    N = len(L)
    ans = solve(L, N)

    print(ans)


def __starting_point():
    main()

__starting_point()

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(200000)

MOD = 1000000007  # type: int

def h(L, i):
    return pow(3, len(L)-i, MOD)

def g(L, i):
    if len(L) == i:
        return 1
    if L[i] == '1':
        return ((2 * g(L, i+1)) % MOD + h(L, i+1)) % MOD
    return g(L, i+1)

def solve(L: str):
    return g(L, 0)

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    L = next(tokens)  # type: str
    print((solve(L)))

def test():
    import doctest
    doctest.testmod()

def __starting_point():
    #test()
    main()

__starting_point()

L = input()

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

# 桁DP
# a+b <= N 確定
dp1 = [0] * N
# a+b <= N 未確定
dp2 = [0] * N

# L[0] == 1なので、初期値が決まる（はず）
dp1[0] = 1 # (A0,B0) = (0,0)
dp2[0] = 2 # (A0,B0) = (0,1), (1,0)

for i in range(1,N):
  dp1[i] += dp1[i-1] * 3 # (1,1)以外の3パターン
  dp1[i] %= mod
  if L[i] == '1':
    dp1[i] += dp2[i-1] # (0,0)
    dp2[i] += dp2[i-1] * 2 # (1,0),(0,1)
  else:
    # L[i] == '0'
    dp2[i] += dp2[i-1] # (0,0)
  dp1[i] %= mod
  dp2[i] %= mod
  
print((dp1[N-1] + dp2[N-1]) % mod)

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

L=str(input())
ls=len(L)
cnt=0
ans=0
MOD=10**9+7
for i in range(ls):
    if L[i]=="1":
        tmp=pow(3,ls-(i+1),MOD)*pow(2,cnt,MOD)
        tmp%=MOD
        ans+=tmp
        cnt+=1
ans+=pow(2,cnt,MOD)
print(ans%MOD)

s=input()[::-1]
n=len(s)
mod=10**9+7
dp=[[0]*2 for i in range(n+5)]
# dp[i][j]
#  : 左からi桁目までチェックしたときに
#     j=0:この桁まではLと一致している
#     j=1:この桁までですでにL未満であることが確定している

dp[n][0]=1
for i in reversed(range(n)):
  # i桁目がa+b=0のケース（つまりi桁目はa=b=0）
  if s[i]=='0':
    dp[i][0]=dp[i+1][0] # j=0はコピー（満たす答えの数はa=b=0の1組だけなので増えない）
    dp[i][1]=dp[i+1][1] # j=1はコピー（満たす答えの数はa=b=0の1組だけなので増えない）
  else:
    dp[i][1]=(dp[i+1][1]+dp[i+1][0])%mod # a+b<lが確定する
    
  # i桁目がa+b=1のケース（つまりi桁目はa=0,b=1 or a=1,b=0）
  if s[i]=='0':
    dp[i][1]+=dp[i+1][1]*2 # j=0のCaseだとa+b>lになるので加算しない
    dp[i][1]%=mod
  else:
    dp[i][0]+=dp[i+1][0]*2 # j=0は2倍をコピー（満たす答えの数の組合せが2組なので）
    dp[i][0]%=mod
    dp[i][1]+=dp[i+1][1]*2
    dp[i][1]%=mod
  
print((dp[0][0]+dp[0][1])%mod)

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)

mod=10**9+7

s=input()
n=len(s)

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

dp[0][0] =1

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

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

L = input()
l = len(L)
mod = 10**9 + 7
ans = 1  # (0,0)

d = dict()


def modpow(x, n, mod):
    if x not in d:
        d[x] = [1]
    l = len(d[x])
    ret = d[x][-1]
    for i in range(l, n+1):
        ret *= x
        ret %= mod
        d[x].append(ret)
    return(d[x][n])


ans = modpow(3, l, mod)

r = 0
count = 0

for i in range(l):
    if L[i] == '0':
        r = modpow(3, l-i-1, mod) * modpow(2, count, mod) * 2
        ans -= r
        ans %= mod
    else:
        count += 1
print(ans)


# coding: utf-8
# Your code here!
L=input()

N=len(L)

dp=[[0 for i in range(2)] for j in range(N)]
dp[0][0]=1
dp[0][1]=2
#print(dp)

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


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



import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    L = readline().strip()

    eq, less = 2, 1
    for d in L[1:]:
        if d == '1':
            less = (eq + 3 * less) % MOD
            eq = 2 * eq % MOD
        else:
            less = 3 * less % MOD

    print(((eq + less) % MOD))
    return


def __starting_point():
    main()

__starting_point()

MOD = 10 ** 9 + 7
L = input()
N = len(L)
total = 0
one_count = 0
p3 = [1] * N
for i in range(1, N):
    p3[i] = p3[i - 1] * 3 % MOD
p2 = 1
for i in range(N):
    if L[i] == "1":
        total = (total + p2 * p3[N - i - 1]) % MOD
        p2 = p2 * 2 % MOD
print((total + p2 * p3[N - i - 1]) % MOD)

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    L = input()
    n = len(L)

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

    res += pow(2, cnt, mod)
    print((res % mod))


def resolve2():
    """
    桁DP
    """
    L = input().rstrip()
    n = len(L)

    # dp[i][0]:Lを上からi桁目まで見た時、Lと一致するような組み合わせ
    # dp[i][1]:Lを上からi桁目まで見た時、L未満になるような組み合わせ
    dp = [[0] * 2 for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(1, n + 1):
        if L[i - 1] == "0":
            # 今見ている桁が0でありそれ以前の数値がLと一致していれば、i桁目まで一致する条件にあてはまる組み合わせは(0,0)のみ
            dp[i][0] = dp[i - 1][0]
            # 今見ている桁が0でありそれ以前の数値がL未満であれば、どの組み合わせでもL未満になる(0,0)(0,1)(1,0)
            dp[i][1] = (dp[i - 1][1] * 3) % mod
        else:
            # 今見ている桁が1でありそれ以前の数値がLと一致していれば、i桁目まで一致する条件にあてはまる組み合わせは(0,1),(1,0)のみ
            dp[i][0] = (dp[i - 1][0] * 2) % mod
            # 今見ている桁が1でありそれ以前の数値がL未満であれば、どの組み合わせでもL未満になる(0,0)(0,1)(1,0)
            # 今見ている桁が1でありそれ以前の数値が一致していれば、L未満になる組み合わせは(0,0)のみ
            dp[i][1] = (dp[i - 1][1] * 3 + dp[i - 1][0]) % mod

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


def __starting_point():
    resolve2()

__starting_point()

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

from sys import stdin
def main():
    #入力
    readline=stdin.readline
    L=readline().strip()
    n=len(L)
    mod=10**9+7

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

    print((dpF[n]+dpT[n])%mod)

def __starting_point():
    main()
__starting_point()

import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
L = input()

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

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



def main():
  L = str(input())
  dp = [[0, 0] for _ in range(len(L))]
  dp[0][0] = 1
  dp[0][1] = 2
  MOD = 10**9 + 7
  for i in range(1, len(L)):
    if L[i] == '1':
      dp[i][0] = 3*dp[i-1][0] + dp[i-1][1]
      dp[i][0] %= MOD
      dp[i][1] = 2*dp[i-1][1]
      dp[i][1] %= MOD
    else:
      dp[i][0] = 3*dp[i-1][0]
      dp[i][0] %= MOD
      dp[i][1] = dp[i-1][1]
  print((dp[-1][0] + dp[-1][1])%MOD)

def __starting_point():
  main()
__starting_point()

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)

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

l = read().rstrip().decode()
n = len(l)
mod = 10 ** 9 + 7
dp = [[0, 0] for _ in range(n)]
dp[0] = [1, 2]
for i, check in enumerate(l[1:]):
    i += 1
    dp[i][0] = dp[i - 1][0] * 3
    dp[i][1] = dp[i - 1][1]
    if check == '1':
        dp[i][0] += dp[i - 1][1]
        dp[i][1] += dp[i - 1][1]
    dp[i][0] %= mod
    dp[i][1] %= mod
print((sum(dp[-1]) % mod))


L = input()
l = len(L)
dp = [[0]*2 for _ in range(100002)]
# dp[i][smaller]: i桁目までみる　未満なら1
# dp[i][1] : i桁目までみて、a, bどちらもL未満
# dp[i][0] : i桁目までみて、a+b = L
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)

l = list(map(int, input()))
mod = 10 ** 9 + 7

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

for e in l:
    dp_new = [[0] * 2 for _ in range(2)]
    for i in range(2):
        # same -> same
        if i == e:
            dp_new[i][1] += (dp[0][1] + dp[1][1]) * (1 + i)

        # same -> small
        if i == 0 and e == 1:
            dp_new[0][0] += dp[0][1] + dp[1][1]

        # small -> small
        dp_new[i][0] += (dp[0][0] + dp[1][0]) * (1 + i)

    dp = dp_new
    for i in range(2):
        for j in range(2):
            dp[i][j] %= mod

ans = 0
for row in dp:
    ans += sum(row)
    ans %= mod

print(ans)


L   = list(input())
dp  = [[0 for _ in range(2)] for _ in range(100005)]
MOD = 10**9+7

dp[0][0] = 1

for i,l in enumerate(L,1):
  if l=='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((dp[i][0] + dp[i][1]) % MOD)

import numpy as np

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

DP = np.zeros((len(L)+1, 2), int)
DP[0][0] = 1

for i in range(len(L)):
    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] %= mod

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

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    L = SI()
    keta = len(L)

    def rec(n):
        if n == 1:
            return 3 if L[keta - n] == "1" else 1

        if L[keta - n] == "1":
            return (pow(3, (n-1), MOD) + rec(n-1) * 2) % MOD
        else:
            return rec(n-1) % MOD

    print(rec(keta))


def __starting_point():
    main()
__starting_point()

MOD = 10 ** 9 + 7
L = input()
N = len(L)
p3 = [1] * N
for i in range(1, N):
    p3[i] = p3[i - 1] * 3 % MOD
p2 = 1
total = 0
for i in range(N):
    if L[i] == "1":
        total = (total + p2 * p3[N - i - 1]) % MOD
        p2 = p2 * 2 % MOD
print((total + p2 * p3[N - i - 1]) % MOD)

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

ans = 0
t1 = 0
for i in range(ll):
    if l[i] == "0":
        continue
    ans = (ans+pow(2,t1,mod)*pow(3,ll-i-1,mod)%mod)%mod
    t1 += 1

ans = (ans+pow(2,t1,mod))%mod

print(ans)


L = input()
ll = len(L)
MOD = 10**9 + 7
#[*2 if 1][*1 if 1][*3]

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)



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


def main():
    l = list(input())
    n = len(l)
    dp = [[0,0] for _ in range(n+1)]
    dp[0][1] = 1
    for i in range(n):
        dp[i+1][0] += dp[i][0]*3
        if l[i] == '1':
            dp[i+1][1] += dp[i][1]*2
            dp[i+1][0] += dp[i][1]
        else:
            dp[i+1][1] += dp[i][1]
        dp[i+1][0] %= 10**9+7
        dp[i+1][1] %= 10**9+7
    print(sum(dp[n])%(10**9+7))

def __starting_point():
    main()
__starting_point()

#!python3

# input
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":
            # 両方0にする場合
            ans = (ans + w * p3[n - i - 1]) % MOD
            # 片方1にする場合
            w = 2 * w % MOD
    ans = (ans + w) % MOD
    print(ans)


def __starting_point():
    main()

__starting_point()

import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


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


def main():
    L = input()
    N = len(L)
    # a + b が小さいのが確定
    dp_1 = [0] * N
    # a + b が大きいのか小さいのかわからない
    dp_2 = [0] * N

    dp_1[0] = 1
    dp_2[0] = 2

    for i in range(1, N):
        if L[i] == "1":
            # (1, 0), (0, 1)の組み合わせで，a+bのi桁目が1
            dp_2[i] = dp_2[i - 1] * 2

            dp_1[i] = dp_2[i - 1] + dp_1[i - 1] * 3

            dp_2[i] %= MOD
            dp_1[i] %= MOD
        else:
            # (1, 0), (0, 1)の組み合わせで，a+bのi桁目が1
            dp_2[i] = dp_2[i - 1]

            dp_1[i] = dp_1[i - 1] * 3

            dp_2[i] %= MOD
            dp_1[i] %= MOD

    ans = dp_1[-1] + dp_2[-1]
    ans %= MOD
    print(ans)


def __starting_point():
    main()

__starting_point()

L = list(input())
N = len(L)
if '0' not in L:
    L = ['1'] + ['0']*N
    N += 1
else:
    for i in range(N):
        t = L[N-i-1]
        if t == '0':
            L[N-i-1] = '1'
            break
        else:
            L[N-i-1] = '0'
res = 0
MOD = 10**9+7
buff = 1
for d, char in enumerate(L):
    if char == '1':
        res = (res + buff * pow(3, N-1-d, MOD))%MOD
        buff = (2 * buff) % MOD
print(res)



s=input()
ans=1
ans2=1
for i in range(len(s)):
  if s[len(s)-1-i]=='1':
    ans=(ans*2+ans2)%(10**9+7)
  ans2=(ans2*3)%(10**9+7)
print(ans)

"""

AtCoder Beginner Contest 129  E - Sum Equals Xor

XORは桁上がりがないので、A xor B がA+Bより大きくなることはない（最大でもA+Bまで）
なので、 A xor B = A + B が成立するのは、AとBを二進数でみたときに、両方1が立っているbitがないこと。

桁DPの文脈で考えると、
dp1,2[i] : AやBの左からi文字目までを決めたときに、
・dp2 : その時点でのA+BがL以下になることがわかっている（左からi番目までについて、A+Bのp桁目は0だが、Lのp桁目は1、みたいなのが存在する（先頭～p-1までは一致してもしなくてもOK））AとBの組の個数
・dp1 : その時点ではA+BがL以下になるか分からないAとBの組の個数（その時点まではLのi桁目までと一致する組の数）



遷移について、
Lのi桁目が
・0の場合
 - dp1 : dp2から遷移するとL以下になることが確定するので、dp2から遷移してくることはない＆A+Bのiビット目に1が立つとLを上回るので、0になるしかなく、i桁目は両方0の１通りで遷移
 - dp2 : dp1から遷移してきてi番目に0をいれても、L以下になるか確定しないので、dp1からの遷移はない。一方で。dp2から遷移してくる場合、既にL以下であることが確定しているので、A,B = 1,1以外の３パターンをとれる
・1の場合
 - dp1 : dp2から遷移してくるのを考えると、dp2の時点で既にL以下になるのが確定しているので、dp2からは遷移できない。一方で、dp1から遷移してくる場合、i桁目までLと同じになるので、A,Bの一方が1で他方が0の２通りをとれる
 - dp2 : dp1から遷移して A,B=0,0 をとればL以下が確定＆dp2から遷移して 1,1 以外の3通りの遷移

"""


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

dp1 = [0] * (N+1)
dp2 = [0] * (N+1)
dp1[0] = 1


for i in range(N):
    if L[i] == "0":
        dp1[i+1] = dp1[i] # (0,0)
        dp2[i+1] = dp2[i] * 3 # (1,1)以外の3つ
    else:
        dp1[i+1] = dp1[i] * 2 # (1,0), (0,1)
        dp2[i+1] = dp2[i] * 3 + dp1[i] # dp2から遷移してくる場合は(1,1)以外の3つ、dp1から遷移してくる場合は1にならないとよいので(0,0)

    dp1[i+1] %= MOD
    dp2[i+1] %= MOD

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

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)

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

dpT = [0]*N
dpF = [0]*N

dpT[0] = 1
dpF[0] = 2

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

print(((dpT[-1]+dpF[-1])%mod))
#print(dpT, dpF)


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

def __starting_point():
    main()

__starting_point()

l = list(map(int, input()))
mod = 10 ** 9 + 7

ln = len(l)
dp = [0] * 2
dp[1] = 1

for e in l:
    dp_new = [0] * 2
    # exact -> exact
    dp_new[1] += dp[1] * (e + 1)

    # exact -> small
    if e == 1:
        dp_new[0] += dp[1]

    # small -> small
    dp_new[0] += dp[0] * 3

    dp = dp_new
    for i in range(2):
        dp[i] %= mod

ans = sum(dp) % mod

print(ans)


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



N=[int(i) for i in L]
keta=len(N)
dp=[[0 for i in range(2)] for j in range(keta+1)]
dp[0][0] = 1
#dp[0][0][1] =0
#dp[0][1][0] =0
#dp[0][1][1] =0

for i in range(keta):
    for smaller in [0,1]:
        if 1:
            for x in range(2 if smaller else (N[i]+1)):
                dp[i + 1][smaller | ((x == 0)&(N[i]==1))]+= dp[i][smaller]*(2 if x==1 else 1)
                dp[i + 1][smaller | ((x == 0)&(N[i]==1))] %=mod
print(((dp[keta][0]+ dp[keta][1])%mod))


L = input()
l = len(L)
dp = [[0]*2 for _ in range(100005)]
# dp[i][smaller]: i桁目までみる　未満なら1
# dp[i][1] : i桁目までみて、a, bどちらもL未満
# dp[i][0] : i桁目までみて、a+b = L
dp[0][0] = 1
mod = 10**9+7

for i in range(l):
  n = L[i]
  # a + b = 0
  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

  # a + b = 1
  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))




L = str(input())
ls = len(L)
cnt = 0
ans = 0
MOD = 10**9+7
for i in range(ls):
    if L[i] == "1":
        tmp = pow(3, ls-(i+1), MOD)*pow(2, cnt, MOD)
        tmp %= MOD
        ans += tmp
        cnt += 1
ans += pow(2, cnt, MOD)
print((ans % MOD))


L = input()
n = len(L)
csum_1 = [0] * n
csum_0 = [0] * n
now1 = 0
now0 = 0
for i in range(n):
    if L[i] == '1':
        now1 += 1
    else:
        now0 += 1
    csum_1[i] = now1
    csum_0[i] = now0

mod = 10**9+7
ans = 0
# iは、「最初にL[i]=1かつai=0かつbi=0となるindex」
for i in range(n):
    if L[i] == '1':
        p = 1
        # 自分より左側の0の度に2パターン増加
        if i >= 1:
            p *= pow(2,csum_1[i-1],mod)
        #print(p)
        # 自分より右側はどの桁も3パターン増加
        p *= pow(3,n-i-1,mod)
        #print(p)
        ans += p
        ans %= mod
# L=a+bの場合
p = pow(2,csum_1[-1],mod)
#print(p)
ans = (ans+p)%mod
print(ans)

import sys

sys.setrecursionlimit(10 ** 7)

f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    L = input()
    n = len(L)

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

    res += pow(2, cnt, mod)
    print((res % mod))


def __starting_point():
    resolve()

__starting_point()

MOD = 10 ** 9 + 7
INF = 10 ** 11
import sys
sys.setrecursionlimit(100000000)

def main():
    L = input()
    dp = [[0]*2 for _ in range(len(L) + 1)]
    
    dp[0][0] = 1
    for i in range(len(L)):
        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
    print((sum(dp[-1])%MOD))
def __starting_point():
    main()

__starting_point()


L = input()
lenl = len(L)
MOD = 10**9 + 7
# dp[is未満][bit]
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))


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

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

dp = [[0,0] for i in range(N+1)]
dp[0][0] = 1
for i,a in enumerate(L):
    a = int(a)
    for less in range(2):
        for d in range(2):
            if less==0 and d > a: continue
            nl = int(less or d < a)
            dp[i+1][nl] += dp[i][less] * (d+1)
    dp[i+1][0] %= MOD
    dp[i+1][1] %= MOD

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

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

def pow_mod(x, y, mod=10**9 + 7):
    if y == 0:
        return 1
    res = 1
    for i in range(y.bit_length()):
        if y & (1 << i):
            res *= x
            res %= mod
        x *= x
        x %= mod
    return res


def calc(r):
    if r <= 1:
        return 3
    return pow_mod(3, r-1) * 2

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

count = [0] * (n+1)
for i in range(1, n+1):
    count[i] = calc(i) + count[i-1]

ans = 0
cnt = 0
u = n
for i in range(n):
    u -= 1
    if i == n-1:
        if l[i] == "1":
            ans += 3 * pow_mod(2, cnt) % mod
            ans %= mod
        else:
            ans += pow_mod(2, cnt) % mod
            ans %= mod
        continue
    if l[i] == "1":
        # 0
        ans += count[u] % mod * pow_mod(2, cnt) % mod
        ans %= mod
        # 1
        cnt += 1
        pass
    else:
        pass

print((ans%mod))





import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, 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
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(): return list(map(int, input().split()))
def ZIP(n): return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

L = input()

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

for i in range(len(L)):
	nd = int(L[i])
	ni = i+1
	for a in range(2):
		for b in range(2):
			if a == b == 1:
				continue
			for k in range(2):
				nk = k

				if nk == 0:  # 未確定
					if nd == 1 and a == b == 0:
						nk = 1
					if nd == 0 and a | b:  # 超える
						continue

				dp[ni][nk] += dp[i][k]
				dp[ni][nk] %= mod

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


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

S = input()
L = len(S)
mod = 10**9+7
dp_c = [0] * L
dp_u = [0] * L
dp_c[0] = 1
dp_u[0] = 2

for i in range(1,L):
    if S[i] == "1":
        dp_c[i] = dp_c[i-1] * 3 + dp_u[i-1]
        dp_u[i] = dp_u[i-1] * 2
    else:
        dp_c[i] = dp_c[i-1] * 3
        dp_u[i] = dp_u[i-1] * 1
    dp_c[i] %= mod
    dp_u[i] %= mod

ans = (dp_c[-1] + dp_u[-1]) % mod
print(ans)


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

#a + b = a xor b を満たすのは a, b の bit が一つも被っていないとき
ans = 1
three = [1] * (len(L) + 1)
for i in range(len(L)):
  ans *= 3
  ans %= mod
  three[i + 1] = ans
  
#print(three)
x = 1
for i in range(len(L)):
  if L[i] == "0":
    y = x * 2
    #print(three[len(L) - i - 1], y, i)
    y *= three[len(L) - i - 1]
    #print(y)
    #y %= mod
    ans -= y
    ans %= mod
  else:
    x *= 2
    x %= mod
    
print(ans)    




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

eq = 1
less = 0
for n in L:
    if n == '1':
        eq, less = eq * 2, eq + less * 3
    else:
        less = less * 3
    eq %= MOD
    less %= MOD

print(((eq + less) % MOD))


# 各桁について3通りある
# (0,0) (1,0) (0,1)
# 3 ** 桁数すればよいのだが、たとえば100以下の数で101は選べないので、
# 桁DPで処理
# ・未満でない->未満でない : 1のときは2通り(1,0) (0,1)
# ・未満でない->未満でない : 0の時は1通り(0,0)
# ・未満でない->未満である : 1の時は1通り(0,0)
# ・未満でない->未満である : 0の時は0通り（未満にできない）
# ・未満である : 1でも0でも3通り(1,0)(0,1)(0,0)

# dp[i][smaller] = 場合の数

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 # 最初の桁は必ず1なので2通り
dp[0][1] = 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)

L = str(input())
ls = len(L)
cnt = 0
ans = 0
MOD = 10**9+7
dp = [[0, 0] for i in range(ls+1)]
dp[0][0] = 1
for i in range(ls):
    dp[i+1][1] += 3*dp[i][1]
    if L[i] == "1":
        dp[i+1][1] += dp[i][0]
        dp[i+1][0] += 2*dp[i][0]
    else:
        dp[i+1][0] += dp[i][0]
    dp[i+1][0] %= MOD
    dp[i+1][1] %= MOD

ans = sum(dp[-1]) % MOD
print(ans)


def powmod(x, n,mod):
  if n == 0:
   return 1
  K = 1
  while n > 1:
   if n % 2 != 0:
    K = K * x%mod
    x = x ** 2%mod
    n = (n - 1) // 2
   else:
    x = x ** 2%mod
    n = n // 2%mod

  return K * x # 指数を割り続け n が 1 に至ったら終了
L=input()
S=len(L)-1
if S==0:
 print((3))
else:
 ans=1
 ct=0
 for i in range(S+1):
  if int(L[i])==1:
   ans+=((powmod(3, S-i,10**9+7)+1)*powmod(2, ct,10**9+7))%(10**9+7)
   ans%=(10**9+7)
   ct+=1
 print(ans)


ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
mod=10**9+7
L = input()
n = len(L)
dp1 = [0]*n#i桁目までがLより小さい
dp2=[0]*n#i桁目までがLと一致
dp1[0]=1 #00
dp2[0]=2 #01 or 10
for i in range(1,n):
    if L[i]=="1":
        dp1[i] = (2+1)*dp1[i-1]+1*dp2[i-1]
        dp2[i]= 2*dp2[i-1]
    elif L[i]=="0":
        dp1[i]=(2+1)*dp1[i-1]
        dp2[i]=dp2[i-1]
    dp1[i]%=mod
    dp2[i]%=mod
print((dp1[n-1]+dp2[n-1])%mod)


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

n = len(l)

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

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

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

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

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


MOD = 10**9+7

L = input()

dp1 = [0]*(len(L)+1)
dp0 = [1]*(len(L)+1)

for i in range(len(L)):
    dp1[i+1] = dp1[i]*3 + dp0[i] * (L[i]=="1")
    dp0[i+1] = dp0[i] * (2 if L[i]=="1" else 1)
    dp1[i+1] %= MOD
    dp0[i+1] %= MOD

ans = dp1[-1] + dp0[-1]
print(ans%MOD)

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

# import numpy as np

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

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


# ===CODE===


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


def __starting_point():
    main()

__starting_point()

import sys
import queue


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


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


def main():
    L = list(input())

    pow = [0] * (len(L) + 1)
    pow[0] = 1
    for i in range(1, len(L) + 1):
        pow[i] = pow[i - 1] * 3 % MOD
    N = len(L)
    if L[-1] == "0":
        answer = 1
    else:
        answer = 3
    for i in range(1, N):
        if L[N - i - 1] == "1":
            answer = answer * 2 + pow[i]
            answer %= MOD
        else:
            continue
    print(answer)


def __starting_point():
    main()

__starting_point()

def mempow(a,b,m):
    temp = 1
    yield temp
    for i in range(b):
        temp = temp * a % m
        yield temp

L = input()
m = 1000000007
mem2 = []
mem3 = []
m2append = mem2.append
m3append = mem3.append
for x in mempow(2,L.count('1'),m):
    m2append(x)
for x in mempow(3,len(L)-1,m):
    m3append(x)
ans = mem3[len(L)-1]
appeared = 1
for i in range(1,len(L)):
    if L[i] == '1':
        ans = (ans+mem2[appeared]*mem3[len(L)-i-1]) % m
        appeared += 1
ans = (ans+mem2[appeared]) % m
print(ans)

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 list(map(int, input().split()))
def LIST(): return list(map(int, input().split()))
def ZIP(n): return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

L = input()
n = len(L)

cnt_1 = list(accumulate(list(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)



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

ans = 1
for i, s in enumerate(reversed(L)):
    if s == '1':
        ans = (2 * ans + pow(3, i, MOD)) % MOD
print(ans)


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)

# E - Sum Equals Xor
# https://atcoder.jp/contests/abc129/tasks/abc129_e

MOD = 10 ** 9 + 7

L = input()
N = len(L)

# dp[i][j]= 上から i 桁目までを決めて、その桁までが (a, b) = [(0,0),(0,1),(1,0)] の3通りから選ばれていて、
# a+b が L より小さいことが確定している(j=1)/していない(j=0)ような選び方の個数
dp = [[0] * 2 for _ in range(N + 1)]
dp[0][0] = 1

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

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

mod=10**9+7
l=input()
bit=[int(i) for i in l]
m=len(bit)
#num1=sum(bit)
#print(bit)
#print(m)
#print(num1)
#ans=0
#ans+=(pow(3,m-1,mod))
#最上位bitの時
#ans+=(2*pow(2,num1-1,mod))
#print(ans%mod)

#適当にやりすぎたけど、桁DPジャン
#小さい方と同じ方
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)

from pprint import pprint

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

for i in range(1, nl + 1):
    li = i - 1

    # 小さいこと確定
    dp[i][1] = dp[i - 1][1] * 3 % MOD

    ############################
    if L[li] == '1':
        dp[i][1] += dp[i - 1][0]  # a, b 両方0

    # 当該桁まで =
    if L[li] == '1':
        dp[i][0] = dp[i - 1][0] * 2 % MOD  # a, b いずれか 1
    else:
        dp[i][0] = dp[i - 1][0]  # a, b 両方0

    dp[i][0] %= MOD
    dp[i][1] %= MOD

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



import sys

sys.setrecursionlimit(10 ** 7)
# ----------

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

s = input().strip()

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

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

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


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):
  # a+b = 0
  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
  # a+b = 1
  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)

L = input()
l = len(L)
dp = [[0]*2 for _ in range(100005)]
# dp[i][smaller]: i桁目までみる　未満なら1
# dp[i][1] : i桁目までみて、a, bどちらもL未満
# dp[i][0] : i桁目までみて、a+b = L
dp[0][0] = 1
mod = 10**9+7

for i in range(l):
  n = L[i]
  # a + b = 0
  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

  # a + b = 1
  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)

import sys

sys.setrecursionlimit(10 ** 7)
# ----------

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

s = input().strip()

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

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

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


L = input()

m = 1000000007

result = 1
t = 1
for c in L[::-1]:
    if c == '1':
        result = result * 2 + t
        result %= m
    t *= 3
    t %= m
print(result)


def mempow(a,b,m):
    temp = 1
    yield temp
    for i in range(b):
        temp = temp * a % m
        yield temp

L = open(0).read().split()[0]
m = 1000000007
mem2 = []
mem3 = []
m2append = mem2.append
m3append = mem3.append
for x in mempow(2,L.count('1'),m):
    m2append(x)
for x in mempow(3,len(L)-1,m):
    m3append(x)
ans = mem3[len(L)-1]
appeared = 1
for i in range(1,len(L)):
    if L[i] == '1':
        ans = (ans+mem2[appeared]*mem3[len(L)-i-1]) % m
        appeared += 1
ans = (ans+mem2[appeared]) % m
print(ans)

import sys

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

# 左からi桁目で、L以下が確定しているかどうか（True /False）の場合の(a, b)の組み合わせの総数
dp = [[0 for i in (True, False)] for _ in range(ls)]
# 1からしか始まらない
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][False] = 1 * dp[i][False]
        dp[i+1][True] %= mod
        dp[i+1][False] %= mod
 
print(sum(dp[ls-1]) % mod)

MOD = 10 ** 9 + 7

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

for i, s in enumerate(l[1:], start = 1):
    if s == "1":
        dp[i][0] = dp[i - 1][0] * 3 + dp[i - 1][1]
        dp[i][1] = dp[i - 1][1] * 2
    else:
        dp[i][0] = dp[i - 1][0] * 3
        dp[i][1] = dp[i - 1][1]
    dp[i][0] %= MOD
    dp[i][1] %= MOD
ans = sum(dp[-1])
print(ans % MOD)

import sys
sys.setrecursionlimit(10**9)
l=list(input())
n=len(l)
p=10**9+7
ans=0
d=0
def f(n,k,q):
    if k==0:
        return 1
    elif k%2==0:
        return ((f(n,k//2,q))**2)%q
    else:
        return (n*f(n,k-1,q))%q

for i in range(n):
    if l[i]=="1":
        x=n-i-1
        ans+=(f(3,x,p)*f(2,d,p))%p
        d+=1
    else:
        continue

ans+=f(2,d,p)
print((ans%p))


#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass

MOD = 1000000007  # type: int


def solve(L: str):
    a = 1
    b = 1
    for Li in L:
        if Li == "1":
            a *= 3
            a %= MOD
            b *= 2
            b %= MOD
        else:
            a += (a - b) * 2
            a %= MOD
    print(a)


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


def __starting_point():
    main()

__starting_point()

import sys
sys.setrecursionlimit(10000000)
import math
import bisect
def input():
    return sys.stdin.readline()[:-1]

l = input()
mod = 10**9+7
from collections import deque
l = deque(l)

def llo(st):
    if len(st)==1 and st[0]=="0":
        return 1
    elif len(st)==1 and st[0]=="1":
        return 3
    tmp = st.popleft()
    if tmp=="0":
        return llo(st)
    else:
        return (pow(3,len(st),mod) + 2*llo(st))%mod



if "0" not in l:
    print((pow(3,len(l),mod)))
else:
    ans = llo(l)
    print(ans)


MOD = 10**9 + 7

L = input()

dp1 = [0]*100010 # dp1[k]: 先頭からk桁について，A+B < L が確定している (A,B) の数
dp2 = [0]*100010 # dp2[k]: 先頭からk桁について，A+B と L が一致している (A,B) の数
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)

def main():
    MOD = 10 ** 9 + 7

    EQ = 0  # 等しくなり得る
    SMALL = 1  # 未満確定

    S = list(map(int, input()))
    dp = [1, 0]
    for x in S:
        ndp = [0] * 2

        if x == 0:
            ndp[EQ] = dp[EQ]  # (0,0)
            ndp[SMALL] = dp[SMALL] * 3  # (0,0),(0,1),(1,0)
        elif x == 1:
            ndp[EQ] = dp[EQ] * 2  # (0,1),(1,0)
            ndp[SMALL] = dp[EQ] + dp[SMALL] * 3  # EQ->(0,0), SMALL->(0,0),(0,1),(1,0)

        *dp, = [x % MOD for x in ndp]

    ans = sum(dp) % MOD  # 取り忘れ

    print(ans)


def __starting_point():
    main()

__starting_point()

MOD=10**9+7
L=input()
K=len(L)
dp=[[0,0] for i in range(K+1)]
dp[0][0]=1
for i in range(K):
    if(L[i]=='0'):
        dp[i+1][0]=dp[i][0]
        dp[i+1][1]=dp[i][1]*3%MOD
    elif(L[i]=='1'):
        dp[i+1][0]=dp[i][0]*2%MOD
        dp[i+1][1]=(dp[i][1]*3%MOD+dp[i][0])%MOD
print(sum(dp[K])%MOD)

def main():
    MOD = 10 ** 9 + 7
    L = input()
    N = len(L)
    dp = [0 for _ in range(N + 1)]
    dpp = [0 for _ in range(N + 1)]
    dpp[0] = 1
    for n in range(1, N + 1):
        dpp_v = dpp[n - 1]
        d = int(L[n - 1])
        dpp[n] = ((d + 1) * dpp_v) % MOD
        dp[n] = (3 * dp[n - 1] + d * dpp_v) % MOD
    print((dp[N] + dpp[N]) % MOD)


def __starting_point():
    main()
__starting_point()

mod = 10 ** 9 + 7

L = input()
N = len(L)

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

for i in range(N):
    nd = int(L[i])
    for a in range(2):
        for b in range(2):
            if a == b == 1:  # 繰り上がっちゃう(a+b>L)
                continue
            for k in range(2):
                ni = i + 1
                nk = k
                if nk == 0:
                    if nd == 1 and a == 0 and b == 0:
                        nk += 1
                    if nd == 0 and a | b > 0:
                        continue
                dp[ni][nk] += dp[i][k]
                dp[ni][nk] %= mod

ans = 0
for k in range(2):
    ans += dp[N][k]
    ans %= mod

print(ans)

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    s = readline().rstrip().decode()
    n = len(s)
    #print(s)
    P = int(1e9)+7
    dp = [[0, 0] for _ in range(n)]
    #dp[i][j]:=Lのi桁目まで見てLと一致する/未満である2数の組の数
    dp[0][0] = 1 #未満となる組は(0, 0)の1通り
    dp[0][1] = 2 #一致する組は(0, 1)と (1, 0)の2通り

    for i in range(1, n):
        if s[i] == '1':
            #dp[i-1][1]からの遷移は(0, 0)のみ。dp[i-1][0]からの遷移は(0, 0), (0, 1), (1, 0)
            dp[i][0] += dp[i-1][1] + dp[i-1][0] * 3 
            #i桁目が1となる組は(1, 0)と(0, 1)の2通り
            dp[i][1] += dp[i-1][1] * 2

            dp[i][0] %= P
            dp[i][1] %= P
        else:
            #(0, 0), (1, 0), (0, 1)を選ぶ
            dp[i][0] += dp[i-1][0] * 3 
            #(0, 0)を選ぶしかない
            dp[i][1] += dp[i-1][1]  

            dp[i][0] %= P
            dp[i][1] %= P

    print(((dp[n-1][0]+dp[n-1][1])%P))
def __starting_point():
    main()

__starting_point()

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    L = list(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] == "0":
            dp[i][0] = dp[i - 1][0]
            dp[i][1] = (dp[i - 1][1] * 3) % mod
        else:
            dp[i][0] = (dp[i - 1][0] * 2) % mod
            dp[i][1] = (dp[i - 1][1] * 3 + dp[i - 1][0]) % mod

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


def __starting_point():
    resolve()

__starting_point()

L=list(input())
L=list(map(int,L))
dp=[2,1]
MOD=10**9+7
for j in range(1,len(L)):
    a,b=dp
    if L[j]==1:
        dp[0]=(a*2)%MOD
        dp[1]=(a+b*3)%MOD
    elif L[j]==0:
        dp[1]=(b*3)%MOD
print(sum(dp)%MOD)