You are given two positive integers $\class{ML__boldsymbol}{\boldsymbol{a}}$ and $\boldsymbol{b}$ in binary representation. You should find the following sum modulo $10^9+7$:

$\sum\limits_{i=0}^{314159}\left(a\:x or\left(b\:s h l\:i\right)\right)$

where operation $\boldsymbol{x}\textbf{or}$ means exclusive OR operation, operation $\mbox{shl}$ means binary shift to the left.

Please note, that we consider ideal model of binary integers. That is there is infinite number of bits in each number, and there are no disappearings (or cyclic shifts) of bits.

Input Format

The first line contains number $\class{ML__boldsymbol}{\boldsymbol{a}}$ $(1\leq a<2^{10^{5}})$ in binary representation. The second line contains number $\boldsymbol{b}$ $(1\leq b<2^{10^{5}})$ in the same format. All the numbers do not contain leading zeros.

Output Format

Output a single integer $-$ the required sum modulo $10^9+7$.

Sample Input
10
1010

Sample Output
489429555

Source: hackerrank | Difficulty: MEDIUM
Tags: Dynamic programming


Solutions:
a = int(input(), 2)
b = int(input(), 2)
r = 0
for i in range(314160):
	r += a ^ b
	b *= 2
print(r % (10 ** 9 + 7))


a = int(input(), 2)
b = int(input(), 2)
total = 0
for i in range(0, 314160):
	total = total + (a ^ b << i)
print(total % (10 ** 9 + 7))


a = input()
a = int(a, 2)
b = input()
b = int(b, 2)
s = 0
for i in range(314160):
	s += a ^ b << i
res = s % (pow(10, 9) + 7)
print(res)


a = int(input(), base=2)
b = int(input(), base=2)
print(sum((a ^ b << i for i in range(314160))) % 1000000007)


a = int(input(), 2)
b = int(input(), 2)
result = 0
for i in range(314160):
	result += a ^ b << i
print(result % (10 ** 9 + 7))


import sys
input = sys.stdin.readline()
k = len(input)
a = int(input, 2)
input = sys.stdin.readline()
b = int(input, 2)
result = 0
modulus = 10 ** 9 + 7
for i in range(0, min(k, 314159) + 1):
	result = result + (a ^ b << i)
	result = result % modulus
if k < 314159:
	result = (result + a * (314159 - k)) % modulus
	result = result + b * pow(2, 314160, modulus)
	result = result - b * pow(2, k + 1, modulus)
	result = result % modulus
print(result)


a = input()
a = str(a)
b = input()
b = str(b)
a = int(a, 2)
b = int(b, 2)
(x, ans) = (0, 0)
for x in range(0, 314160):
	ans = ans + (a ^ b << x)
print(ans % 1000000007)


a = input()
la = len(a)
a = int(a, 2)
b = input()
lb = len(b)
b = int(b, 2)
n = 314159
m = 10 ** 9 + 7
bcurr = b
bpost = b << n + 1
res = 0
c = bcurr & 1
p = 1
for i in range(lb + n + 1):
	if a & 1:
		res += (n + 1 - c) * p
		res %= m
	else:
		res += c * p
		res %= m
	bcurr >>= 1
	bpost >>= 1
	p = p * 2 % m
	a >>= 1
	c += (bcurr & 1) - (bpost & 1)
print(res)


N = 314159
MAX = 1000000
MOD = 1000000007
a = input()[::-1]
b = input()[::-1]
p2 = [1] * MAX
for i in range(1, MAX):
	p2[i] = p2[i - 1] * 2 % MOD
nb_ones_b = [0] * len(b)
for i in range(len(b)):
	nb_ones_b[i] = int(b[i])
	if i > 0:
		nb_ones_b[i] += nb_ones_b[i - 1]

def count_ones(lo, hi):
	if lo < 0:
		lo = 0
	if hi >= len(b):
		hi = len(b) - 1
	if lo > hi:
		return 0
	return nb_ones_b[hi] - (0 if lo == 0 else nb_ones_b[lo - 1])
