Ringo got interested in modern art. He decided to draw a big picture on the board with N+2 rows and M+2 columns of squares constructed in the venue of CODE FESTIVAL 2017, using some people.

The square at the (i+1)-th row and (j+1)-th column in the board is represented by the pair of integers (i,j). That is, the top-left square is (0,0), and the bottom-right square is (N+1,M+1). Initially, the squares (x,y) satisfying 1 \leq x \leq N and 1 \leq y \leq M are painted white, and the other (outermost) squares are painted black.

Ringo arranged people at some of the outermost squares, facing inward. More specifically, the arrangement of people is represented by four strings A, B, C and D, as follows:

* For each row except the top and bottom, if the i-th character (1 \leq i \leq N) in A is `1`, place a person facing right at the square (i,0); otherwise, do nothing.
* For each row except the top and bottom, if the i-th character (1 \leq i \leq N) in B is `1`, place a person facing left at the square (i,M+1); otherwise, do nothing.
* For each column except the leftmost and rightmost, if the i-th character (1 \leq i \leq M) in C is `1`, place a person facing down at the square (0,i); otherwise, do nothing.
* For each column except the leftmost and rightmost, if the i-th character (1 \leq i \leq M) in D is `1`, place a person facing up at the square (N+1,i); otherwise, do nothing.



Each person has a sufficient amount of non-white paint. No two people have paint of the same color.

<image>

An example of an arrangement of people (For convenience, black squares are displayed in gray)

Ringo repeats the following sequence of operations until all people are dismissed from the venue.

* Select a person who is still in the venue.
* The selected person repeats the following action while the square in front of him/her is white: move one square forward, and paint the square he/she enters with his/her paint. When the square in front of him/her is not white, he/she stops doing the action.
* The person is now dismissed from the venue.



<image>

An example of a way the board is painted

How many different states of the board can Ringo obtain at the end of the process? Find the count modulo 998244353.

Two states of the board are considered different when there is a square painted in different colors.

Constraints

* 1 \leq N,M \leq 10^5
* |A|=|B|=N
* |C|=|D|=M
* A, B, C and D consist of `0` and `1`.

Input

Input is given from Standard Input in the following format:


N M
A
B
C
D


Output

Print the number of the different states of the board Ringo can obtain at the end of the process, modulo 998244353.

Examples

Input

2 2
10
01
10
01


Output

6


Input

2 2
11
11
11
11


Output

32


Input

3 4
111
111
1111
1111


Output

1276


Input

17 21
11001010101011101
11001010011010111
111010101110101111100
011010110110101000111


Output

548356548


Input

3 4
000
101
1111
0010


Output

21


Input

9 13
111100001
010101011
0000000000000
1010111111101


Output

177856


Input

23 30
01010010101010010001110
11010100100100101010101
000101001001010010101010101101
101001000100101001010010101000


Output

734524988

//#define USEPB_DS
#define USETR1
#define CPPELEVEN
#define GPP

/*
 * temp.cpp
 *
 *  Created on: 2012-7-18
 *      Author: BSBandme
 */
//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <iostream>
#include <fstream>
#include <string.h>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <cassert>
#include <list>
#include <iomanip>
#include <math.h>
#include <deque>
#include <utility>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <climits>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <functional>
#include <sstream>
#include <tuple>

using namespace std;

#ifndef CPPELEVEN
#ifdef USETR1
#include <tr1/unordered_map>
#include <tr1/unordered_set>
using namespace tr1;
#endif
#else
#include <unordered_map>
#include <unordered_set>
#endif

#ifdef USEPB_DS
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
// binomial_heap_tag, rc_binomial_heap_tag, thin_heap_tag, binary_heap_tag
typedef __gnu_pbds::priority_queue<int, greater<int>, pairing_heap_tag> pq_type;
// splay_tree_tag, ov_tree_tag
typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> tree_type;
#endif

#define mpr make_pair
typedef unsigned int ui;
typedef unsigned long long ull;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <double, double> pdd;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <double> vd;
typedef vector <string> vs;
typedef map <string, int> mpsi;
typedef map <double, int> mpdi;
typedef map <int, int> mpii;

const double pi = acos(0.0) * 2.0;
const long double eps = 1e-10;
const int step[8][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};

template <class T> inline T abs1(T a) {return a < 0 ? -a : a;}

#ifndef CPPELEVEN
template <class T> inline T max1(T a, T b) { return b < a ? a : b; }
template <class T> inline T max1(T a, T b, T c) { return max1(max1(a, b), c); }
template <class T> inline T max1(T a, T b, T c, T d) { return max1(max1(a, b, c), d); }
template <class T> inline T max1(T a, T b, T c, T d, T e) { return max1(max1(a, b, c, d), e); }
template <class T> inline T min1(T a, T b) { return a < b ? a : b; }
template <class T> inline T min1(T a, T b, T c) { return min1(min1(a, b), c); }
template <class T> inline T min1(T a, T b, T c, T d) { return min1(min1(a, b, c), d); }
template <class T> inline T min1(T a, T b, T c, T d, T e) { return min1(min1(a, b, c, d), e); }
#else
template <typename t, typename t1>
t min1(t a, t1 b) { return a < b ? a : b; }
template <typename t, typename... arg>
t min1(t a, arg... arr) { return min1(a, min1(arr...)); }
template <typename t, typename t1>
t max1(t a, t1 b) { return a > b ? a : b; }
template <typename t, typename... arg>
t max1(t a, arg... arr) { return max1(a, max1(arr...)); }
#endif

inline int jud(double a, double b){
	if(abs(a) < eps && abs(b) < eps) return 0;
	else if(abs1(a - b) / max(abs1(a), abs1(b)) < eps) return 0;
	if(a < b) return -1;
	return 1;
}
template <typename t> inline int jud(t a, t b){
	if(a < b) return -1;
	if(a == b) return 0;
	return 1;
}

