미니언과 방

그루의 지하실에는 미니언 $N$마리가 살고, 각 미니언에는 $1$번부터 $N$번까지 번호가 붙어 있다. 지하실에는 수용 인원 제한이 없는 방이 $M$개 있고, 각 방은 사용 가능 또는 사용 불가 중 한 가지 상태다. 그루는 매일 연속한 구간에 있는 방의 상태를 모두 뒤집는다.

미니언은 사용 가능한 방에만 살 수 있다. 또 사용 가능한 방에는 미니언이 한 마리 이상 들어가야 한다. 방은 서로 구분하지 않는다. 즉 배치 $A$의 모든 방에 대해, 그 방에 있는 미니언 번호 집합과 똑같은 집합을 가진 방이 배치 $B$에도 있으면 $A$와 $B$는 같은 배치로 센다.

처음에는 모든 방이 사용 가능하다. 이어지는 $D$일 동안, 그루가 그날의 구간을 뒤집은 직후 미니언을 배치하는 방법의 수를 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다 ($T \le 10$).

각 테스트 케이스의 첫째 줄에 정수 $N$, $M$, $D$가 공백으로 구분되어 주어진다 ($1 \le M \le N \le 100000$, $1 \le D \le 100000$).

이어지는 $D$개 줄에 정수 $L$과 $R$이 공백으로 구분되어 주어진다 ($1 \le L \le R \le M$). 그루는 그날 방 $L, L+1, \dots, R$의 상태를 뒤집는다.

각 질의마다 미니언을 배치하는 방법의 수를 $880803841$로 나눈 나머지를 한 줄에 하나씩 출력한다.