res = 0
for i in range(int(MAX)):
	co = count_ones(i - N, i)
	bit = 0 if i >= len(a) else int(a[i])
	if bit == 1:
		res = (res + (N + 1 - co) * p2[i]) % MOD
	else:
		res = (res + co * p2[i]) % MOD
print(res)


a = int(input(), 2)
b = int(input(), 2)
modulo = 10 ** 9 + 7
count = 314160
s = 0
bitLength = a.bit_length()
for i in range(bitLength):
	summand = a ^ b
	s = (s + summand) % modulo
	b = b << 1
count -= bitLength
multiplier = pow(2, count, modulo) - 1
s = (s + a * count + b * multiplier) % modulo
print(s)


a = int(input(), 2)
b = int(input(), 2)
t = 0
for i in range(314160):
	t += a ^ b << i
print(t % (10 ** 9 + 7))


a = input()
b = input()
p2 = [1]
p21 = [0]
MOD = 1000000007
for i in range(1, 314161):
	p2.append(2 * p2[i - 1])
	p2[i] %= MOD
	p21.append((p21[i - 1] + p2[i - 1]) % MOD)
al = len(a)
bl = len(b)
ans = 0
for i in range(bl):
	if b[bl - i - 1] == '1':
		ans += p21[314160] * p2[i]
		ans %= MOD
if bl < al:
	d = al - bl
	ex = ''
	for i in range(d):
		ex += '0'
	b = ex + b
	bl = al
o = 0
z = 0
for i in range(al):
	if b[bl - i - 1] == '1':
		o += 1
	else:
		z += 1
	if a[al - i - 1] == '1':
		ans += (314160 - 2 * o) * p2[i] % MOD
		ans %= MOD
if ans < 0:
	ans += MOD
print(str(ans))


a = int(input(), 2)
b = int(input(), 2)
total = 0
for _ in range(314160):
	total += a ^ b
	b = b << 1
print(total % (10 ** 9 + 7))


a = int(input(), 2)
b = int(input(), 2)
total = 0
for _ in range(314160):
	total += a ^ b
	b = b << 1
print(total % (10 ** 9 + 7))


a = int(input(), 2)
b = int(input(), 2)
s = 0
for i in range(314160):
	s += a ^ b << i
print(s % (10 ** 9 + 7))


MOD = 10 ** 9 + 7
SUMTO = 314159
from itertools import accumulate, repeat, chain

def main():
	a = input()
	b = input()
	total = ((SUMTO + 1) * (int(a, 2) % MOD) + (pow(2, SUMTO + 1, MOD) - 1) * (int(b, 2) % MOD)) % MOD
	cumsum = accumulate((digit == '1' for digit in chain(reversed(b), repeat(0))))
	mult = 2
	for (cs, digit) in zip(cumsum, reversed(a)):
		if digit == '1':
			total = total - mult * cs
		mult = 2 * mult % MOD
	print(total % MOD)
main()


a = int(input(), base=2)
b = int(input(), base=2)
sum = 0
for i in range(314160):
	sum += a ^ b << i
print(sum % (pow(10, 9) + 7))


a = int(input(), base=2)
b = int(input(), base=2)

def solve(a, b):
	n = 314160
	s = a ^ b
	for i in range(1, n):
		s += a ^ b << i
	print(s % (10 ** 9 + 7))
solve(a, b)


a = int(input(), 2)
b = int(input(), 2)
ab_sum = 0
mod = 10 ** 9 + 7
for i in range(314159 + 1):
	ab_sum += a ^ b << i
print(ab_sum % mod)


def bitlist(numstring):
	return map(int, reversed(numstring))