// f_lb == 1代表返回相同的一串的左边界，f_small == 1代表返回如果没有寻找的值返回小的数
template <typename it, typename t1>
inline int find(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1){
	if(na == 0) return 0;
	int be = 0, en = na - 1;
	if(*a <= *(a + na - 1)){
		if(f_lb == 0) while(be < en){
			int mid = (be + en + 1) / 2;
			if(jud(*(a + mid), val) != 1) be = mid;
			else en = mid - 1;
		}else while(be < en){
			int mid = (be + en) / 2;
			if(jud(*(a + mid), val) != -1) en = mid;
			else be = mid + 1;
		}
		if(f_small && jud(*(a + be), val) == 1) be--;
		if(!f_small && jud(*(a + be), val) == -1) be++;
	} else {
		if(f_lb) while(be < en){
			int mid = (be + en + 1) / 2;
			if(jud(*(a + mid), val) != -1) be = mid;
			else en = mid - 1;
		}else while(be < en){
			int mid = (be + en) / 2;
			if(jud(*(a + mid), val) != 1) en = mid;
			else be = mid + 1;
		}
		if(!f_small && jud(*(a + be), val) == -1) be--;
		if(f_small && jud(*(a + be), val) == 1) be++;
	}
	return be;
}

template <class T> inline T lowb(T num) {return num & (-num); }
#ifdef GPP
inline int bitnum(ui nValue) { return __builtin_popcount(nValue); }
inline int bitnum(int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(ull nValue) { return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32); }
inline int bitnum(ll nValue) { return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32); }
inline int bitmaxl(ui a) { if(a == 0) return 0; return 32 - __builtin_clz(a); }
inline int bitmaxl(int a) { if(a == 0) return 0; return 32 - __builtin_clz(a); }
inline int bitmaxl(ull a) { int temp = a >> 32; if(temp) return 32 - __builtin_clz(temp) + 32; return bitmaxl(int(a)); }
inline int bitmaxl(ll a) { int temp = a >> 32; if(temp) return 32 - __builtin_clz(temp) + 32; return bitmaxl(int(a)); }
#else
#endif

long long pow(long long n, long long m, long long mod = 0){
	if(m < 0) return 0;
	long long ans = 1;
	long long k = n;
	while(m){
		if(m & 1) {
			ans *= k;
			if(mod) ans %= mod;
		}
		k *= k;
		if(mod) k %= mod;
		m >>= 1;
	}
	return ans;
}

#define  MOD 1000000007
template <class t1, class t2>
inline void add(t1 &a, t2 b, int mod = -1) {
	if(mod == -1) mod = MOD;
	a += b;
	while(a >= mod) a -= mod;
	while(a < 0) a += mod;
}
template <class t>
void output1(t arr) {
	for(int i = 0; i < (int)arr.size(); i++)
		cerr << arr[i] << ' ';
	cerr << endl;
}
template <class t>
void output2(t arr) {
	for(int i = 0; i < (int)arr.size(); i++)
		output1(arr[i]);
}

//....................密..........封..........线..........下..........禁..........止..........hack...............................................

const int mod = 998244353;
const int maxn = 500100;
ll fac[maxn];
ll invfac[maxn];
int n, m;
string stra, strb, strc, strd;
ll ans = 0;

ll c(int a, int b) {
	if (a == b) return 1;
	if (b < 0) return 0;
	if (b > a) return 0;
	return fac[a] * invfac[b] % mod * invfac[a - b] % mod;
}

int cnt1(const string &str) {
	int a = 0;
	for (int i = 0; i < (int)str.length(); i++) {
		a += str[i] == '1';
	}
	return a;
}

void solve() {
	ll rsum = 1;
	ll la = cnt1(stra), lb = cnt1(strb), ora = la, orb = lb, lc = cnt1(strc), ld = cnt1(strd);
	for (int i = n - 1; i >= 0; i--) {
		if (stra[i] != '1' && strb[i] != '1') {
			continue;
		}
		ll mul = 1;
 		if (stra[i] == '1' && strb[i] == '1') {
 			mul++;
 		}
 		la -= stra[i] == '1', lb -= strb[i] == '1';
 		rsum = rsum * mul % mod;
 		ans += rsum *  c(la + lb + lc - 1, lc - 1);
 		ans %= mod;
 		rsum += c(ora - la + orb - lb + ld - 1, ld - 1);
 		rsum %= mod;
	}
}

int main() {


//............................不要再忘了检查maxn大小了！！！！BSBandme你个SB！！！！...................................................

	ios_base::sync_with_stdio(0);
	#ifdef DEBUG //......................................................................................................
	freopen("input.txt", "r", stdin);
	int __size__ = 256 << 20; // 256MB
	char *__p__ = (char*)malloc(__size__) + __size__;
	__asm__("movl %0, %%esp\n" :: "r"(__p__));
	#endif //...........................................................................................................

	fac[0] = 1;
	for (int i = 1; i < maxn; i++) {
		fac[i] = fac[i - 1] * i % mod;
	}
	invfac[maxn - 1] = pow(fac[maxn - 1], mod - 2, mod);
	for (int i = maxn - 2; i >= 0; i--) {
		invfac[i] = invfac[i + 1] * (i + 1) % mod;
	}
	cin >> n >> m >> stra >> strb >> strc >> strd;
	solve();
	swap(n, m);
	swap(stra, strc);
	swap(strb, strd);
	solve();
	if (cnt1(stra) + cnt1(strb) + cnt1(strc) + cnt1(strd) == 0) {
		ans++;
	}
	cout << ans << endl;

    return 0;
}

