https://codeforces.com/contest/1066/problem/E

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given two huge binary integer numbers a and b of lengths n and mmrespectively. 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 aa and bb. 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=10102 (1010)and b=10002 (810), then the value a & ba & b will be equal to 8, not to 1000.

Input

The first line of the input contains two integers n and mm (1≤n,m≤2⋅105) — 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:

  1. add to the answer 10102 & 11012=10002=810 and set b:=110;
  2. add to the answer 10102 & 1102=102=210 and set b:=11;
  3. add to the answer 10102 & 112=102=210 and set b:=1;
  4. add to the answer 10102 & 12=02=010 and set b:=0.

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

The algorithm for the second example:

  1. add to the answer 10012 & 101012=12=110 and set b:=1010;
  2. add to the answer 10012 & 10102=10002=810 and b:=101;
  3. add to the answer 10012 & 1012=12=110 and set b:=10;
  4. add to the answer 10012 & 102=02=010 and set b:=1;
  5. add to the answer 10012 & 12=12=110 and set b:=0.

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

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG

using namespace std;
typedef long long ll;
const int N=2e5+10;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
const ll MOD=998244353;
int t,n,m;
int add(int a, int b) {
	a += b;
	if (a < 0) a += MOD;
	if (a >= MOD) a -= MOD;
	return a;
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    scanf("%d%d",&n,&m);
	string s, t;
	cin >> s >> t;

	int pw = 1;
	int res = 0;
	int ans = 0;

	for (int i = 0; i < m; ++i) {
		if (i < n && s[n - i - 1] == '1') {
			res = add(res, pw);
		}
		if (t[m - i - 1] == '1') {
			ans = add(ans, res);
		}
		pw = add(pw, pw);
	}

	cout << ans << endl;
    //cout << "Hello world!" << endl;
    return 0;
}