정렬 프로그램

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

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

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

이번 학기 조교장을 맡은 민준이는 학생들의 프로그램을 채점한다. 학생이 받는 점수는 프로그램이 오름차순으로 정렬하는 수열의 개수이다. 학생의 프로그램이 주어졌을 때 민준이를 도와 학생이 받을 점수를 계산하자.

첫째 줄에 $N$, $M$, $K$가 공백으로 구분되어 주어진다. ($1 \le N \le 18$; $1 \le M \le 10^9$; $0 \le K \le 1000$)

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

학생이 받을 점수를 998244353으로 나눈 나머지를 출력한다. $998\,244\,353 = 119 \times 223 + 1$은 소수이다.