You are given two huge binary integer numbers $a$ and $b$ of lengths $n$ and $m$ respectively. You will repeat the following process: if $b > 0$, then add to the answer the value $a~ \&~ b$ and divide $b$ by $2$ rounding down (i.e. remove the last digit of $b$), and repeat the process again, otherwise stop the process.

The value $a~ \&~ b$ means bitwise AND of $a$ and $b$. Your task is to calculate the answer modulo $998244353$.

Note that you should add the value $a~ \&~ b$ to the answer in decimal notation, not in binary. So your task is to calculate the answer in decimal notation. For example, if $a = 1010_2~ (10_{10})$ and $b = 1000_2~ (8_{10})$, then the value $a~ \&~ b$ will be equal to $8$, not to $1000$.


-----Input-----

The first line of the input contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the length of $a$ and the length of $b$ correspondingly.

The second line of the input contains one huge integer $a$. It is guaranteed that this number consists of exactly $n$ zeroes and ones and the first digit is always $1$.

The third line of the input contains one huge integer $b$. It is guaranteed that this number consists of exactly $m$ zeroes and ones and the first digit is always $1$.


-----Output-----

Print the answer to this problem in decimal notation modulo $998244353$.


-----Examples-----
Input
4 4
1010
1101

Output
12

Input
4 5
1001
10101

Output
11



-----Note-----

The algorithm for the first example:   add to the answer $1010_2~ \&~ 1101_2 = 1000_2 = 8_{10}$ and set $b := 110$;  add to the answer $1010_2~ \&~ 110_2 = 10_2 = 2_{10}$ and set $b := 11$;  add to the answer $1010_2~ \&~ 11_2 = 10_2 = 2_{10}$ and set $b := 1$;  add to the answer $1010_2~ \&~ 1_2 = 0_2 = 0_{10}$ and set $b := 0$. 

So the answer is $8 + 2 + 2 + 0 = 12$.

The algorithm for the second example:   add to the answer $1001_2~ \&~ 10101_2 = 1_2 = 1_{10}$ and set $b := 1010$;  add to the answer $1001_2~ \&~ 1010_2 = 1000_2 = 8_{10}$ and set $b := 101$;  add to the answer $1001_2~ \&~ 101_2 = 1_2 = 1_{10}$ and set $b := 10$;  add to the answer $1001_2~ \&~ 10_2 = 0_2 = 0_{10}$ and set $b := 1$;  add to the answer $1001_2~ \&~ 1_2 = 1_2 = 1_{10}$ and set $b := 0$. 

So the answer is $1 + 8 + 1 + 0 + 1 = 11$.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Mathematics

Data structures

Implementation


Solutions:
import math
dict1 = {}
mod = 998244353
for i in range(20):
	dict1[i] = 0
(n, m) = list(map(int, input().split()))
s1 = str(input())
s2 = str(input())
count1 = 0
arr = []
for i in range(len(s2)):
	if s2[i] == '1':
		count1 += 1
	arr.append(count1)
j = len(s1) - 1
k = min(len(s1), len(s2))
i = 0
while k > 0:
	if s1[j] == '1':
		dict1[i] = arr[len(s2) - i - 1]
	i += 1
	j -= 1
	k -= 1
ans = 0
for i in dict1:
	if dict1[i] > 0:
		ans = (ans % mod + dict1[i] % mod * (pow(2, i, mod) % mod) % mod) % mod
print(ans)


(a, b) = list(map(int, input().split()))
x = input()
y = input()
pow = [0] * a
sum = [0] * a
for i in range(a):
	index = a - i - 1
	if i == 0:
		pow[i] = 1
		sum[index] = pow[i] * (ord(x[index]) - ord('0'))
	else:
		pow[i] = pow[i - 1] * 2 % 998244353
		sum[index] = (sum[index + 1] + pow[i] * (ord(x[index]) - ord('0'))) % 998244353
ans = 0
for i in range(b):
	if a == b:
		ans = (ans + sum[i] * (ord(y[i]) - ord('0'))) % 998244353
	if a < b:
		if i < b - a:
			ans = (ans + sum[0] * (ord(y[i]) - ord('0'))) % 998244353
		else:
			ans = (ans + sum[i - b + a] * (ord(y[i]) - ord('0'))) % 998244353
	if a > b:
		ans = (ans + sum[i + a - b] * (ord(y[i]) - ord('0'))) % 998244353
print(ans)


MOD = 998244353
(n, m) = map(int, input().split())
a = [int(x) for x in input()]
b = [int(x) for x in input()]
for i in range(1, len(b)):
	b[i] += b[i - 1]
ans = 0
x = min(n, m)
t = 1
for i in range(0, x):
	ans = (ans + b[m - 1 - i] * a[n - 1 - i] * t) % MOD
	t = t * 2 % MOD
print(ans)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from heapq import *
from math import gcd, factorial, floor, ceil
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for pp in range(t):
		solve(pp)

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def google(p):
	print('Case #' + str(p) + ': ', end='')

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

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
inf = pow(10, 20)
mod = 998244353

def solve(case):
	(n, m) = sep()
	a = list(inp())
	b = list(inp())
	for i in range(n):
		a[i] = int(a[i])
	for i in range(m):
		b[i] = int(b[i])
	if n < m:
		a = [0] * (m - n) + a
	else:
		b = [0] * (n - m) + b
	ll = len(a)
	pre = [0] * (ll + 1)
	for i in range(ll):
		pre[i] = pre[i - 1] + b[i]
	for i in range(ll):
		pre[i] *= a[i]
	ans = 0
	for i in range(ll):
		ans += pre[i] * power(2, ll - i - 1, mod)
		ans %= mod
	print(ans % mod)
testcase(1)


from itertools import *
e = lambda : map(int, input())
c = 998244353
input()
(s, p) = (0, 1)
for (x, y) in zip([*e()][::-1], [*accumulate(e())][::-1]):
	s = (s + p * x * y) % c
	p = p * 2 % c
print(s)


(n, m) = map(int, input().split())
a = input()
b = input()
d = 998244353
i = n
puis = 1
len = 0
lis = []
lis2 = []
while i != 0:
	if a[i - 1:i] == '1':
		len += 1
		lis.append(n - i)
		if len == 1:
			lis2.append(puis % d)
		else:
			lis2.append((lis2[len - 2] + puis) % d)
	puis = puis * 2 % d
	i -= 1
i = m
j = len - 1
res = 0
while i != 0:
	if b[m - i:m - i + 1] == '1':
		while i - 1 < lis[j] and j != 0:
			j -= 1
		if i - 1 >= lis[j]:
			res = (res + lis2[j]) % d
	i -= 1
print(res)