base = 10 ** 9 + 7
rounds = 314159 + 1
a = input()
b = input()
aint = int(a, 2) % base
bint = int(b, 2) % base
supermultiple = int('1' * rounds, 2) % base
answer = (aint * rounds + bint * supermultiple) % base
abits = bitlist(a)
bbits = bitlist(b)
bcount = 0
for (i, abit) in enumerate(abits):
	bcount += next(bbits, 0)
	if abit == 0:
		continue
	answer = (answer - bcount * pow(2, i + 1, base)) % base
print(answer)


a = int(input(), 2)
b = int(input(), 2)
x = 0
m = 10 ** 9 + 7
for i in range(0, 314160):
	y = b << i
	y = y ^ a
	x = x + y
print(x % m)


a = int(input(), 2)
b = int(input(), 2)
total = 0
for num in range(0, 314160):
	total += a ^ b << num
print(total % 1000000007)


a = int(input(), 2)
b = int(input(), 2)
sum = 0
modulo = 1000000007
for i in range(0, 314160):
	sum += a ^ b << i
print(sum % modulo)


import sys

def num_ones(cumulative_binary, left, right):
	if left < 0:
		left = 0
	if right > len(cumulative_binary):
		right = len(cumulative_binary) - 1
	if left > right:
		return 0
	return cumulative_binary[right] - (cumulative_binary[left - 1] if left > 0 else 0)
N = 314159
MOD = 1000000007
A = sys.stdin.readline().strip()
B = sys.stdin.readline().strip()
NMax = 1000000
A = '0' * (NMax - len(A)) + A
B = '0' * (NMax - len(B)) + B
power_mod = [1]
for i in range(NMax - 1):
	power_mod.append(2 * power_mod[i] % MOD)
count = 0
sb = []
for i in range(NMax - 1, -1, -1):
	count += 1 if B[i] == '1' else 0
	sb.append(count)
ans = 0
for i in range(NMax):
	if A[NMax - 1 - i] == '1':
		ans += power_mod[i] * (N - num_ones(sb, i - N, i) + 1)
	else:
		ans += power_mod[i] * num_ones(sb, i - N, i)
print(ans % MOD)


def binaryToDecimal(value_str):
	size = len(value_str)
	value = 0
	for i in value_str:
		value = value * 2
		if i == '1':
			value += 1
	return value

def findXorSum(act_a, act_b, len_a, max_idx, modulo):
	value = 0
	for i in range(len_a):
		value += act_a ^ act_b << i
		value = value % modulo
	temp = (max_idx - len_a) * act_a % modulo
	temp1 = (2 ** max_idx - 1) * act_b % modulo
	temp1 = temp1 - (2 ** len_a - 1) * act_b
	value2 = (temp + temp1) % modulo
	return (value + value2) % modulo
a = input()
b = input()
act_a = binaryToDecimal(a)
act_b = binaryToDecimal(b)
print(findXorSum(act_a, act_b, len(a), 314160, 10 ** 9 + 7))


def xor_and_sum(a, b):
	C = [[0 for _ in range(2)] for _ in range(500000)]
	A = [0 for _ in range(500000)]
	B = [0 for _ in range(500000)]
	L = len(a)
	M = len(b)
	for i in range(L):
		A[L - i - 1] = int(a[i])
	for i in range(M):
		B[M - i - 1] = int(b[i])
	C[0][0] = B[0] == 0
	C[0][1] = B[0] == 1
	for i in range(1, M + 314159):
		C[i][0] = C[i - 1][0] + (B[i] == 0)
		C[i][1] = C[i - 1][1] + (B[i] == 1)
	I = 1
	T = A[0] * (C[0][0] + 314159) + (A[0] ^ 1) * C[0][1]
	for i in range(1, M + 314159):
		if i < 314159:
			T1 = C[i][0] - i + 314159
			T2 = C[i][1]
		else:
			T1 = C[M - 1][0] - C[i - 314159 - 1][0] + 314159
			T2 = C[M - 1][1] - C[i - 314159 - 1][1]
		I *= 2
		I %= 1000000007
		T += I * (A[i] * T1 + (A[i] ^ 1) * T2)
		T %= 1000000007
	return T

