Under construction

Still being built. Things may change

Shuffled Stones

Time limit3sMemory limit1024 MB

Summary
Given N and a pair X, Y, count the sequences of 2N stones with longest decreasing subsequence 2 in which X and Y are a pair, modulo 998244353.
Level

Hard8 of 10

Topics
Combinatorics, Math
Solved
No attempts yet

Problem

While walking down the street, Chanwoo found 2N2N stones on the ground, with the integers from 11 to 2N2N written on them in order. Bothered by the neat order, he decided to shuffle the stones. He grouped the 2N2N stones into NN pairs of two, then swapped the positions of the two stones in each pair. This produced a new sequence {a1,a2,…,a2N}\{a_1,a_2,\ldots,a_{2N}\}.

Pleased with the mess he had made, Chanwoo noticed an interesting property. The longest decreasing subsequence of the shuffled sequence has length only 22. He wanted to take a photo of it, but his phone battery was dead. Instead, he took one pair of stones (X,Y)(X,Y) that he had paired.

Back home, Chanwoo wanted to reconstruct the sequence, but he remembers only three things: XX and YY were paired, the total number of stones is 2N2N, and the longest decreasing subsequence of the sequence has length 22. Given 2N2N and the pair XX, YY, count how many sequences satisfy these conditions.

Input

The first line contains NN, XX, and YY separated by spaces. (1≤N≤500 0001 \le N \le 500\,000; 1≤X,Y≤2N1 \le X, Y \le 2N; X≠YX \ne Y)

Output

Print the number of valid sequences modulo 998 244 353998\,244\,353.

Hint

You can form a subsequence by removing some numbers from a sequence. Among the subsequences formed this way, the longest one sorted in decreasing order is called the longest decreasing subsequence.

Examples1

  1. Example 1

    Input
    4 5 6
    
    Expected output
    2