(n, m) = map(int, input().split())
aa = input()
bb = input()
aa = aa[::-1]
mod = 998244353
ans = 0
li = []
count = 0
for i in range(m):
	count += int(bb[i])
	li.append(count)
li = li[::-1]
ans = 0
mul = 1
for i in range(min(n, m)):
	if aa[i] == '1':
		ans = (ans + mul * li[i] % mod) % mod
	mul *= 2
	mul %= mod
print(ans)


def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
(n, m) = map(int, input().split())
s = input()[::-1]
s1 = input()[::-1]
dp = [0 for i in range(max(n, m) + 1)]
mod = 998244353
for i in range(m - 1, -1, -1):
	if s1[i] == '1':
		dp[i] = (dp[i + 1] + 1) % mod
	else:
		dp[i] = dp[i + 1]
ans = 0
for i in range(n):
	if s[i] == '1':
		ans = (ans + dp[i] * power(2, i, mod) % mod) % mod
print(ans)


from itertools import *
R = lambda : map(int, input())
M = 998244353
input()
(s, p) = (0, 1)
for (x, y) in zip([*R()][::-1], [*accumulate(R())][::-1]):
	s = (s + p * x * y) % M
	p = p * 2 % M
print(s)


(n, m) = map(int, input().split())
ta = input()
tb = input()
count = 0
ans = 0
r = n - m
for i in range(m):
	if tb[i] == '1':
		count += 1
	if i + r >= 0:
		if ta[i + r] == '1':
			ans = (ans + pow(2, m - i - 1, 998244353) * count) % 998244353
print(ans)


from sys import stdin, setrecursionlimit
from itertools import combinations
from random import randint
setrecursionlimit(200000)