def main():
	a = input()
	b = input()
	print(xor_and_sum(a, b))
main()


a = input()
b = input()
a = int(a, 2)
b = int(b, 2)
sum = 0
for i in range(314159 + 1):
	sum += a ^ b << i
print(sum % (10 ** 9 + 7))


a = int(str(input()), 2)
b = int(str(input()), 2)
s = 1
for i in range(0, 314160):
	s += a ^ b << i
print(s % 1000000007 - 1)


a = int(input(), 2)
b = int(input(), 2)
sum = 0
for i in range(0, 314160):
	sum += a ^ b << i
print(sum % 1000000007)


a = int('0b' + input(), 2)
b = int('0b' + input(), 2)
s = 0
for i in range(314160):
	s += a ^ b << i
print(s % (pow(10, 9) + 7))


from sys import stdin, stdout
a = stdin.readline().rstrip()
lenA = len(a)
a = int(a, 2)
b = int(stdin.readline(), 2)
add = 0
end = 314159
mod = 10 ** 9 + 7
for i in range(lenA):
	add += a ^ b << i
add += a * (end - lenA + 1) + b * 2 ** lenA * (2 ** (end - lenA + 1) - 1)
print(add % mod)


a = int(input(), 2)
b = int(input(), 2)
r = 0
for i in range(314160):
	r += a ^ b
	b *= 2
print(r % (10 ** 9 + 7))


a = int(input(), 2)
b = int(input(), 2)
print(sum((a ^ b << i for i in range(314160))) % 1000000007)


a = int(input(), 2)
b = int(input(), 2)
N = 314159
s = 0
for i in range(0, N + 1):
	s += a ^ b << i
print(s % 1000000007)


def solve(a, b):
	ans = 0
	for i in range(314159 + 1):
		ans += a ^ b << i
	return ans % (10 ** 9 + 7)

def main():
	a = int(input(), 2)
	b = int(input(), 2)
	print(solve(a, b))
main()


a = int(input(), 2)
b = int(input(), 2)
sum = 0
for i in range(314159 + 1):
	curVal = a ^ b << i
	sum += curVal
print(sum % 1000000007)


from functools import reduce
import sys
a = int(sys.stdin.readline().lstrip(), 2)
b = int(sys.stdin.readline().lstrip(), 2)
value = 0
for i in range(0, 314160):
	value += a ^ b << i
print(value % (10 ** 9 + 7))


a = int(input(), 2)
b = int(input(), 2)
s = 0
for i in range(314159 + 1):
	s += a ^ b << i
print(s % (10 ** 9 + 7))


a = int(input().strip(), 2)
b = int(input().strip(), 2)
total = 0
for i in range(314159 + 1):
	rol = b << i
	total += a ^ rol
print(total % (10 ** 9 + 7))


mod = 1000000007
s = 314159

def binVal(R):
	value = 0
	mul = 1
	for r in R:
		value = (value + r * mul) % mod
		mul = 2 * mul % mod
	return value
A = [int(i) for i in reversed(input())]
B = [int(i) for i in reversed(input())]
a = len(A)
b = len(B)
n = max(a, b + s)
Res = [0] * n
Res[0] = B[0]
if b > s + 1:
	for i in range(1, s + 1):
		Res[i] = Res[i - 1] + B[i]
	for i in range(s + 1, b):
		Res[i] = Res[i - 1] + B[i] - B[i - s - 1]
	for i in range(b, b + s):
		Res[i] = Res[i - 1] - B[i - s - 1]
else:
	for i in range(1, b):
		Res[i] = Res[i - 1] + B[i]
	for i in range(b, s + 1):
		Res[i] = Res[i - 1]
	for i in range(s + 1, b + s):
		Res[i] = Res[i - 1] - B[i - s - 1]
