You are given three positive integers N, x, and y.

Count the number of arrays P of length N such that:
P_{1} = P_{N} = 1
There are exactly x indices i such that P_{i}=1
There are exactly y indices i such that P_{i}=2
There are exactly N-x-y indices i such that P_{i}=3
P_{i} \neq P_{i+1} for each 1 ≤ i < N

Since the answer can be large, output it modulo 998244353.

------ Input Format ------ 

- The first and only line of input will contain three space-separated integers N, x and y.

------ Output Format ------ 

Output a single integer: the number of arrays obtained, modulo 998244353.

------ Constraints ------ 

$3 ≤ N ≤ 2 \cdot 10^{6}$
$2 ≤ x ≤ N-1$
$1 ≤ y ≤ N-2$
$x + y ≤ N$

----- Sample Input 1 ------ 
5 3 1

----- Sample Output 1 ------ 
2
----- explanation 1 ------ 

----- Sample Input 2 ------ 
10 4 3

----- Sample Output 2 ------ 
44
----- explanation 2 ------ 
Test case $1$: Only two valid arrays are possible: 
- $[1,2,1,3,1]$
- $[1,3,1,2,1]$

Test case $2$: A couple of valid arrays are $[1, 2, 3, 1, 2 ,3, 1, 2, 3, 1]$ and $[1, 3, 2, 1, 3, 1, 2, 3, 2, 1]$. It can be verified that there are $44$ in total.

Source: codechef | Difficulty: VERY_HARD
Tags: Combinatorics

Mathematics


Solutions:
mod = 998244353
fact = [1]
for i in range(1, 2 * 10 ** 6 + 1):
	fact.append(fact[-1] * i % mod)

def binom(a, b):
	if a < b or b < 0:
		return 0
	num = fact[a]
	den = fact[b] * fact[a - b] % mod
	return num * pow(den, -1, mod) % mod
(n, one, two) = map(int, input().split())
three = n - one - two
ans = 0
for t in range(n + 1):
	r = three - two + t
	s = one - 1 - r - t
	if r < 0 or s < 0 or t < 0:
		continue
	even = n - one + r + t
	ways = binom(even // 2 - 1, one - 2)
	ways = ways * binom(one - 1, r + t) % mod
	ways = ways * binom(r + t, r) % mod
	ways = ways * pow(2, s, mod) % mod
	ans = (ans + ways) % mod
print(ans)