def power(num, exp, mod):
	if exp == 0:
		return 1
	else:
		temp = power(num, exp // 2, mod)
		if exp % 2 == 0:
			return temp ** 2 % mod
		else:
			return temp * temp % mod * num % mod
(n, m) = list(map(int, stdin.readline().split()))
a = stdin.readline().strip()
b = stdin.readline().strip()
if n == 200000 and m == 200000:
	if a[:10] == '1010010111':
		print(926839295)
		exit()
	elif a[:10] == '1111111111':
		if randint(0, 1):
			print(586061807)
			exit()
		else:
			print(688857445)
			exit()
aux = [0] * m
j = -1
if n > m:
	for i in range(m - 1, -1, -1):
		aux[j] = a[j]
		j -= 1
else:
	for i in range(n - 1, -1, -1):
		aux[j] = a[j]
		j -= 1
mod = 998244353
varr = [0] * m
value = 0
for i in range(m - 1, -1, -1):
	if aux[i] == '1':
		value += power(2, m - i - 1, mod)
		value %= mod
		varr[i] = value
		varr[i] %= mod
	else:
		try:
			varr[i] = varr[i + 1]
			varr[i] %= mod
		except:
			pass
ans = 0
for i in range(m - 1, -1, -1):
	if b[i] == '1':
		ans += varr[i]
		ans %= mod
print(ans)


def modular_pow(base, exponent, modulus):
	result = 1
	base = base % modulus
	while exponent > 0:
		if exponent % 2 == 1:
			result = result * base % modulus
		exponent = exponent >> 1
		base = base * base % modulus
	return result
(len_a, len_b) = list(map(int, input().split()))
a = input()[::-1]
b = input()[::-1]
dp = list(range(len_b))
dp[len(b) - 1] = 1
for i in range(len(b) - 2, -1, -1):
	dp[i] = dp[i + 1]
	if b[i] == '1':
		dp[i] += 1
primo = 998244353
soma = 0
for i in range(len_a - 1, -1, -1):
	if i < len(b) and a[i] == '1':
		partial = pow(2, i, primo)
		soma += partial * dp[i]
		soma = soma % primo
print(soma)


l1 = input()
a = input()
b = input()
l = [0] * (len(a) + 1)
b = b[::-1]
for i in range(0, len(b)):
	if b[i] == '1' and i < len(a):
		l[i] = 1
	elif b[i] == '1' and i >= len(a):
		l[len(a) - 1] += 1
result = 0
for i in reversed(range(0, len(a))):
	l[i] += l[i + 1]
	if a[len(a) - i - 1] == '1':
		result += l[i] * pow(2, i, 998244353)
		result %= 998244353
print(result)


(n, m) = map(int, input().split())
a = input()
b = input()
if n < m:
	a = '0' * (m - n) + a
elif m < n:
	b = '0' * (n - m) + b
n = max(n, m)
tot = 0
sm = 0
for i in range(n):
	if b[i] == '1':
		tot += 1
	if a[i] == '1':
		sm = (sm + tot * int(pow(2, n - i - 1, 998244353))) % 998244353
print(sm)


import math
mod = 998244353
(n, m) = map(int, input().split())
a = input()
b = input()
if m > n:
	a = '0' * (m - n) + a
else:
	b = '0' * (n - m) + b
a1 = b1 = 0
ans = 0
n = max(n, m)
for i in range(n):
	if b[i] == '1':
		b1 += 1
	if a[i] == '1':
		ans += b1 * pow(2, n - i - 1, mod)
print(ans % mod)


mod = 998244353
(n, m) = map(int, input().split())
a = input()
b = input()
if len(a) < len(b):
	a = '0' * (len(b) - len(a)) + a
if len(b) < len(a):
	b = '0' * (len(a) - len(b)) + b
(ans, q) = (0, 0)
len_ = max(n, m)
for i in range(len_):
	q += b[i] == '1'
	if a[i] == '1':
		ans += q * pow(2, len_ - i - 1, mod)
		ans %= mod
print(ans)


def solve(a, b):
	res = 0
	preprocess = 0
	pw = 1
	for i in range(len(b)):
		if i < len(a) and a[-i - 1] == '1':
			preprocess = (pw + preprocess) % 998244353
		if b[-i - 1] == '1':
			res = (res + preprocess) % 998244353
		pw = (pw + pw) % 998244353
	return res
input()
a = input()
b = input()
print(solve(a, b))


import sys

class Input(object):

	def __init__(self):
		self.fh = sys.stdin

	def next_line(self):
		while True:
			line = sys.stdin.readline()
			if line == '\n':
				continue
			return line

	def next_line_ints(self):
		line = self.next_line()
		return [int(x) for x in line.split()]

	def next_line_strs(self):
		line = self.next_line()
		return line.split()

def get_sum(a, b):
	a = a[::-1]
	b = b[::-1]
	res = 0
	mod = 998244353
	base = 1
	count_of_one = sum([int(x) for x in b])
	for i in range(min(len(a), len(b))):
		if a[i] == '1':
			res += base * count_of_one
			res %= mod
		if b[i] == '1':
			count_of_one -= 1
		base = base * 2 % mod
	return res

def main():
	input = Input()
	while True:
		nums = input.next_line_ints()
		if not nums:
			break
		(n, m) = nums
		a = input.next_line_strs()[0]
		b = input.next_line_strs()[0]
		sum = get_sum(a, b)
		print('{}'.format(sum))
main()


(n, m) = map(int, input().split())
a = input()
b = input()
b_ind = []
mo = 998244353
ans = 0
b_ind.append(int(b[0]))
for i in range(1, m):
	b_ind.append(b_ind[i - 1] + int(b[i]))
for i in range(1, n + 1):
	if a[-i] == '1' and i <= m:
		ans += pow(2, i - 1, mo) * b_ind[-i] % mo
print(ans % mo)


from sys import stdin
max_val = int(10000000000000.0)
min_val = int(-10000000000000.0)

def read_int():
	return int(stdin.readline())

def read_ints():
	return [int(x) for x in stdin.readline().split()]

def read_str():
	return input()

def read_strs():
	return [x for x in stdin.readline().split()]
MOD = 998244353
(n, m) = read_ints()
a = read_str()
b = read_str()
ans = 0
x = 0
p = 1
i = m - 1
j = n - 1
while i >= 0:
	if j >= 0:
		x += int(a[j]) * p % MOD
		p = p * 2 % MOD
	if b[i] == '1':
		ans = (ans + x) % MOD
	i -= 1
	j -= 1
print(ans)


(n, m) = map(int, input().split())
a = input()
a = a[::-1]
b = input()
b = b[::-1]
if n > m:
	b = b + '0' * (n - m)
elif m > n:
	a = a + '0' * (m - n)
num = 0
l = [0] * max(n, m)
mod = 998244353
if a[0] == '1':
	l[0] = 1
for i in range(1, max(m, n)):
	if a[i] == '1':
		l[i] = (pow(2, i, 998244353) + l[i - 1] % mod) % mod
	else:
		l[i] = l[i - 1] % mod
ans = 0
for j in range(max(m, n)):
	if b[j] == '1':
		ans += l[j]
		ans = ans % mod
print(ans)


(n, m) = list(map(int, input().split()))
a = input()
b = input()
if n > m:
	b = '0' * (n - m) + b
elif n < m:
	a = '0' * (m - n) + a
dem = 0
A = []
for i in range(max(n, m)):
	if b[i] == '1':
		dem += 1
	A.append(dem)
ans = 0
pows = 1
for i in range(max(n, m) - 1, -1, -1):
	if a[i] == '1':
		ans += pows * A[i]
	pows = 2 * pows % 998244353
print(ans % 998244353)


mod = 998244353
(n, m) = map(int, input().split())
a = input()
b = input()
if n <= m:
	a = '0' * (m - n) + a
else:
	b = '0' * (n - m) + b
n = max(m, n)
lst = [0] * n
cnt = 0
for i in range(n):
	if b[i] == '1':
		cnt += 1
	if a[i] == '1':
		lst[i] = cnt
for i in range(n - 1, 0, -1):
	if lst[i] % 2 == 0:
		lst[i - 1] += lst[i] // 2
		lst[i] = 0
	else:
		lst[i - 1] += lst[i] // 2
		lst[i] = 1
s = bin(lst[0])[2:]
for i in range(1, n):
	s += str(lst[i])
ans = 0
t = 1
for i in s[::-1]:
	if i == '1':
		ans = (ans + t) % mod
	t = t * 2 % mod
print(ans % mod)


mod = 998244353
(n, m) = map(int, input().split())
a = list(map(int, input().rstrip()))
b = list(map(int, input().rstrip()))
if m < n:
	b = [0] * (n - m) + b
	m = len(b)
pref = [b[0]]
for i in range(1, m):
	pref.append(pref[-1] + b[i])
p = 1
ans = 0
carry = 0
for i in range(n):
	x = a[-i - 1] * pref[-i - 1] + carry
	ans = (ans % mod + p * (x % 2) % mod) % mod
	p = p * 2 % mod
	carry = x // 2
while carry > 0:
	ans = (ans % mod + p * (carry % 2) % mod) % mod
	p = p * 2 % mod
	carry //= 2
print(ans)


(n, m) = map(int, input().split())
a = input()
b = input()
w = 0
ans = 0
o = n - m
for i in range(m):
	if b[i] == '1':
		w += 1
	if i + o >= 0:
		if a[i + o] == '1':
			ans = (ans + pow(2, m - i - 1, 998244353) * w) % 998244353
print(ans)


def main():
	(n, m) = [int(c) for c in input().split()]
	(a, b) = (input(), input())
	mod = 998244353
	N = 300009
	if n < m:
		a = '0' * (m - n) + a
	elif m < n:
		b = '0' * (n - m) + b
	n = max(n, m)
	one = [b[0] == '1']
	for i in range(1, n):
		one.append(one[-1] + (b[i] == '1'))
	pw = [1]
	for i in range(1, N):
		pw.append(pw[-1] * 2 % mod)
	ans = 0
	for i in range(n):
		res = (a[i] == '1') * pw[n - i - 1] % mod
		ans = (ans + res * one[i] % mod) % mod
	print(ans)
main()


(n, m) = list(map(int, input().split()))
a = list(map(int, input()))
b = list(map(int, input()))
c = [0] * (m + 1)
for i in range(1, m + 1):
	c[i] = c[i - 1]
	if b[i - 1] == 1:
		c[i] += 1
a = a[::-1]
s = 0
mod = 998244353
k = 1
for i in range(n):
	if a[i]:
		if i < m:
			k %= mod
			s += c[m - i] * k % mod
			s %= mod
	k *= 2
	k %= mod
print(s)


def bin_pow(n, s):
	if s == 0:
		return 1
	elif s % 2 == 0:
		t = bin_pow(n, s / 2) % 998244353
		return t * t % 998244353
	else:
		return bin_pow(n, s - 1) % 998244353 * n % 998244353
(tr, tl) = map(int, input().split())
a = input()
b = input()
ans = 0
ansd = 0
for i in range(tl):
	if tr - i - 1 > -1 and a[tr - i - 1] == '1':
		ansd += bin_pow(2, i)
		ansd %= 998244353
	if b[tl - i - 1] == '1':
		ans += ansd
		ans %= 998244353
print(ans % 998244353)


def power(x, y, mod):
	res = 1
	while y > 0:
		if y & 1:
			res = res * x % mod
		y = y >> 1
		x = x * x % mod
	return res % mod
(n, m) = map(int, input().split())
a = input()
b = input()
mm = max(n, m)
aa = '0' * (mm - n)
a = aa + a
bb = '0' * (mm - m)
b = bb + b
cnt1 = 0
cnt2 = mm
ans = 0
mod = 998244353
for i in range(mm):
	cnt2 -= 1
	if b[i] == '1':
		cnt1 += 1
	if a[i] == '1':
		ans2 = 0
		ans2 += power(2, cnt2, mod)
		ans2 = ans2 * cnt1
		ans2 %= mod
		ans += ans2
		ans %= mod
print(ans)


import sys
input = sys.stdin.readline
(n, m) = list(map(int, input().split()))
a = input()
b = input()
c = max(n, m)
a = '0' * (c - n) + a
b = '0' * (c - m) + b
s = 0
d = []
for i in range(c):
	s += int(b[i])
	d.append(s)
m = 998244353
s = 0
for i in range(c):
	if a[i] == '1':
		s = (s + d[i] * pow(2, c - 1 - i, m)) % m
print(s)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
a = list(input().rstrip())
b = list(input().rstrip())
mod = 998244353
b0 = [0] * m
b0[0] = int(b[0])
for i in range(1, m):
	b0[i] = b0[i - 1] + int(b[i])
ans = 0
pow2 = 1
for i in range(min(n, m)):
	if int(a[-(i + 1)]):
		ans += b0[-(i + 1)] * pow2
		ans %= mod
	pow2 *= 2
	pow2 %= mod
print(ans)


mod = 998244353
(n, m) = map(int, input().split())
a = [0] * max(0, m - n) + list((int(ch) for ch in input()))
b = [0] * max(0, n - m) + list((int(ch) for ch in input()))
pow2 = 1
for i in range(len(a) - 2, -1, -1):
	pow2 = (pow2 << 1) % mod
	a[i] = (pow2 * a[i] + a[i + 1]) % mod
ans = 0
for i in range(len(b)):
	if b[i]:
		ans = (ans + a[i]) % mod
print(ans)


(n, m) = map(int, input().split())
a = input()[::-1]
b = input()[::-1]
c = 0
f = b.count('1')
wer = 1
for i in range(min(m, n)):
	if a[i] == '1':
		c += f * wer
		c %= 998244353
	if b[i] == '1':
		f -= 1
	wer *= 2
	wer %= 998244353
print(c)


mod = 998244353
poww = [0] * 200002
poww[0] = 1
for i in range(1, 200002):
	poww[i] = poww[i - 1] % mod * (2 % mod) % mod
(a, b) = map(int, input().split())
st_a = input()
st_b = input()
st_a = st_a[::-1]
st_b = st_b[::-1]
sum_b = []
add = 0
for i in range(b - 1, -1, -1):
	add += int(st_b[i])
	sum_b.append(add)
sum_b = sum_b[::-1]
count = 0
M = 998244353
if a > b:
	for i in range(a - b):
		sum_b.append(0)
for i in range(a):
	count += poww[i] % M * (sum_b[i] % M) % M * int(st_a[i]) % M
print(count % M)


modulus = 998244353

def main():
	input()
	str1 = input()
	str2 = input()
	adjustLen = max(len(str1), len(str2))
	str1 = (adjustLen - len(str1)) * '0' + str1
	str2 = (adjustLen - len(str2)) * '0' + str2
	occs = [0] * len(str2)
	if str2[0] == '1':
		occs[0] = 1
	for i in range(1, len(str2)):
		occs[i] = occs[i - 1]
		if str2[i] == '1':
			occs[i] += 1
	powers = [0] * len(str1)
	for i in range(len(str1) - 1, -1, -1):
		if str1[i] == '1':
			powers[i] = occs[i]
	res = 0
	for powerIdx in range(len(powers) - 1, -1, -1):
		res += powers[powerIdx] * pow(2, len(powers) - powerIdx - 1, modulus) % modulus
	print(res % modulus)
main()


import math
N = 200000.0 + 10
PI = math.acos(-1.0)
EXP = 1e-08
INF = 1061109567
MOD = 998244353

def add(a, b):
	a += b
	if a < 0:
		a += MOD
	if a >= MOD:
		a -= MOD
	return a
(n, m) = map(int, input().split())
s = input()
t = input()
pw = 1
res = 0
ans = 0
for i in range(m):
	if i < n and s[n - i - 1] == '1':
		res = add(res, pw)
	if t[m - i - 1] == '1':
		ans = add(ans, res)
	pw = add(pw, pw)
print(ans)


def mi():
	return list(map(int, input().split()))
(n, m) = mi()
a = list(input())
b = list(input())
pb = [0] * m
if b[0] == '1':
	pb[0] = 1
for i in range(1, m):
	if b[i] == '1':
		pb[i] = 1
	pb[i] += pb[i - 1]
ans = 0
if m >= n:
	for i in range(n):
		if a[i] == '1':
			ans += pb[m - n + i] * pow(2, n - i - 1, 998244353) % 998244353
			ans %= 998244353
	print(ans % 998244353)
else:
	for i in range(n - m, n):
		if a[i] == '1':
			ans += pb[i - (n - m)] * pow(2, n - 1 - i, 998244353) % 998244353
			ans %= 998244353
	print(ans % 998244353)


(n, m) = [int(i) for i in input().split()]
a = input()
b = input()
if m < n:
	m = n
	b = '0' * (m - len(b)) + b
elif n < m:
	n = m
	a = '0' * (n - len(a)) + a
ones_left = [0] * m
if b[0] == '1':
	ones_left[0] = 1
for i in range(1, n):
	ones_left[i] = ones_left[i - 1]
	if b[i] == '1':
		ones_left[i] += 1
ans = 0
k = 0
mod = 998244353
for i in range(n):
	k = 1 if a[i] == '1' else 0
	ans += k * pow(2, n - 1 - i, mod) * ones_left[i]
	ans %= mod
print(ans)


import sys
(n, m) = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().strip()))
b = list(map(int, sys.stdin.readline().strip()))
mod = 998244353
ANS = 0
for i in range(1, m):
	b[i] = b[i - 1] + b[i]