for i in range(a):
	if A[i] == 1:
		Res[i] = s + 1 - Res[i]
print(binVal(Res))


a = int(input(), 2)
b = int(input(), 2)
s = 0
for i in range(314160):
	s += a ^ b << i
print(s % 1000000007)


a = int(input(), 2)
b = int(input(), 2)
sum = 0
for i in range(314160):
	sum += a ^ b << i
print(sum % (10 ** 9 + 7))


def convertto(a):
	mul = int(1)
	i = int(len(a) - 1)
	k = int(0)
	while i >= 0:
		k += int(a[i]) * mul
		mul *= 2
		i -= 1
	return k
x = input()
y = input()
a = convertto(x)
b = convertto(y)
k = int(0)
i = int(0)
k = int(0)
while i <= 314159:
	c = int(b << i)
	k += a ^ c
	i += 1
print(k % 1000000007)


import sys
aStr = '0b' + input().strip()
bStr = '0b' + input().strip()
A = int(aStr, 2)
B = int(bStr, 2)
modN = 10 ** 9 + 7
sum = 0
for i in range(314160):
	sum += A ^ B << i
print(sum % modN)


a = input()
b = input()
ab = int(a, base=2)
bb = int(b, base=2)
sum = 0
for i in range(314160):
	sum += ab ^ bb << i
print(sum % 1000000007)


howmany = 314159
mod = 10 ** 9 + 7
a = input()
b = input()
na = len(a)
nb = len(b)
n = howmany + nb
a = '0' * (n - na) + a
b = '0' * (n - nb) + b + '0' * howmany
times = [0 for i in range(n)]
lasts = [0 for i in range(n)]
times[-1] = ((a[-1] != b[n - 1]) + howmany * (a[-1] != '0')) % mod
for i in reversed(range(n - 1)):
	t = times[i + 1] - (a[i + 1] != b[i + 1 + howmany])
	assert t >= 0
	assert howmany - t >= 0
	if a[i] == a[i + 1]:
		times[i] = t
	else:
		times[i] = (howmany - t) % mod
	times[i] = (times[i] + (a[i] != b[i])) % mod
res = 0
p = 1
for x in reversed(times):
	res = (res + x * p % mod) % mod
	p = 2 * p % mod
print(res)


a = input().strip()
b = input().strip()
ba = int(a, 2)
bb = int(b, 2)
m = 1000000007
res = 0
for i in range(0, 314160):
	if i > 0:
		bb = bb << 1
	s = ba ^ bb
	res = res + s
print(res % m)


a = int(input(), 2)
b = int(input(), 2)
s = 0
for i in range(314159 + 1):
	s += a ^ b << i
print(s % (10 ** 9 + 7))


a = int(input(), 2)
b = int(input(), 2)
count = 0
for x in range(314160):
	count += a ^ b << x
print(count % (10 ** 9 + 7))


import sys
a = input()
b = input()
a = int(a, 2)
b = int(b, 2)
sum = 0
range1 = 0
for i in range(0, 314160):
	sum = sum + (a ^ b << i)
sum = sum % 1000000007
print(sum)


(s, a, b) = (0, int(input(), 2), int(input(), 2))
for i in range(314160):
	s += a ^ b
	b <<= 1
print(s % 1000000007)


(a, b) = (input(), input())
res = 0
(s, t) = ('0b' + a, '0b' + b)
(i, j) = (int(s, 2), int(t, 2))
for k in range(0, 314160):
	res = res + (i ^ j << k)
temp = 10 ** 9 + 7
print(res % temp)


MOD = 10 ** 9 + 7
a = input()
b = input()
a_int = int(a, 2)
b_int = int(b, 2)
ans = 0
for i in range(314160):
	ans += a_int ^ b_int << i
print(ans % MOD)


a = int(input(), 2)
b = int(input(), 2)
sum = 0
for i in range(314159 + 1):
	sum += a ^ b << i
