뒤섞인 돌
시간 제한3초메모리 제한1024 MB
N과 짝 X, Y가 주어졌을 때, 가장 긴 감소 부분수열의 길이가 2인 수열 중 X와 Y가 짝인 경우의 수를 998244353으로 나눈 나머지로 구합니다.
문제
길을 걷던 찬우는 바닥에서 부터 까지의 정수가 차례로 적힌 돌 개를 발견했다. 질서정연하게 정렬된 돌들이 불편하게 느껴진 찬우는 돌의 순서를 마음대로 바꾸기로 했다. 그는 개의 돌을 두 개씩 짝지어 개의 쌍을 만든 뒤, 각 쌍에서 두 돌의 위치를 서로 바꿨다. 이렇게 해서 새로운 수열 이 만들어졌다.
순서가 엉망이 된 돌들을 보며 흡족해하던 찬우는 재미있는 특징을 발견했다. 바뀐 수열의 최장 감소 부분 수열의 길이가 밖에 되지 않는다는 것이었다. 찬우는 이를 사진으로 남기려 했지만 배터리가 다 떨어졌다. 대신 자신이 짝지은 돌 중 한 쌍 을 가져가기로 했다.
집에 돌아온 찬우는 방금 만든 수열을 복원하고 싶어졌지만, 기억나는 것은 가져온 돌 와 가 한 쌍이었다는 사실, 돌의 총 개수 , 그리고 수열의 최장 감소 부분 수열의 길이가 였다는 사실뿐이다. 돌의 개수 과 가져온 쌍 , 가 주어질 때, 조건을 만족하는 돌의 수열이 몇 개인지 구해보자.
입력
첫 번째 줄에 , , 가 공백으로 구분되어 주어진다. (; ; )
출력
조건을 만족하는 돌의 수열의 개수를 으로 나눈 나머지를 출력한다.
힌트
어떤 수열에서 몇 개의 수를 제거해서 부분 수열을 만들 수 있다. 이때 만들어진 부분 수열 중 내림차순으로 정렬된 가장 긴 부분 수열을 최장 감소 부분 수열이라고 한다.