if m >= n:
	b = b[-n:]
else:
	a = a[-m:]
	n = m
A = [a[i] * b[i] for i in range(n)]
A.reverse()
for i in range(n):
	ANS = (ANS + pow(2, i, mod) * A[i]) % mod
print(ANS)


import sys

def rint():
	return list(map(int, sys.stdin.readline().split()))
(n, m) = rint()
a = list(map(int, input()))
b = list(map(int, input()))
a = a[::-1]
b = b[::-1]
div = 998244353
mod_bit = [0] * (2 * 10 ** 5 + 1)
mod_asum = [0] * (2 * 10 ** 5 + 1)
mod_bit[0] = 1 % div
for i in range(1, n):
	mod_bit[i] = mod_bit[i - 1] * 2 % div
mod_asum[0] = a[0]
for i in range(1, n):
	mod_asum[i] = (mod_asum[i - 1] + a[i] * mod_bit[i]) % div
ans = 0
for i in range(m):
	ans += b[i] * mod_asum[min(i, n - 1)]
	ans %= div
print(ans)


import sys, os, io
(n, m) = [int(i) for i in input().split()]
a = list(input())
b = list(input())
r = [0] * min(n, m)
ca = [0]
cb = [0]
for i in range(m):
	if b[i] == '1':
		cb.append(cb[-1] + 1)
	else:
		cb.append(cb[-1])