mod = 1000000007
val = sum % mod
print(val)


a = int(input(), 2)
b = int(input(), 2)
val = 0
for i in range(314160):
	val += a ^ b << i
val = val % 1000000007
print(val)


import math
a = input()
a = int(a, 2)
b = input()
b = int(b, 2)
s = 0
for i in range(314160):
	s = s + (a ^ b << i)
p = 10 ** 9 + 7
s = s % p
print(s)


a = input()
a = int(a, 2)
b = input()
b = int(b, 2)
s = 0
for i in range(314160):
	s += a ^ b << i
s %= 10 ** 9 + 7
print(s)


a = input()
b = input()
a_decimal = int(a, 2)
b_decimal = int(b, 2)
sum = 0
for i in range(0, 314160):
	sum += a_decimal ^ b_decimal << i
print(sum % 1000000007)


bin1 = input()
a = int(bin1, 2)
bin2 = input()
b = int(bin2, 2)
ans = 0
for i in range(0, 314160):
	ans = ans + (a ^ b << i)
print(ans % 1000000007)


bin1 = input()
a = int(bin1, 2)
bin2 = input()
b = int(bin2, 2)
ans = 0
for i in range(0, 314160):
	ans = ans + (a ^ b << i)
print(ans % 1000000007)


a = int(input().strip(), base=2)
b = int(input().strip(), base=2)
print(sum((a ^ b << i for i in range(314160))) % 1000000007)


def summing(a, b):
	a = int(str(a), 2)
	b = int(str(b), 2)
	s = a ^ b
	for i in range(314159):
		b <<= 1
		s += a ^ b
	return s % (10 ** 9 + 7)
print(summing(int(input()), int(input())))


from sys import stdin
a = int(stdin.readline(), 2)
b = int(stdin.readline(), 2)
sum = 0
mod = 10 ** 9 + 7
for i in range(314159 + 1):
	sum += a ^ b
	b <<= 1
sum %= mod
print(sum)


a = int(input(), 2)
b = int(input(), 2)
big = 10 ** 9 + 7
limit = 314159 + 1
s1 = 0
for i in range(limit):
	s1 += a ^ b << i
print(s1 % big)


num1 = int(input(), 2)
num2 = int(input(), 2)
mod_num = 1000000007
sum = 0
for i in range(314160):
	sum += num1 ^ num2 << i
sum = sum % mod_num
print(sum)


MOD = 1000000007
a = int(input(), 2)
b = int(input(), 2)
c = int(0)
for i in range(314160):
	c = c + (a ^ b)
	b = b << 1
print(c % MOD)


import sys
from functools import reduce
(ab, bb) = sys.stdin.read().split()
a = reduce(lambda r, x: r * 2 + (1 if x == '1' else 0), ab, 0)
b = reduce(lambda r, x: r * 2 + (1 if x == '1' else 0), bb, 0)
s = sum((a ^ b << i for i in range(314159 + 1)))
print(s % 1000000007)


print((lambda a, b: (sum(((a ^ b << i) % 1000000007 for i in range(a.bit_length() + 1))) % 1000000007 + (314159 - a.bit_length()) * a % 1000000007 + b * (1 << a.bit_length() + 1) * ((1 << 314159 - a.bit_length()) - 1) % 1000000007) % 1000000007)(*map(lambda x: int(x, 2), (input(), input()))))


import sys
(a, b) = (int(input(), 2), int(input(), 2))
d = int(10 ** 9 + 7)
print(a, b, file=sys.stderr)
s = sum((a ^ b << i for i in range(314160))) % d
print(s)


a = eval('0b' + input())
b = eval('0b' + input())
res = 0
for i in range(314160):
	res += a ^ b << i
print(res % (10 ** 9 + 7))


a = int(input(), 2)
b = int(input(), 2)
r = 0
for i in range(314159 + 1):
	r += a ^ b
	b <<= 1
print(r % 1000000007)


