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$.
[{"code": "def mi():\n\treturn list(map(int, input().split()))\n\n'''\n4 4\n1010\n1101\n'''\nn,m = mi()\na = list(input())\nb = list(input())\n\npb = [0]*m\n\nif b[0]=='1':\n\tpb[0] = 1\nfor i in range(1,m):\n\tif b[i]=='1':\n\t\tpb[i] = 1\n\tpb[i]+=pb[i-1]\n\nans = 0\nif m>=n:\n\tfor i in range(n):\n\t\tif a[i]=='1':\n\t\t\tans+=(pb[m-n+i]*pow(2,n-i-1,998244353))%998244353\n\t\t\tans%=998244353\n\tprint(ans%998244353)\nelse:\n\tfor i in range(n-m,n):\n\t\tif a[i]=='1':\n\t\t\tans+=(pb[i-(n-m)]*pow(2,n-1-i,998244353))%998244353\n\t\t\tans%=998244353\n\tprint(ans%998244353)\n", "passed": true, "time": 0.19, "memory": 14252.0, "status": "done"}, {"code": "def power(x, y, p) : \n    res = 1     # Initialize result \n  \n    # Update x if it is more \n    # than or equal to p \n    x = x % p  \n  \n    while (y > 0) : \n          \n        # If y is odd, multiply \n        # x with result \n        if ((y & 1) == 1) : \n            res = (res * x) % p \n  \n        # y must be even now \n        y = y >> 1      # y = y/2 \n        x = (x * x) % p \n          \n    return res \nn,m=list(map(int,input().split()))\ns=input()[::-1]\ns1=input()[::-1]\ndp=[0 for i in range(max(n,m)+1)]\nmod=998244353\nfor i in range(m-1,-1,-1):\n    if s1[i]=='1':\n        dp[i]=(dp[i+1]+1)%mod\n    else:\n        dp[i]=dp[i+1]\nans=0\nfor i in range(n):\n    if s[i]=='1':\n        ans=(ans+(dp[i]*power(2,i,mod))%mod)%mod\n        \nprint(ans)\n", "passed": true, "time": 0.16, "memory": 14152.0, "status": "done"}, {"code": "mod=998244353\nn,m=map(int,input().split())\na=[0]*max(0,m-n)+list(int(ch) for ch in input())\nb=[0]*max(0,n-m)+list(int(ch) for ch in input())\npow2 = 1\nfor i in range(len(a)-2,-1,-1):\n\tpow2 = (pow2<<1)%mod\n\ta[i]=(pow2*a[i]+a[i+1])%mod\nans = 0\nfor i in range(len(b)):\n\tif b[i]:\n\t\tans=(ans+a[i])%mod\nprint(ans)", "passed": true, "time": 0.23, "memory": 14356.0, "status": "done"}, {"code": "s = 0\np = 998244353\n\na, b = map(int, input().split())\nA = input()[::-1]\nB = input()[::-1]\ndiff = b-a\ncount = 0\nexp = 1\n\nfor i in range(b):\n\tif B[i]=='1':\n\t\tcount += 1\n\nfor i in range(a):\n\t\n\tif A[i] == '1':\n\t\tval = (exp * count) % p\n\t\ts = (s+val)%p\n\n\texp = exp*2 % p\n\n\tif count > 0:\n\t\tif B[i] == '1':\n\t\t\tcount -= 1\n\nprint(s)", "passed": true, "time": 0.15, "memory": 14212.0, "status": "done"}, {"code": "TOT = 2*10**5\nmod = 998244353\naux = [0] * (TOT+1)\naux[0] = 1\nfor i in range(1,len(aux)):\n    aux[i] = (2*aux[i-1]) % mod\n\nn,m = [int(x) for x in input().split()]\n\na = input()[::-1]\nar = [0] * (TOT+1)\nfor i in range(n):\n    if i:\n        ar[i] = ar[i-1]\n    if a[i] == '1':\n        ar[i] = (ar[i] + aux[i])%mod\n        \nb = input()[::-1]\nans = 0\nfor i in range(m):\n    if b[i] == '1':\n        if i >= n:\n            ans = (ans + ar[n-1]) % mod\n        else:\n            ans = (ans + ar[i])%mod\n            \n            \n# print(aux)\n# print(ar)\nprint(ans)\n\n", "passed": true, "time": 0.24, "memory": 22532.0, "status": "done"}, {"code": "n,m=map(int,input().split())\nta=input()\ntb=input()\ncount=0\nans=0\nr=n-m\nfor i in range(m):\n    if tb[i]=='1':\n        count+=1\n    if i+r>=0:\n        if ta[i+r]=='1':\n            ans=(ans+pow(2,m-i-1,998244353)*count)%998244353\nprint(ans)", "passed": true, "time": 0.14, "memory": 14044.0, "status": "done"}, {"code": "input()\na = list(map(int, input()))\nb = list(map(int, input()))\n\nmod = 998244353\ndef binpow(a, n):\n    if n == 0:\n        return 1\n    ans = binpow(a, n // 2)\n    ans = (ans * ans) % mod\n    if n % 2 == 1:\n        ans = (ans * a) % mod\n    return ans\n\nc = 1\nans = 0\ns = sum(b)\nfor i in range(min(len(a), len(b))):\n    if a[-1 - i] == 1:\n        ans = (ans + c * s) % mod\n    s -= b[-1 - i]\n    c = (c * 2) % mod\nprint(ans)\n", "passed": true, "time": 0.14, "memory": 14080.0, "status": "done"}, {"code": "n,m=map(int,input().split())\na=input()\nb=input()\ncountlist=[]\nman=0\nif len(a)<len(b):\n    a=\"0\"*(len(b)-len(a))+a\nif len(b)<len(a):\n    b=\"0\"*(len(a)-len(b))+b\nfor i in range(len(b)):\n    if b[i]==\"1\":\n        man+=1\n    countlist.append(man)\npower=1\nsum=0\nfor i in range(len(a)):\n    if a[-i-1]==\"1\":\n        sum+=power*countlist[-i-1]\n    power=(2*power)%998244353\nprint(sum%998244353)", "passed": true, "time": 0.14, "memory": 14084.0, "status": "done"}, {"code": "n, m = list(map(int, input().split()))\na = input()\nb = input()\nn, m = len(a), len(b)\nif n > m:\n    addition = ''.join([\"0\"] * (n - m))\n    b = addition + b\nelif m > n:\n    addition = ''.join([\"0\"] * (m - n))\n    a = addition + a\n\n#print(a)\n#print(b)\n\nl = max(m, n)\ncount_bigger = [0] * l\nacc = 0\nfor i in range(l):\n    if b[i] == \"1\":\n        acc += 1\n    if a[i] == \"1\":\n        count_bigger[i] = acc\n\ncount_bigger = count_bigger[::-1]\nanswer = 0\nmul = 1\nfor i in range(l):\n    if count_bigger[i] != 0:\n        answer += count_bigger[i] * mul\n    mul *= 2\n    mul %= 998244353\n\nanswer %= 998244353\nprint(answer)", "passed": true, "time": 0.14, "memory": 14356.0, "status": "done"}, {"code": "import math\ndict1={}\nmod=998244353\nfor i in range(20):\n\tdict1[i]=0\nn,m=list(map(int,input().split()))\ns1=str(input())\ns2=str(input())\ncount1=0\narr=[]\nfor i in range(len(s2)):\n\tif(s2[i]=='1'):\n\t\tcount1+=1\n\tarr.append(count1)\nj=len(s1)-1\nk=min(len(s1),len(s2))\ni=0\nwhile(k>0):\n\tif(s1[j]=='1'):\n\t\tdict1[i]=arr[len(s2)-i-1]\n\ti+=1\n\tj-=1\n\tk-=1\nans=0\nfor i in dict1:\n\tif(dict1[i]>0):\n\t\tans=((ans%mod)+(((dict1[i]%mod)*(pow(2,i,mod)%mod))%mod))%mod\nprint(ans)\n", "passed": true, "time": 0.15, "memory": 14120.0, "status": "done"}, {"code": "n,m=map(int,input().split())\nta=input()\ntb=input()\ncount=0\nans=0\nr=n-m\nfor i in range(m):\n    if tb[i]=='1':\n        count+=1\n    if i+r>=0:\n        if ta[i+r]=='1':\n            ans=(ans+pow(2,m-i-1,998244353)*count)%998244353\nprint(ans)", "passed": true, "time": 0.24, "memory": 14216.0, "status": "done"}, {"code": "n, m = [int(i) for i in input().split()]\na = input()\nb = input()\nif m < n:\n    m = n\n    b = ('0'*(m-len(b)))+b\nelif n < m:\n    n = m\n    a = ('0'*(n-len(a)))+a\n\nones_left = [0]*m\nif b[0] == '1':\n    ones_left[0] = 1\n    \nfor i in range(1, n):\n    ones_left[i] = ones_left[i-1]\n    if b[i] == '1':\n        ones_left[i] += 1\n\nans = 0\nk = 0\nmod = 998244353\nfor i in range(n):\n    k = 1 if a[i] == '1' else 0\n    ans += k*pow(2, n-1-i, mod)*ones_left[i]\n    ans %= mod\n    \nprint(ans)", "passed": true, "time": 0.2, "memory": 14188.0, "status": "done"}, {"code": "def modular_pow(base, exponent, modulus):\n    result = 1\n    base = base % modulus\n    while exponent > 0:\n        if exponent % 2 == 1:\n            result = (result * base) % modulus\n        exponent = exponent >> 1\n        base = (base * base) % modulus\n    return result\n\nlen_a, len_b = list(map(int, input().split()))\na = input()[::-1]\nb = input()[::-1]\n\n\ndp = list(range(len_b))\ndp[len(b) - 1] = 1\nfor i in range(len(b) - 2, -1, -1):\n    dp[i] = dp[i + 1]\n    if b[i] == '1':\n        dp[i] += 1\n\nprimo = 998244353\nsoma = 0\nfor i in range(len_a - 1, -1, -1):\n    if i < len(b) and a[i] == '1':\n        partial = pow(2, i, primo)\n        soma += partial * dp[i]\n        soma = soma % primo\n\nprint(soma)\n\n", "passed": true, "time": 0.14, "memory": 14232.0, "status": "done"}, {"code": "n,m = [int(s) for s in input().split()]\na = input()\nb = input()\nones = 0\nans = 0\nfor i in range(m):\n    if b[i] == '1':\n        ones += 1\n    if n >= m-i:\n        ans <<= 1\n        ans %= 998244353\n        if a[n-(m-i)] == '1':\n            ans += ones \n            ans %= 998244353\n\nprint(ans)", "passed": true, "time": 0.14, "memory": 14272.0, "status": "done"}, {"code": "import sys\n\nn,m=list(map(int,sys.stdin.readline().split()))\na=list(map(int,sys.stdin.readline().strip()))\nb=list(map(int,sys.stdin.readline().strip()))\nmod=998244353\n\n\nANS=0\n\nfor i in range(1,m):\n    b[i]=b[i-1]+b[i]\n\n\nif m>=n:\n    b=b[-n:]\nelse:\n    a=a[-m:]\n    n=m\n\nA=[a[i]*b[i] for i in range(n)]\nA.reverse()\n\nfor i in range(n):\n    ANS=(ANS+pow(2,i,mod)*A[i])%mod\n\nprint(ANS)\n\n\n\n", "passed": true, "time": 0.14, "memory": 14148.0, "status": "done"}, {"code": "import sys\n\ndef minp():\n\treturn sys.stdin.readline().strip()\n\nn,m = map(int,minp().split())\na = minp()\nb = minp()\nc = 0\nif n >= m:\n\ti = n-m\n\tj = 0\nelse:\n\tfor j in range(m-n):\n\t\tif b[j] == '1':\n\t\t\tc += 1\n\ti = 0\n\tj = m-n\nr = 0\nwhile i < n:\n\tr = (r*2)%998244353\n\tif b[j] == '1':\n\t\tc += 1\n\tif a[i] == '1':\n\t\tr += c\n\t#print(c,r)\n\ti += 1\n\tj += 1\nprint(r%998244353)", "passed": true, "time": 0.24, "memory": 14216.0, "status": "done"}, {"code": "n,m = list(map(int, input().split()))\na = input()\nb = input()\nif n > m:\n    b = \"0\"*(n-m) + b\nelif n < m:\n    a = \"0\"*(m-n) + a\ndem = 0\nA = []\nfor i in range(max(n,m)):\n    if b[i] == \"1\":\n        dem += 1\n    A.append(dem)\nans =0\npows = 1\nfor i in range(max(n,m)-1,-1,-1):\n    if a[i] ==\"1\":\n        ans += pows*A[i]\n    pows = (2*pows)%998244353\nprint(ans%998244353)\n", "passed": true, "time": 0.14, "memory": 14268.0, "status": "done"}, {"code": "n,m=map(int,input().split())\nta=input()\ntb=input()\ncount=0\nans=0\nr=n-m\nfor i in range(m):\n    if tb[i]=='1':\n        count+=1\n    if i+r>=0:\n        if ta[i+r]=='1':\n            ans=(ans+pow(2,m-i-1,998244353)*count)%998244353\nprint(ans)", "passed": true, "time": 0.2, "memory": 14076.0, "status": "done"}, {"code": "'''\nn, m = map(int, input().split())\na = input()\nb = input()\nb_ind = []\nmo = 998244353\nans = 0\n\nb_ind.append(int(b[0]))\nfor i in range(1, m):\n\tb_ind.append(b_ind[i-1]+int(b[i]))\n\nfor i in range(1, n+1):\n\tif a[-i] == '1' and i<=m:\n\t\tans += (pow(2, i-1, mo)*b_ind[-i])%mo\n\nprint(ans%mo)\n\n'''\n\nn, m = list(map(int, input().split()))\na = input()\nb = input()\nb_ind = []\nmo = 998244353\nans = 0\n\nb_ind.append(int(b[0]))\nfor i in range(1, m):\n\tb_ind.append(b_ind[i-1]+int(b[i]))\n\nfor i in range(1, n+1):\n\tif a[-i] == '1' and i<=m:\n\t\tans += (pow(2, i-1, mo)*b_ind[-i])%mo\n\nprint(ans%mo)\n\n", "passed": true, "time": 0.14, "memory": 14096.0, "status": "done"}, {"code": "n,m=[int(x)for x in input().split()]\nns=input()\nms=input()\nif n>m:\n    n=m\n    ns=ns[-m:]\n\nmod=998244353\nsq2=[2]\n\nfor i in range(32):\n    x=sq2[-1]*sq2[-1]%mod\n    sq2.append(x)\n\np1=[1]\nfor i in range(n+1):\n    p1.append(p1[-1]*2%mod)\n\n\ndef pow2(n):\n    ans=1\n    for i in range(32):\n        if (n>>i)&1==1:\n            ans*=sq2[i]\n            ans%=mod\n    return ans\n# if m==1:\n    # print(ms)\n# print(sq2)\n\nz=[]\nsum=0\nfor i in range(m):\n    if ms[i]=='0':\n        sum+=1\n    z.append(sum)\n\nans=0\nfor i in range(n):\n    if ns[i]=='0':\n        continue\n    q=n-i-1\n\n    l=i-(n-m)\n\n    ti=0\n    if l>=0: # musk\n        zn=z[l]\n        ti=l-zn+1\n    else:\n        ti=l\n    ans+=ti*p1[q]\n    ans%=mod\n\nprint(ans%mod)\n\n", "passed": true, "time": 0.15, "memory": 14404.0, "status": "done"}, {"code": "def bin_pow(n, s):\n    if s == 0:\n        return 1\n    else:\n        if s % 2 == 0:\n            t = bin_pow(n, s / 2) % 998244353\n            return (t * t) % 998244353\n        else:\n            return ((bin_pow(n, s - 1) % 998244353) * n) % 998244353\ntr, tl = list(map(int, input().split()))\na = input()\nb = input()\n\nans = 0\nansd = 0\nfor i in range(tl):\n    if tr - i - 1 > -1 and a[tr - i - 1] == \"1\":\n        ansd += bin_pow(2, i)\n        ansd %= 998244353\n    if b[tl - i - 1] == \"1\":\n        ans += ansd\n        ans %= 998244353\nprint(ans % 998244353)\n", "passed": true, "time": 0.17, "memory": 14332.0, "status": "done"}, {"code": "def get_input_list():\n\treturn list(map(int, input().split()))\nn, m = get_input_list()\na = input()\nb = input()\nl = 0\nq = 1\nv = 0\ni = n-1\nj = m-1\nr = 0\nmod = 998244353\nwhile j >= 0:\n\tif i>=0 and a[i] == '1':\n\t\tv = (v+q)%mod\n\tif b[j] == '1':\n\t\tr = (r+v)%mod\n\ti -= 1\n\tq = (q << 1)%mod\n\tj -= 1\nprint(r)\n", "passed": true, "time": 0.15, "memory": 14392.0, "status": "done"}, {"code": "n,m = list(map(int,input().split()))\ns1 = input();\ns2 = input();\nif m < n:\n\ts2 = \"0\"*(n-m) + s2;\n\tm = n;\nelse:\n\ts1 = \"0\"*(m-n) + s1;\n\tn = m;\n\n#print(s1,s2)\n#count1 = s1.count(\"1\");\n#count2 = s2.count(\"1\");\nans = [0]*n;\nfor i in range(n):\n\tif s2[i] == \"1\":\n\t\tans[i] =1;\nfor i in range(1,n):\n\tans[i] += ans[i-1];\n\n\nmod = 998244353;\nfinal = 0;\nn -= 1;\n#print(s1)\n#print(*ans)\nfor i in range(m):\n\tif s1[i] == \"1\":\n\t\t#print(i)\n\t\tfinal += ( pow(2,n-i,mod) * ans[i] )%mod\n\t\tfinal %= mod;\nprint(final)\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n", "passed": true, "time": 0.14, "memory": 14172.0, "status": "done"}, {"code": "n,m = list(map(int,input().split()))\na = input()\nb = input()\nif n < m:\n    a = \"0\"*(m-n)+a\nelif m < n:\n    b = \"0\"*(n-m)+b\nn = max(n,m)\ntot = 0\nsm = 0\nfor i in range(n):\n    if b[i] == '1':\n        tot += 1\n    if a[i] == '1':\n        sm = (sm+tot*int(pow(2,(n-i-1),998244353)))%998244353\nprint(sm)\n", "passed": true, "time": 0.14, "memory": 14352.0, "status": "done"}, {"code": "#!/usr/bin/env python3\nimport sys\n\ndef rint():\n    return list(map(int, sys.stdin.readline().split()))\n#lines = stdin.readlines()\n\n\nn, m = rint()\n\na = list(map(int, input()))\nb = list(map(int, input()))\na = a[::-1]\nb = b[::-1]\ndiv = 998244353\n\nmod_bit = [0]*(2*10**5+1)\nmod_asum = [0]*(2*10**5+1)\n\nmod_bit[0] = 1%div\nfor i in range(1, n):\n    mod_bit[i] = mod_bit[i-1]*2%div\nmod_asum[0] = a[0]\nfor i in range(1, n):\n    mod_asum[i] = (mod_asum[i-1] + a[i]*mod_bit[i])%div\n\nans = 0\nfor i in range(m):\n    ans += b[i]*mod_asum[min(i, n-1)]\n    ans %= div\n\nprint(ans)\n\n\n\n", "passed": true, "time": 0.14, "memory": 16580.0, "status": "done"}]