You are given $n$ dominoes. Each domino has a left and a right cell. Each cell can be colored either black or white. Some cells are already colored, while some aren't yet.

The coloring is said to be valid if and only if it is possible to rearrange the dominoes in some order such that for each $1 \le i \le n$ the color of the right cell of the $i$-th domino is different from the color of the left cell of the $((i mod n)+1)$-st domino.

Note that you can't rotate the dominoes, so the left cell always remains the left cell, and the right cell always remains the right cell.

Count the number of valid ways to color the yet uncolored cells of dominoes. Two ways are considered different if there is a cell that is colored white in one way and black in the other. In particular, colorings BW WB and WB BW different (and both invalid).

As this number can be very big, output it modulo $998\,244\,353$.


-----Input-----

The first line of the input contains a single integer $n$ ($1 \le n \le 10^5$) — the number of dominoes.

The next $n$ lines describe dominoes. Each line contains two characters which represent the left and the right cell. Character B means that the corresponding cell is black, character W means that the corresponding cell is white, and ? means that the cell is yet to be colored.


-----Output-----

Print a single integer — the answer to the problem.


-----Examples-----

Input
1
?W
Output
1
Input
2
??
W?
Output
2
Input
4
BB
??
W?
??
Output
10


-----Note-----

In the first test case, there is only one domino, and we need the color of its right cell to be different from the color of its left cell. There is only one way to achieve this.

In the second test case, there are only $2$ such colorings:

BB WW and WB WB.

Difficulty: VERY_HARD
Tags: Graph algorithms

Combinatorics

Number theory

Mathematics

Polynomials and generating functions

Starter code:

Solutions:
MOD = 998244353
MAX = 200005
fact = [1]
for zz in range(1, MAX + 1):
	fact.append(fact[-1] * zz % MOD)

def nCr(n, r):
	num = fact[n]
	den = fact[r] * fact[n - r] % MOD
	return num * pow(den, MOD - 2, MOD) % MOD
from collections import Counter

def main():
	MOD = 998244353
	cnts = Counter()
	n = int(input())
	arr = []
	for _ in range(n):
		s = input()
		arr.append(s)
		cnts[s] += 1
	wCnt = bCnt = 0
	for (k, v) in cnts.items():
		for i in range(2):
			if k[i] == 'W':
				wCnt += v
			if k[i] == 'B':
				bCnt += v
	if wCnt > n or bCnt > n:
		print(0)
		return
	gap = n - wCnt + n - bCnt
	total = nCr(gap, n - wCnt)
	if cnts['WW'] == cnts['BB'] == 0:
		subtract = 0
		minWBCnts = minBWCnts = 0
		for wb in ['W?', '?B', 'WB']:
			minWBCnts += cnts[wb]
		for bw in ['B?', '?W', 'BW']:
			minBWCnts += cnts[bw]
		gap = n - minWBCnts - minBWCnts
		qq = cnts['??']
		for wbCnts in range(1, n):
			bwCnts = n - wbCnts
			if wbCnts < minWBCnts or bwCnts < minBWCnts:
				continue
			assert qq >= wbCnts - minWBCnts
			subtract += nCr(qq, wbCnts - minWBCnts)
			subtract %= MOD
		total = (total - subtract + MOD) % MOD
	print(total)
	return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(i, j):
	print('? {} {}'.format(i, j))
	sys.stdout.flush()
	return int(input())

def answerInteractive(i, j, k):
	print('! {} {} {}'.format(i, j, k))
	sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
	main()


mod = 998244353

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m

def choose(n, k, p):
	if k == 0:
		return 1
	x = n
	for y in range(n - 1, n - k, -1):
		x = x * y % p
	d = 1
	for i in range(2, k + 1):
		d = d * i % p
	return x * modinv(d, p) % p

def solve():
	n = int(input())
	wb_poss = n > 1
	bw_poss = n > 1
	w = 0
	b = 0
	q = 0
	free = 0
	any_bad_poss = n > 1
	for _ in range(n):
		s = input().strip()
		if s[0] == 'B':
			b += 1
			wb_poss = False
		elif s[0] == 'W':
			w += 1
			bw_poss = False
		elif s[0] == '?':
			q += 1
		if s[1] == 'B':
			b += 1
			bw_poss = False
		elif s[1] == 'W':
			w += 1
			wb_poss = False
		elif s[1] == '?':
			q += 1
		if s == '??':
			free += 1
		elif s[0] == s[1]:
			any_bad_poss = False
	w_needed = n - w
	if w_needed > q or w_needed < 0:
		print(0)
		return
	if any_bad_poss:
		num_bad_poss = pow(2, free, mod)
		num_bad_poss -= int(bw_poss) + int(wb_poss)
	else:
		num_bad_poss = 0
	print((choose(q, w_needed, mod) - num_bad_poss + mod) % mod)
solve()


import sys, os, io
input = sys.stdin.readline
n = int(input())
a = []
w = 0
b = 0
for i in range(n):
	c = input().strip()
	w += c.count('W')
	b += c.count('B')
	a.append(c)
