만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

뒤섞인 돌

시간 제한3초메모리 제한1024 MB

요약
N과 짝 X, Y가 주어졌을 때, 가장 긴 감소 부분수열의 길이가 2인 수열 중 X와 Y가 짝인 경우의 수를 998244353으로 나눈 나머지로 구합니다.
난이도

어려움10점 중 8점

유형
조합론, 수학
정답자
아직 제출이 없습니다

문제

길을 걷던 찬우는 바닥에서 11부터 2N2N까지의 정수가 차례로 적힌 돌 2N2N개를 발견했다. 질서정연하게 정렬된 돌들이 불편하게 느껴진 찬우는 돌의 순서를 마음대로 바꾸기로 했다. 그는 2N2N개의 돌을 두 개씩 짝지어 NN개의 쌍을 만든 뒤, 각 쌍에서 두 돌의 위치를 서로 바꿨다. 이렇게 해서 새로운 수열 {a1,a2,…,a2N}\{a_1,a_2,\ldots,a_{2N}\}이 만들어졌다.

순서가 엉망이 된 돌들을 보며 흡족해하던 찬우는 재미있는 특징을 발견했다. 바뀐 수열의 최장 감소 부분 수열의 길이가 22밖에 되지 않는다는 것이었다. 찬우는 이를 사진으로 남기려 했지만 배터리가 다 떨어졌다. 대신 자신이 짝지은 돌 중 한 쌍 (X,Y)(X,Y)을 가져가기로 했다.

집에 돌아온 찬우는 방금 만든 수열을 복원하고 싶어졌지만, 기억나는 것은 가져온 돌 XX와 YY가 한 쌍이었다는 사실, 돌의 총 개수 2N2N, 그리고 수열의 최장 감소 부분 수열의 길이가 22였다는 사실뿐이다. 돌의 개수 2N2N과 가져온 쌍 XX, YY가 주어질 때, 조건을 만족하는 돌의 수열이 몇 개인지 구해보자.

입력

첫 번째 줄에 NN, XX, YY가 공백으로 구분되어 주어진다. (1≤N≤500 0001 \le N \le 500\,000; 1≤X,Y≤2N1 \le X, Y \le 2N; X≠YX \ne Y)

출력

조건을 만족하는 돌의 수열의 개수를 998 244 353998\,244\,353으로 나눈 나머지를 출력한다.

힌트

어떤 수열에서 몇 개의 수를 제거해서 부분 수열을 만들 수 있다. 이때 만들어진 부분 수열 중 내림차순으로 정렬된 가장 긴 부분 수열을 최장 감소 부분 수열이라고 한다.

예제1

  1. 예제 1

    입력
    4 5 6
    
    예상 출력
    2