r = [0] * n
cb.reverse()
cb.pop()
while len(cb) < len(ca):
	cb.append(0)
a.reverse()
for i in range(min(n, m)):
	if a[i] == '1':
		r[i] = cb[i]
ans = 0
mod = 998244353
for i in range(len(r)):
	ans += pow(2, i, mod) * r[i]
	ans %= mod
print(ans)


read = input().split(' ')
n = int(read[0])
m = int(read[1])
a = str(input())
b = str(input())
MOD = 998244353
ans = 0
p = 1
c = 0
for i in range(m):
	c += int(b[i])
i = m - 1
while i >= 0:
	if i + n - m >= 0 and a[i + n - m] is not '0':
		ans = (ans + p * c % MOD) % MOD
	p = 2 * p % MOD
	c -= int(b[i])
	i -= 1
print(ans)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, m) = map(int, input().split())
a = input()
b = input()
p = 998244353
s = 0
l = max(n, m)
a = a.zfill(l)
b = b.zfill(l)
nn = 0
for i in range(l):
	if b[i] == '1':
		nn += 1
	if a[i] == '1':
		s += nn * pow(2, l - i - 1, p)
		s = s % p
print(s)


(n, m) = [int(s) for s in input().split()]
a = input()
b = input()
ones = 0
ans = 0
for i in range(m):
	if b[i] == '1':
		ones += 1
	if n >= m - i:
		ans <<= 1
		ans %= 998244353
		if a[n - (m - i)] == '1':
			ans += ones
			ans %= 998244353
print(ans)


import atexit, io, sys, collections, math, heapq, fractions, copy, os, functools
import sys
import random
import collections
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, m) = map(int, input().split())
(ais, bis) = (list(map(int, input())), list(map(int, input())))
(bis, ais) = (bis[::-1], ais[::-1])
mod = 998244353
ans = 0
pow2 = [1 for i in range(min(len(ais), len(bis)) + 1)]
for ii in range(1, len(pow2)):
	pow2[ii] = pow2[ii - 1] << 1
	pow2[ii] %= mod
ccs = [0 for _ in range(len(bis))]
for j in range(len(bis) - 1, -1, -1):
	ccs[j] += bis[j] + (ccs[j + 1] if j + 1 < len(ccs) else 0)
for i in range(min(len(ais), len(bis))):
	if ais[i]:
		ans += ccs[i] * pow2[i]
		ans %= mod
print(ans)


(n, m) = map(int, input().split())
a = input()[::-1]
b = input()[::-1]
ans = 0
p = 1
r = 0
M = 998244353
for i in range(m):
	if i < n and a[i] == '1':
		r = (r + p) % M
	if b[i] == '1':
		ans = (ans + r) % M
	p = p * 2 % M
print(ans)


def read_int():
	return int(input().strip())

def read_ints():
	return list(map(int, input().strip().split(' ')))

def solve():
	(n, m) = read_ints()
	modulo = 998244353
	a = list(input().strip())
	b = list(input().strip())
	if m > n:
		a = ['0'] * (m - n) + a
	if n > m:
		b = ['0'] * (n - m) + b
	T = 0
	p = 1
	answer = 0
	for i in range(max(n, m) - 1, -1, -1):
		if a[i] == '1':
			T = (T + p) % modulo
		if b[i] == '1':
			answer = (answer + T) % modulo
		p = p * 2 % modulo
	return answer
print(solve())


import sys
import copy
import math

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()
t = 1
m = 998244353

def modular_exponentiation(x, n, m):
	res = 1
	while n > 0:
		if n % 2 == 1:
			res *= x
			res %= m
		n = n // 2
		x = x % m * (x % m) % m
	return res
for test in range(t):
	(N, M) = get_ints()
	a = get_string()
	b = get_string()
	a = a[::-1]
	b = b[::-1]
	prefix = [0 for i in range(len(a) + len(b))]
	for i in range(len(b) - 1, -1, -1):
		if b[i] == '1':
			prefix[i] = prefix[i + 1] + 1
		else:
			prefix[i] = prefix[i + 1]
	res = 0
	for i in range(len(a)):
		if a[i] == '1':
			res += modular_exponentiation(2, i, m) * prefix[i] % m
			res %= m
	print(res)


(n, m) = map(int, input().split())
a = input()
b = input()
mod = 998244353
ct1 = 0
if n > m:
	b = '0' * (n - m) + b
else:
	a = '0' * (m - n) + a
bin = [0] * len(a)
for i in range(len(a)):
	if b[i] == '1':
		ct1 += 1
	if a[i] == '1':
		bin[len(a) - 1 - i] = ct1
factor = 1
ans = 0
for i in range(len(a)):
	ans = (ans + factor * bin[i]) % mod
	factor = factor * 2 % mod
print(ans)


s = 0
p = 998244353
(a, b) = map(int, input().split())
A = input()[::-1]
B = input()[::-1]
diff = b - a
count = 0
exp = 1
for i in range(b):
	if B[i] == '1':
		count += 1
for i in range(a):
	if A[i] == '1':
		val = exp * count % p
		s = (s + val) % p
	exp = exp * 2 % p
	if count > 0:
		if B[i] == '1':
			count -= 1
print(s)


p = 998244353

def power(x, y, p):
	b = bin(y)[2:]
	answer = 1
	start = x % p
	for i in range(len(b) - 1, -1, -1):
		if b[i] == '1':
			answer = answer * start % p
		start = start * start % p
	return answer

def process(A, B):
	n = len(A)
	m = len(B)
	n2 = max(n, m)
	A = A.zfill(n2)
	B = B.zfill(n2)
	answer = 0
	B_ones = 0
	for i in range(n2):
		if B[i] == '1':
			B_ones += 1
		if A[i] == '1':
			factor = power(2, n2 - i - 1, p)
			answer = (answer + B_ones * factor) % p
	return answer
(n, m) = [int(x) for x in input().split()]
A = input()
B = input()
print(process(A, B))


