25612번 - 정렬 프로그램

서울대학교 컴퓨터공학부 학생들은 2학년이 되면 전공 필수 과목인 “논리설계”를 수강하게 된다. 논리설계 과목의 꽃은 역시 학기말에 주어지는 파이널 프로젝트 과제로, FPGA(Field Programmable Gate Array)를 이용해서 주어진 스펙에 맞춰서 프로그램을 구현해야 하는 과제이다. 올해 논리설계 과목의 파이널 프로젝트는, 1 이상 M 이하의 정수 N개를 입력으로 받아 오름차순으로 정렬하는 프로그램을 구현하는 과제이다.

학생들이 구현에 사용할 수 있는 연산은 다음의 conditional_swap 연산뿐이다. 즉, 모든 학생들의 프로그램은 conditional_swap 연산의 나열로 이루어져 있다.

• conditional_swap(x, y): x번째 정수가 y번째 정수보다 크면 두 정수의 위치를 뒤바꾼다.

이번 학기 논리설계 과목의 조교장을 맡은 민준이는 학생들이 구현한 프로그램을 채점하는 일을 하고 있다. 학생이 받는 점수는, 프로그램에 의해 오름차순으로 정렬되는 수열의 개수이다. 학생의 프로그램이 주어졌을 때, 민준이를 도와 학생이 받을 점수를 계산해주자.

첫째 줄에 N, M, K가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 18; 1 ≤ M ≤ 10⁹; 0 ≤ K ≤ 1 000)

둘째 줄부터 K개의 줄에 x, y가 공백으로 구분되어 주어진다. (1 ≤ x, y ≤ N)

학생이 받을 점수를 998 244 353로 나눈 나머지를 출력한다. 998 244 353 = 119 × 2²³ + 1은 소수이다.