if w > n or b > n:
	print(0)
	exit()

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p
mod = 998244353
total = ncr(2 * n - w - b, n - w, mod)
bad = 1
if 'BB' in a or 'WW' in a:
	bad = 0
bw = 1
wb = 1
for i in a:
	if i[0] == '?' and i[1] == '?':
		bad *= 2
		bad %= mod
	if i[0] == 'B' or i[1] == 'W':
		wb = 0
	if i[0] == 'W' or i[1] == 'B':
		bw = 0
print((total - bad + bw + wb) % mod)


from sys import stdin, stdout
N = 998244353

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m=998244353):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
n = int(stdin.readline())
if n == 1:
	domino = stdin.readline().strip()
	if domino[0] == '?' and domino[1] == '?':
		stdout.write('2\n')
	elif domino[0] == '?' or domino[1] == '?':
		stdout.write('1\n')
	elif domino == 'BB' or domino == 'WW':
		stdout.write('0\n')
	else:
		stdout.write('1\n')
else:
	count = {'BB': 0, 'BW': 0, 'B?': 0, 'WB': 0, 'WW': 0, 'W?': 0, '?B': 0, '?W': 0, '??': 0}
	for _ in range(n):
		count[stdin.readline().strip()] += 1
	count_b = 2 * count['BB'] + count['BW'] + count['WB'] + count['B?'] + count['?B']
	count_w = 2 * count['WW'] + count['BW'] + count['WB'] + count['W?'] + count['?W']
	if count_b > n or count_w > n:
		stdout.write('0\n')
	else:
		answer = 1
		top = 2 * n - count_b - count_w
		bottom = 1
		while bottom <= n - count_w:
			answer = answer * top * modinv(bottom) % N
			top -= 1
			bottom += 1
		if count['BB'] == 0 and count['WW'] == 0:
			deduction = 1
			for i in range(count['??']):
				deduction = deduction * 2 % N
			if count['BB'] + count['BW'] + count['B?'] + count['WW'] + count['?W'] == 0:
				deduction -= 1
			if count['WW'] + count['WB'] + count['W?'] + count['BB'] + count['?B'] == 0:
				deduction -= 1
			answer = (answer - deduction) % N
		stdout.write(str(answer) + '\n')


import os
import sys
from io import BytesIO, IOBase

def main():
	MOD = 998244353
	n = int(input())
	lcnt = [0, 0]
	rcnt = [0, 0]
	errorterm = 1
	allBW = 1
	allWB = 1
	for _ in range(n):
		a = input()
		if a[0] == 'W':
			lcnt[0] += 1
			allBW = 0
		elif a[0] == 'B':
			lcnt[1] += 1
			allWB = 0
		if a[1] == 'W':
			rcnt[0] += 1
			allWB = 0
		elif a[1] == 'B':
			rcnt[1] += 1
			allBW = 0
		if a[0] == 'W' and a[1] == 'W' or (a[0] == 'B' and a[1] == 'B'):
			errorterm = 0
		elif a[0] == '?' and a[1] == '?':
			errorterm *= 2
			errorterm %= MOD
	combiL = [1]
	combiR = [1]
	nL = n - sum(lcnt)
	nR = n - sum(rcnt)
	for i in range(nL):
		combiL.append(combiL[-1] * (nL - i) * pow(i + 1, MOD - 2, MOD))
		combiL[-1] %= MOD
	for i in range(nR):
		combiR.append(combiR[-1] * (nR - i) * pow(i + 1, MOD - 2, MOD))
		combiR[-1] %= MOD
	ans = 0
	for i in range(n + 1):
		target1 = i - lcnt[0]
		target2 = i - rcnt[1]
		if target1 < 0 or target1 > nL or target2 < 0 or (target2 > nR):
			continue
		ans += combiL[target1] * combiR[target2]
		ans %= MOD
	print((ans - errorterm + allBW + allWB) % MOD)
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')
main()


import sys
input = sys.stdin.readline
mod = 998244353
n = int(input())
b = 0
w = 0
blank = 0

def fact(n):
	res = 1
	for i in range(1, n + 1):
		res *= i
		res %= mod
	return res
ct = 1
L = []
leftb = True
rightb = True
for i in ' ' * n:
	s = input().strip()
	L = []
	for j in s:
		if j == 'B':
			b += 1
		if j == 'W':
			w += 1
		if j == '?':
			blank += 1
	if s == 'BB' or s == 'WW':
		ct = 0
	if s == '??':
		ct *= 2
	ct %= mod
	if s[0] == 'W':
		leftb = False
	if s[0] == 'B':
		rightb = False
	if s[1] == 'W':
		rightb = False
	if s[1] == 'B':
		leftb = False
res = 0
if abs(b - w) <= blank:
	r = (blank - abs(b - w)) // 2
	comb = fact(blank) * pow(fact(blank - r), mod - 2, mod) * pow(fact(r), mod - 2, mod)
	comb %= mod
	if leftb and rightb:
		res = comb - ct + 2
	elif leftb or rightb:
		res = comb - ct + 1
	else:
		res = comb - ct
print(res)