Problem:


Score : 2200 points

Problem Statement

We have two indistinguishable pieces placed on a number line.
Both pieces are initially at coordinate 0. (They can occupy the same position.)

We can do the following two kinds of operations:

Choose a piece and move it to the right (the positive direction) by 1.

Move the piece with the smaller coordinate to the position of the piece with the greater coordinate.
If two pieces already occupy the same position, nothing happens, but it still counts as doing one operation.

We want to do a total of N operations of these kinds in some order so that one of the pieces will be at coordinate A and the other at coordinate B.
Find the number of ways to move the pieces to achieve it.
The answer can be enormous, so compute the count modulo 998244353.

Two ways to move the pieces are considered different if and only if there exists an integer i (1 \leq i \leq N) such that the set of the coordinates occupied by the pieces after the i-th operation is different in those two ways.

Constraints

1 \leq N \leq 10^7

0 \leq A \leq B \leq N

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N A B

Output

Print the number of ways to move the pieces to achieve our objective, modulo 998244353.

Sample Input 1

5 1 3

Sample Output 1

4

Shown below are the four ways to move the pieces, where (x,y) represents the state where the two pieces are at coordinates x and y.

(0,0)→(0,0)→(0,1)→(0,2)→(0,3)→(1,3)

(0,0)→(0,0)→(0,1)→(0,2)→(1,2)→(1,3)

(0,0)→(0,0)→(0,1)→(1,1)→(1,2)→(1,3)

(0,0)→(0,1)→(1,1)→(1,1)→(1,2)→(1,3)

Sample Input 2

10 0 0

Sample Output 2

1

Sample Input 3

10 4 6

Sample Output 3

197

Sample Input 4

1000000 100000 200000

Sample Output 4

758840509



Sample input:
5 1 3


Sample output:
4

Submission status: Wrong Answer

Solution code:
# F

Submission status: Time Limit Exceeded

Solution code:
def Q():
    N, A, B = map(int, input().split())
    MOD = 998244353

    if B == 0:
        print(1)
        exit()

    f = 1
    F = [1] * (N + 1)
    for i in range(1, N + 1):
        F[i] = f = f * i % MOD

    FI = [1] * (N + 1)
    FI[N] = fi = pow(f, MOD - 2, MOD)
    for i in range(N, 1, -1):
        FI[i - 1] = fi = fi * i % MOD

    z = 0
    for k in range(min(A + 1, N - B) if N - B - A else A + 1):
        x = (B - k) * F[B + k - 1] * FI[B] * FI[k] % MOD
        y = F[N + A - B - 2 * k - 1] * FI[N - B - k - 1] * FI[A - k] % MOD
        z = (z + x * y) % MOD

    print(z)

Q()

Submission status: Time Limit Exceeded

Solution code:
N, A, B = map(int, input().split())
MOD = 998244353

if B == 0:
    print(1)
    exit()

f = 1
F = [1] * (N + 1)
for i in range(1, N + 1):
    F[i] = f = f * i % MOD

FI = [1] * (N + 1)
FI[N] = fi = pow(f, MOD - 2, MOD)
for i in range(N, 1, -1):
    FI[i - 1] = fi = fi * i % MOD

z = 0
for k in range(min(A + 1, N - B) if N - B - A else A + 1):
    x = (B - k) * F[B + k - 1] * FI[B] * FI[k] % MOD
    y = F[N + A - B - 2 * k - 1] * FI[N - B - k - 1] * FI[A - k] % MOD
    z = (z + x * y) % MOD

print(z)

Submission status: Accepted

Solution code:
N,A,B=map(int,input().split());M=998244353;P=N+1;f=1;F=[1]*P;I=[1]*P;z=0;R=range
for n in R(1,P):F[n]=f=f*n%M
I[N]=i=pow(f,M-2,M)
for n in R(N,1,-1):I[n-1]=i=i*n%M
for k in R(min(A+1,N-B)if N-B-A else A+1):Q=N-B-k-1;z+=(B-k)*F[B+k-1]*I[B]*I[k]*F[Q+A-k]*I[Q]*I[A-k]
print(z%M if B else 1)

Submission status: Accepted

Solution code:
N,A,B=map(int,input().split());M=998244353;P=N+1;f=1;F=[1]*P;I=[1]*P;z=0;R=range
for n in R(1,P):F[n]=f=f*n%M
I[N]=i=pow(f,M-2,M)
for n in R(N,1,-1):I[n-1]=i=i*n%M
for k in R(min(A+1,N-B)if N-B-A else A+1):Q=N-B-k-1;z=(z+(B-k)*F[B+k-1]*I[B]*I[k]*F[Q+A-k]*I[Q]*I[A-k])%M
print(z if B else 1)

Submission status: Accepted

Solution code:
N,A,B=map(int,input().split());M=998244353;P=N+1;f=1;F=[1]*P;I=[1]*P;z=0;R=range
if B==0:print(1);exit()
for n in R(1,P):F[n]=f=f*n%M
I[N]=i=pow(f,M-2,M)
for n in R(N,1,-1):I[n-1]=i=i*n%M
for k in R(min(A+1,N-B)if N-B-A else A+1):Q=N-B-k-1;z=(z+(B-k)*F[B+k-1]*I[B]*I[k]*F[Q+A-k]*I[Q]*I[A-k])%M
print(z)

Submission status: Runtime Error

Solution code:
def inc(a, b, inc_a, a_max, b_max, n, n_max):
    cnt = 0
    n += 1

    if inc_a:
        a += 1
    else:
        b += 1

    if a == a_max and b == b_max and n == n_max:
        return 1

    if a > b or a > a_max or b > b_max or n > n_max:
        return 0

    cnt += inc(a, b, True, a_max, b_max, n, n_max)
    cnt += inc(a, b, False, a_max, b_max, n, n_max)
    cnt += same(a, b, a_max, b_max, n, n_max)
    return cnt


def same(a, b, a_max, b_max, n, n_max):
    if b - a == 1:
        return 0

    cnt = 0
    n += 1

    a = b

    if a == a_max and b == b_max and n == n_max:
        return 1

    if a > b or a > a_max or b > b_max or n > n_max:
        return 0

    cnt += inc(a, b, True, a_max, b_max, n, n_max)
    cnt += inc(a, b, False, a_max, b_max, n, n_max)
    cnt += same(a, b, a_max, b_max, n, n_max)
    return cnt


if __name__ == '__main__':
    n_max, a_max, b_max = list(map(int, input().split()))
    n = 0
    a = 0
    b = 0
    cnt = 0

    cnt += inc(a, b, False, a_max, b_max, n, n_max)
    cnt += same(a, b, a_max, b_max, n, n_max)
    print(cnt)