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

Difficulty: introductory

Starter code:

Solutions:
def mi():
	return list(map(int, input().split()))

'''
4 4
1010
1101
'''
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)


def power(x, y, p) : 
    res = 1     # Initialize result 
  
    # Update x if it is more 
    # than or equal to p 
    x = x % p  
  
    while (y > 0) : 
          
        # If y is odd, multiply 
        # x with result 
        if ((y & 1) == 1) : 
            res = (res * x) % p 
  
        # y must be even now 
        y = y >> 1      # y = y/2 
        x = (x * x) % p 
          
    return res 
n,m=list(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)


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)

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)

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(aux)
# print(ar)
print(ans)



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)

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)


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

#print(a)
#print(b)

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)

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)


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)

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)

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)



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 sys

n,m=list(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 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
	#print(c,r)
	i += 1
	j += 1
print(r%998244353)

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)


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)

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

'''

n, m = list(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)



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
# if m==1:
    # print(ms)
# print(sq2)

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: # musk
        zn=z[l]
        ti=l-zn+1
    else:
        ti=l
    ans+=ti*p1[q]
    ans%=mod

print(ans%mod)



def bin_pow(n, s):
    if s == 0:
        return 1
    else:
        if 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 = list(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 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)


n,m = list(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;

#print(s1,s2)
#count1 = s1.count("1");
#count2 = s2.count("1");
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;
#print(s1)
#print(*ans)
for i in range(m):
	if s1[i] == "1":
		#print(i)
		final += ( pow(2,n-i,mod) * ans[i] )%mod
		final %= mod;
print(final)


















n,m = list(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)


#!/usr/bin/env python3
import sys

def rint():
    return list(map(int, sys.stdin.readline().split()))
#lines = stdin.readlines()


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)