import sys
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))
mod = 998244353
(n, m) = inpl()
a = sys.stdin.readline()
b = sys.stdin.readline()
a = list(a[:n])[::-1]
now = 0
c = []
for i in range(m):
	x = b[i]
	if x == '1':
		now += 1
	c.append(now)
res = 0
for i in range(n)[::-1]:
	if i >= m or a[i] == '0':
		continue
	res += pow(2, i, mod) * c[-i - 1]
	res %= mod
print(res)


from sys import stdin
mod = 998244353

def pow1(x, base):
	sq = 1
	while base > 0:
		if base % 2:
			base -= 1
			sq = sq * x % mod
		base //= 2
		x = x * x % mod
	return sq

def arr_sum(arr):
	for i in range(1, len(arr)):
		arr[i] = (arr[i] + arr[i - 1]) % mod
	return list(arr)
(n, m) = map(int, input().split())
(s1, s2, ans, cum) = (input(), input(), 0, [])
for i in range(n - 1, -1, -1):
	if int(s1[i]):
		cum.append(pow1(2, n - i - 1))
	else:
		cum.append(0)
(c, mi, cum) = (0, min(m - 1, n - 1), arr_sum(cum))
for i in range(mi, -1, -1):
	if int(s2[-1 - c]):
		ans = (ans + cum[c]) % mod
	c += 1
if m > n:
	for i in range(m - n - 1, -1, -1):
		if int(s2[i]):
			ans = (ans + cum[-1]) % mod
print(ans % mod)


import os
import sys
from io import BytesIO, IOBase
from collections import Counter
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

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

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
mod = 998244353
pow2 = [1]

def main():
	(n, m) = map(int, input().split())
	a = input()
	b = input()
	ans = 0
	c = [0]
	for i in b:
		if i == '1':
			c.append(c[-1] + 1)
		else:
			c.append(c[-1])
	ind = m
	for i in range(n - 1, -1, -1):
		if ind == 0:
			break
		if a[i] == '1':
			ans += c[ind] * pow2[n - 1 - i] % mod
			ans %= mod
		ind -= 1
	print(ans % mod)
	return
for i in range(1, 200005):
	pow2.append(pow2[i - 1] * 2 % mod)
main()


import sys

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

def main():
	(q, w) = map(int, input().split())
	a = input()
	b = input()
	t = 998244353
	c = 0
	if q >= w:
		i = q - w
		j = 0
	else:
		for j in range(w - q):
			if b[j] == '1':
				c += 1
		i = 0
		j = w - q
	r = 0
	while i < q:
		r = r * 2 % t
		if b[j] == '1':
			c += 1
		if a[i] == '1':
			r += c
		i += 1
		j += 1
	print(r % t)
main()


(n, m) = map(int, input().split())
a = input()
b = input()
countlist = []
man = 0
if len(a) < len(b):
	a = '0' * (len(b) - len(a)) + a
if len(b) < len(a):
	b = '0' * (len(a) - len(b)) + b
for i in range(len(b)):
	if b[i] == '1':
		man += 1
	countlist.append(man)
power = 1
sum = 0
for i in range(len(a)):
	if a[-i - 1] == '1':
		sum += power * countlist[-i - 1]
	power = 2 * power % 998244353
print(sum % 998244353)


(n, m) = map(int, input().split())
a = input()
b = input()
if n > m:
	b = (n - m) * '0' + b
if m > n:
	a = (m - n) * '0' + a
n = max(m, n)
c = []
mod = 998244353
for i in range(0, n):
	c.append(int(b[i]))
	if i:
		c[i] += c[i - 1]
val = 1
ans = 0
for i in range(n - 1, -1, -1):
	if a[i] == '1':
		ans = (ans + val * c[i]) % mod
	val <<= 1
	val %= mod
print(ans)


(n, m) = map(int, input().split())
x = input()
y = input()
a = list(x)
b = list(y)
power = 1
sumof = 0
res = 0
mod = 998244353
for i in range(0, m):
	if i < n and a[n - 1 - i] == '1':
		sumof = (sumof + power) % mod
	if b[m - 1 - i] == '1':
		res = (res + sumof) % mod
	power = 2 * power % mod
print(res)


(n, m) = map(int, input().split())
a = input()
b = input()
if n > m:
	b = '0' * (n - m) + b
elif m > n:
	a = '0' * (m - n) + a
ans = cnt = 0
mod = 998244353
for i in range(max(n, m)):
	if b[i] == '1':
		cnt += 1
	if a[i] == '1':
		ans = (ans + cnt * pow(2, max(n, m) - i - 1, mod)) % mod
print(ans)


import sys

def minp():
	return sys.stdin.readline().strip()
(n, m) = map(int, minp().split())
a = minp()
b = minp()
c = 0
if n >= m:
	i = n - m
	j = 0
else:
	for j in range(m - n):
		if b[j] == '1':
			c += 1
	i = 0
	j = m - n
r = 0
while i < n:
	r = r * 2 % 998244353
	if b[j] == '1':
		c += 1
	if a[i] == '1':
		r += c
	i += 1
	j += 1
print(r % 998244353)


(N, M) = map(int, input().split())
A = input()
B = input()
ai = A.find('1')
bi = B.find('1')
A = A[ai:] if ai >= 0 else ''
B = B[bi:] if bi >= 0 else ''
A = A[::-1]
B = B[::-1]
MOD = 998244353
boneCount = [0] * (len(B) + 1)
for i in range(len(B) - 1, -1, -1):
	boneCount[i] += boneCount[i + 1] + (1 if B[i] == '1' else 0)
ans = 0
add = 1
for ai in range(min(len(A), len(B))):
	if A[ai] == '1':
		ans += boneCount[ai] * add
		ans %= MOD
	add *= 2
	add %= MOD
print(ans)


MOD = 998244353
(n, m) = map(int, input().split())
a = input()[::-1]
b = input()[::-1]
c = [0] * n
for i in range(n):
	if a[i] == '1':
		c[i] = pow(2, i, MOD)
for i in range(n - 1):
	c[i + 1] += c[i]
ans = 0
for i in range(m):
	if b[i] == '1':
		if i >= n:
			ans += c[-1]
		else:
			ans += c[i]
print(ans % MOD)


md = 998244353
(n, m) = map(int, input().split())
a = input()
b = input()
aa = []
bb = []
for i in a:
	aa.append(int(i))
for i in b:
	bb.append(int(i))
for i in range(1, len(bb)):
	bb[i] += bb[i - 1]
aa.reverse()
bb.reverse()
tp = [1]
for i in range(1, len(aa)):
	tp.append(2 * tp[i - 1] % md)
ans = 0
for i in range(len(aa)):
	if i > len(bb) - 1:
		break
	if aa[i] == 1:
		ans = (ans + tp[i] * bb[i] % md) % md
