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

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, 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
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):
			if now == e:
				dp_new[now][1] += dp[prev][1] * (now + 1)
			if now == 0 and e == 1:
				dp_new[now][0] += dp[prev][1]
			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)


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]
		dp2[i + 1] = dp2[i] * 3
	else:
		dp1[i + 1] = dp1[i] * 2
		dp2[i + 1] = dp2[i] * 3 + dp1[i]
	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):
		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
			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
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)


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


import sys
sys.setrecursionlimit(200000)
MOD = 1000000007

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)

def main():

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

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

def __starting_point():
	main()
__starting_point()


L = input()
N = len(L)
mod = int(1000000000.0 + 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)


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


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


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


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():
	L = input().rstrip()
	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[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 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
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)


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


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)

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)
	dp_1 = [0] * N
	dp_2 = [0] * N
	dp_1[0] = 1
	dp_2[0] = 2
	for i in range(1, N):
		if L[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:
			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)


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)


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
	dp_new[1] += dp[1] * (e + 1)
	if e == 1:
		dp_new[0] += dp[1]
	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
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[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)


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
for i in range(n):
	if L[i] == '1':
		p = 1
		if i >= 1:
			p *= pow(2, csum_1[i - 1], mod)
		p *= pow(3, n - i - 1, mod)
		ans += p
		ans %= mod
p = pow(2, csum_1[-1], mod)
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 = [[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':
		ans += count[u] % mod * pow_mod(2, cnt) % mod
		ans %= mod
		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)


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
ans = 1
three = [1] * (len(L) + 1)
for i in range(len(L)):
	ans *= 3
	ans %= mod
	three[i + 1] = ans
x = 1
for i in range(len(L)):
	if L[i] == '0':
		y = x * 2
		y *= three[len(L) - i - 1]
		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)


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)


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
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
dp2 = [0] * n
dp1[0] = 1
dp2[0] = 2
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)


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
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
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()])

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
from decimal import *
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)


MOD = 10 ** 9 + 7
L = input()
N = len(L)
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)
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]
	if L[li] == '1':
		dp[i][0] = dp[i - 1][0] * 2 % MOD
	else:
		dp[i][0] = dp[i - 1][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):
	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)


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


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)


import sys
try:
	from typing import List
except ImportError:
	pass
MOD = 1000000007

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


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]
			ndp[SMALL] = dp[SMALL] * 3
		elif x == 1:
			ndp[EQ] = dp[EQ] * 2
			ndp[SMALL] = dp[EQ] + dp[SMALL] * 3
		(*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:
				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)
	P = int(1000000000.0) + 7
	dp = [[0, 0] for _ in range(n)]
	dp[0][0] = 1
	dp[0][1] = 2
	for i in range(1, n):
		if s[i] == '1':
			dp[i][0] += dp[i - 1][1] + dp[i - 1][0] * 3
			dp[i][1] += dp[i - 1][1] * 2
			dp[i][0] %= P
			dp[i][1] %= P
		else:
			dp[i][0] += dp[i - 1][0] * 3
			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)