a = int(input(), 2)
b = int(input(), 2)
s = 0
for i in range(314160):
	s += a ^ b
	b = b << 1
print(s % (10 ** 9 + 7))


a = int(input(), 2)
b = int(input(), 2)
s = 0
for i in range(0, 314159 + 1):
	s += a ^ b << i
print(s % 1000000007)


a = int(input(), 2)
b = int(input(), 2)
sum = 0
for i in range(0, 314160):
	sum += a ^ b << i
print(sum % (pow(10, 9) + 7))


a = int(input(), 2)
b = int(input(), 2)
result = sum((a ^ b << i for i in range(314160)))
print(result % (10 ** 9 + 7))


a = int(input(), 2)
b = int(input(), 2)
s = 0
for i in range(314160):
	s += a ^ b << i
print(s % 1000000007)


a = int(input(), 2)
b = int(input(), 2)
c = 0
for i in range(0, 314159 + 1):
	c += a ^ b << i
print(c % (10 ** 9 + 7))


import sys
import operator
a = int(input(), 2)
b = int(input(), 2)
sum = 0
for i in range(314160):
	sum = sum + operator.xor(a, operator.lshift(b, i))
result = operator.mod(sum, 1000000007)
print(result)


a = int(input(), 2)
b = int(input(), 2)
s = 0
for i in range(314159 + 1):
	s += a ^ b << i
print(s % (10 ** 9 + 7))


a = int(input(), 2)
b = int(input(), 2)
total = a ^ b
for i in range(1, 314160):
	total += a ^ b << i
total %= 10 ** 9 + 7
print(total)


(a, b) = [int(input().strip(), 2), int(input().strip(), 2)]
total = 0
for i in range(0, 314160):
	total += a ^ b << i
print(total % (10 ** 9 + 7))


from itertools import chain, count, islice, repeat
from operator import __add__, __mul__

def iterate(function, iterable, initializer=None):
	it = iter(iterable)
	if initializer is None:
		try:
			value = next(it)
		except StopIteration:
			raise TypeError('iterate() of empty sequence with no initial value') from None
	else:
		value = initializer
	yield value
	for element in it:
		value = function(value, element)
		yield value

def intput():
	return list(map(int, input()))
(X, MODULUS) = (314159, 10 ** 9 + 7)

def counts(b):
	assert len(b) < X
	from collections import Counter
	counter = Counter()
	for i in range(len(b) + X):
		if i < len(b):
			counter[b[i]] += 1
		else:
			counter[0] += 1
			if i > X:
				counter[b[i - X - 1]] -= 1
		yield (counter[0], counter[1])
(a, b) = (intput(), intput())
if len(a) > len(b):
	b = list(chain(repeat(0, len(a) - len(b)), b))
a = list(chain(repeat(0, len(b) + X - len(a)), a))
powers = lambda base: iterate(lambda a, b: a * b % MODULUS, repeat(base), 1)
powers = reversed(list(islice(powers(2), len(b) + X)))
total = 0
for (i, x, power, (zeros, ones)) in zip(count(0), a, powers, counts(b)):
	total = (total + power * [ones, zeros][x]) % MODULUS
print(total)


a = int(input(), 2)
b = int(input(), 2)
print(sum((a ^ b << i for i in range(314159 + 1))) % (10 ** 9 + 7))


a = int(input(), 2)
b = int(input(), 2)
sum1 = 0
for i in range(0, 314160):
	sum1 += a ^ b << i
print(sum1 % (10 ** 9 + 7))


def bits_to_int(ar):
	c = 1
	ret = 0
	for it in ar:
		if it == 1:
			ret += c
		c <<= 1
	return ret

def forward_sum(ar):
	ret = ar
	for it in range(1, len(ret)):
		ret[it] += ret[it - 1]
	return ret