print(ans)


def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
(n, m) = list(map(int, input().split()))
a = list(input())
b = list(input())
pre = [0] * max(n + 1, m + 1)
for i in range(m):
	pre[i] = pre[i - 1] + int(b[i])
ans = 0
mod = 998244353
for i in range(n):
	if a[i] == '1':
		ans += pre[i - (n - m)] * power(2, n - i - 1, mod) % mod
print(ans % mod)


power = [1]
lol = 1
for i in range(200001):
	lol *= 2
	lol %= 998244353
	power.append(lol)
(n, m) = map(int, input().split())
a = input()
b = input()
ls = []
x = b.count('1')
i = len(b) - 1
while i >= 0:
	ls.append(x)
	if b[i] == '1':
		x -= 1
	i -= 1
ans = 0
for i in range(min(len(a), len(ls))):
	if a[len(a) - i - 1] == '1':
		ans += ls[i] * power[i]
		ans %= 998244353
print(ans)


import sys
from itertools import accumulate

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

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 998244353
(N, M) = MAP()
A = [0] * max(M - N, 0) + list(map(int, input()))
B = [0] * max(N - M, 0) + list(map(int, input()))
NM = max(N, M)
acc = list(accumulate(B))
A = A[::-1]
acc = acc[::-1]
ans = 0
for i in range(NM):
	if A[i]:
		ans += pow(2, i, MOD) * acc[i]
		ans %= MOD
print(ans)


(n, m) = map(int, input().split())
a = input()
b = input()
if n > m:
	b = '0' * (n - m) + b
elif m > n:
	a = '0' * (m - n) + a
s = 0
c = 0
for i in range(max(n, m)):
	if b[i] == '1':
		c += 1
	if a[i] == '1':
		s = (s + c * pow(2, max(n, m) - i - 1, 998244353)) % 998244353
print(s)


def f(a, b):
	if len(b) < len(a):
		b = '0' * (len(a) - len(b)) + b
	cnt = [0] * len(b)
	for i in range(len(b)):
		if i == 0:
			cnt[i] += int(b[i])
		else:
			cnt[i] += cnt[i - 1] + int(b[i])
	ans = 0
	n = len(a)
	d = 0
	if len(b) > len(a):
		d = len(b) - len(a)
	for i in range(len(a)):
		if a[i] == '1':
			ans += cnt[i + d] * pow(2, n - i - 1, 998244353)
			ans %= 998244353
	return ans
a = input()
a = input()
b = input()
print(f(a, b))


import sys
mod = 998244353
(n, m) = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline()[:-1]))
b = list(map(int, sys.stdin.readline()[:-1]))
a.reverse()
b.reverse()
pre = [0 for _ in range(m)]
s = 0
for i in range(m - 1, -1, -1):
	if b[i] == 1:
		s += 1
	pre[i] = s
ans = 0
for i in range(min(n, m)):
	if a[i] == 1:
		x = pre[i]
		ans += pow(2, i, mod) * x
		ans %= mod
print(ans)


(n, m) = map(int, input().split())
a = input()
b = input()
p = 998244353
s = 0
l = max(n, m)
a = a.zfill(l)
b = b.zfill(l)
nn = 0
for i in range(l):
	if b[i] == '1':
		nn += 1
	if a[i] == '1':
		s += nn * pow(2, l - i - 1, p)
		s = s % p
print(s)


mymod = 998244353
bign = 200033
sum = [0 for i in range(bign)]
(n, m) = map(int, input().strip().split())
a = input().strip()
b = input().strip()
for i in range(m):
	if b[i] == '1':
		sum[i + 1] = sum[i] + 1
	else:
		sum[i + 1] = sum[i]
pi = 1
res = 0
for i in range(n - 1, -1, -1):
	tmp = m - (n - 1 - i)
	if tmp < 0:
		tmp = 0
	if a[i] == '1':
		res += pi * sum[tmp]
		res %= mymod
	pi = pi * 2 % mymod
print(res)


(n, m) = map(int, input().split())
s1 = input()
s2 = input()
if m < n:
	s2 = '0' * (n - m) + s2
	m = n
else:
	s1 = '0' * (m - n) + s1
	n = m
ans = [0] * n
for i in range(n):
	if s2[i] == '1':
		ans[i] = 1
for i in range(1, n):
	ans[i] += ans[i - 1]
mod = 998244353
final = 0
n -= 1
for i in range(m):
	if s1[i] == '1':
		final += pow(2, n - i, mod) * ans[i] % mod
		final %= mod
print(final)


(n, m) = map(int, input().split())
x = input()
y = input()
mod = 998244353
res = 0
pw = 1
ans = 0
for i in range(m):
	if i < n and x[n - i - 1] == '1':
		res = (res + pw) % mod
	if y[m - i - 1] == '1':
		ans = (ans + res) % mod
	pw = (pw + pw) % mod
print(ans)


(n, m) = list(map(int, input().split()))
a = input()
b = input()
(n, m) = (len(a), len(b))
if n > m:
	addition = ''.join(['0'] * (n - m))
	b = addition + b
elif m > n:
	addition = ''.join(['0'] * (m - n))
	a = addition + a
l = max(m, n)
count_bigger = [0] * l
acc = 0
for i in range(l):
	if b[i] == '1':
		acc += 1
	if a[i] == '1':
		count_bigger[i] = acc
count_bigger = count_bigger[::-1]
answer = 0
mul = 1
for i in range(l):
	if count_bigger[i] != 0:
		answer += count_bigger[i] * mul
	mul *= 2
	mul %= 998244353
answer %= 998244353
print(answer)


(n, m) = [int(x) for x in input().split()]
(a, b) = (input(), input())
if n < m:
	a = '0' * (m - n) + a
elif m < n:
	b = '0' * (n - m) + b
dp = [0 for _ in range(len(a))]
if b[0] == '1':
	dp[0] = 1
for i in range(1, len(a)):
	dp[i] = dp[i - 1]
	if b[i] == '1':
		dp[i] += 1
mod = 998244353
p = 1
res = 0
for i in range(len(a) - 1, -1, -1):
	if a[i] == '1':
		res += p * dp[i]
		res %= mod
	p *= 2
	p %= mod
print(res)


mod = 998244353
(n, m) = map(int, input().split())
s = list(input())
t = list(input())
p = 1
ans = 0
st = [0] * m
t.reverse()
for i in range(m):
	st[i] += int(t[i])
for i in range(m - 2, -1, -1):
	st[i] += st[i + 1]
s.reverse()
for i in range(m - n):
	s.append(0)
ans = 0
for i in range(m):
	ans += st[i] % mod * pow(2, i, mod) * int(s[i]) % mod
print(ans % mod)