def solve_(a, b):
	width = 314160
	a_sum = bits_to_int(a) * width
	b_sum = 0
	b_temp = bits_to_int(b)
	for it in range(width):
		b_sum <<= 1
		b_sum += b_temp
	b = forward_sum(b)
	overlap = 0
	for it in enumerate(a):
		if it[1] == 0:
			continue
		if len(b) < it[0]:
			continue
		overlap += (2 << it[0]) * b[it[0]]
	return (a_sum + b_sum - overlap) % 1000000007

def solve(a, b):
	a = bits_to_int(a)
	b = bits_to_int(b)
	total = 0
	for it in range(314160):
		total += a ^ b << it
	return total % 1000000007
a = [int(it) for it in reversed(input())]
b = [int(it) for it in reversed(input())]
print(solve(a, b))


a = int(input(), 2)
b = int(input(), 2)
sum = 0
for i in range(314160):
	sum += a ^ b << i
print(sum % 1000000007)


def calc(a, b):
	sum = 0
	n = 314160
	for i in range(n):
		sum += a ^ b << i
	return sum
a = int(input(), 2)
b = int(input(), 2)
out = calc(a, b) % (10 ** 9 + 7)
print(out)


a = int(input().strip(), 2)
b = int(input().strip(), 2)
mod = 1000000007
s = 0
for i in range(314160):
	s += a ^ b << i
print(s % mod)


a = input()
b = input()
aa = int(a, 2)
bb = int(b, 2)
m = 10 ** 9 + 7
res = 0
res += (314160 - len(a)) * (aa % m) % m
res += (2 ** 314160 - 2 ** len(a)) % m * (bb % m) % m
res %= m
for i in range(len(a)):
	res += (aa ^ bb << i) % m
	res %= m
print(res)


a = int(input(), 2)
b = int(input(), 2)
r = 0
for i in range(314160):
	r += a ^ b
	b *= 2
print(r % (10 ** 9 + 7))


(a, b) = (int(input(), 2), int(input(), 2))
s = 0
for n in range(314160):
	s += a ^ b << n
print(s % (10 ** 9 + 7))


MOD = 10 ** 9 + 7
N = 314159

def get_sum(a, b):
	s = 0
	for i in range(N + 1):
		s += a & b << i
	return (b * (2 ** (N + 1) - 1) + a * (N + 1) - s * 2) % MOD
a = int(input(), 2)
b = int(input(), 2)
print(get_sum(a, b))


import sys
(a, b) = (input(), input())
(alen, blen) = (len(a), len(b))
(a, b) = (int(a, base=2), int(b, base=2))
sm = 0
for i in range(314160):
	sm += a ^ b << i
print(sm % (10 ** 9 + 7))


a = int(input(), 2)
b = int(input(), 2)
ans = 0
m = 10 ** 9 + 7
for x in range(314159 + 1):
	ans += a ^ b << x
print(ans % m)


a = int(input().strip(), 2)
b = int(input().strip(), 2)
s = 0
for i in range(314160):
	s += a ^ b << i
print(s % (10 ** 9 + 7))


a = int(input(), 2)
b = int(input(), 2)
ans = 0
for i in range(314160):
	ans += a ^ b << i
print(ans % 1000000007)


N = 314159
K = 1000000007
A = input().strip()
B = input().strip()
L = len(A)
a = int(A, 2)
b = int(B, 2)
bb = b
X = 0
for i in range(L):
	X += a ^ bb
	bb <<= 1
print(((N - L + 1) * a % K + ((b << N - L + 1) % K - b << L) % K + X % K) % K)


a = int(input(), 2)
b = int(input(), 2)
ans = 0
for i in range(314160):
	ans += a ^ b << i
print(ans % 1000000007)


MOD_BASE = 1000000007
MAX_I = 314159
a = input().strip()
b = input().strip()
a = int(a, base=2)
b = int(b, base=2)
xorSum = 0
for i in range(MAX_I + 1):
	xorSum += a ^ b << i
xorSum %= MOD_BASE
print(xorSum)