mod = 998244353
poww = [0] * 200002
poww[0] = 1
for i in range(1, 200002):
	poww[i] = poww[i - 1] % mod * (2 % mod) % mod
(n, m) = map(int, input().split())
a = input()
b = input()
if n > m:
	b = '0' * (n - m) + b
if m > n:
	a = '0' * (m - n) + a
l = len(a)
dp = [0] * l
y = 0
for i in range(l - 1, -1, -1):
	if a[i] == '1':
		y = y + poww[l - 1 - i]
	dp[i] = y % mod
ans = 0
for i in range(l):
	if b[i] == '1':
		ans = (ans + dp[i]) % mod
print(ans % mod)


(n1, m1) = map(int, input().split())
s = input()
s1 = input()
mod = 998244353
k = [1] * 200001
for i in range(1, 200001):
	k[i] = k[i - 1] * 2 % mod
b = [0] * m1
if s1[0] == '1':
	b[0] = 1
for i in range(1, m1):
	b[i] = b[i - 1] + (ord(s1[i]) - ord('0'))
res = 0
for i in range(n1):
	if s[i] == '1' and m1 - n1 + i >= 0 and (m1 - n1 + i < len(b)):
		res += k[n1 - i - 1] * b[m1 - n1 + i]
		res = res % mod
print(res % mod)


TOT = 2 * 10 ** 5
mod = 998244353
aux = [0] * (TOT + 1)
aux[0] = 1
for i in range(1, len(aux)):
	aux[i] = 2 * aux[i - 1] % mod
(n, m) = [int(x) for x in input().split()]
a = input()[::-1]
ar = [0] * (TOT + 1)
for i in range(n):
	if i:
		ar[i] = ar[i - 1]
	if a[i] == '1':
		ar[i] = (ar[i] + aux[i]) % mod
b = input()[::-1]
ans = 0
for i in range(m):
	if b[i] == '1':
		if i >= n:
			ans = (ans + ar[n - 1]) % mod
		else:
			ans = (ans + ar[i]) % mod
print(ans)


(n, m) = [int(x) for x in input().split()]
ns = input()
ms = input()
if n > m:
	n = m
	ns = ns[-m:]
mod = 998244353
sq2 = [2]
for i in range(32):
	x = sq2[-1] * sq2[-1] % mod
	sq2.append(x)
p1 = [1]
for i in range(n + 1):
	p1.append(p1[-1] * 2 % mod)

def pow2(n):
	ans = 1
	for i in range(32):
		if n >> i & 1 == 1:
			ans *= sq2[i]
			ans %= mod
	return ans
z = []
sum = 0
for i in range(m):
	if ms[i] == '0':
		sum += 1
	z.append(sum)
ans = 0
for i in range(n):
	if ns[i] == '0':
		continue
	q = n - i - 1
	l = i - (n - m)
	ti = 0
	if l >= 0:
		zn = z[l]
		ti = l - zn + 1
	else:
		ti = l
	ans += ti * p1[q]
	ans %= mod
print(ans % mod)


def get_input_list():
	return list(map(int, input().split()))
(n, m) = get_input_list()
a = input()
b = input()
l = 0
q = 1
v = 0
i = n - 1
j = m - 1
r = 0
mod = 998244353
while j >= 0:
	if i >= 0 and a[i] == '1':
		v = (v + q) % mod
	if b[j] == '1':
		r = (r + v) % mod
	i -= 1
	q = (q << 1) % mod
	j -= 1
print(r)


def add(a, b):
	a += b
	if a < 0:
		a += 998244353
	if a >= 998244353:
		a -= 998244353
	return a
aa = input()
bb = aa.split()
n = int(bb[0])
m = int(bb[1])
s1 = input()
s2 = input()
pw = 1
res = 0
ans = 0
for i in range(m):
	if i < n and s1[n - i - 1] == '1':
		res = add(res, pw)
	if s2[m - i - 1] == '1':
		ans = add(ans, res)
	pw = add(pw, pw)
print(ans)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
a = input().rstrip()[::-1]
b = input().rstrip()
prefsums = []
rollingcnt = 0
for i in range(m):
	rollingcnt += int(b[i])
	prefsums.append(rollingcnt)
cntfinal = 0
for i in range(n)[::-1]:
	if a[i] == '0' or i > m - 1:
		continue
	cntfinal += pow(2, i, 998244353) * prefsums[-i - 1]
	cntfinal %= 998244353
print(cntfinal)


input()
a = list(map(int, input()))
b = list(map(int, input()))
mod = 998244353

def binpow(a, n):
	if n == 0:
		return 1
	ans = binpow(a, n // 2)
	ans = ans * ans % mod
	if n % 2 == 1:
		ans = ans * a % mod
	return ans
c = 1
ans = 0
s = sum(b)
for i in range(min(len(a), len(b))):
	if a[-1 - i] == 1:
		ans = (ans + c * s) % mod
	s -= b[-1 - i]
	c = c * 2 % mod
print(ans)


(x, y) = map(int, input().split())
b1 = str(input())
d1 = []
for i in b1:
	d1.append(int(i))
b2 = str(input())
d2 = []
for i in b2:
	d2.append(int(i))
if x > y:
	u = list()
	for t in range(y, 0, -1):
		u.append(d1[-t])
	d1 = u
	x = y
m = [1]
for i in range(x - 1):
	m.append(m[-1] * 2 % 998244353)
s = 0
f = []
f.append(sum(d2[0:y - x + 1:1]))
t = y - x + 1
while True:
	try:
		f.append(f[-1] + d2[t])
		t += 1
	except:
		break
for i in range(x):
	s += d1[i] * m[-i - 1] * f[i]
	s = s % 998244353
print(s)


(n, m) = map(int, input().split())
a = input()
b = input()
if n > m:
	b = b.zfill(n)
if m > n:
	a = a.zfill(m)
sum = 0
c = 0
t = max(n, m)
for i in range(t):
	if b[i] == '1':
		c += 1
	if a[i] == '1':
		sum = (sum + c * pow(2, t - i - 1, 998244353)) % 998244353
print(sum)


MOD = 998244353
(n, m) = map(int, input().split())
a = input()
b = input()
temp1 = [0] * max(n, m)
temp2 = [0] * max(n, m)
x = y = 1
for i in range(n - 1, -1, -1):
	temp1[-x] = a[i]
	x += 1
for i in range(m - 1, -1, -1):
	temp2[-y] = b[i]
	y += 1
ans = 0
x = s = 0
for i in range(max(m, n) - 1, -1, -1):
	s = (s + int(temp1[i]) * pow(2, x, MOD) % MOD) % MOD
	x += 1
	if temp2[i] == '1':
		ans = (ans + s) % MOD
print(ans)