State Reversing

Time Limit: 2 Seconds

Memory Limit: 131072 KB

Description

Yakumo Yukari is with no doubt one of the most powerful youkai in Gensokyo. Her ability is manipulating boundaries. She has N unknown creatures called "sinsack" or "the crime bag" which live in the basement of Yukari's house. Sinsacks are numbered from 1 to N. There are M rooms with infinite capacity in the basement and each room has two states: available or unavailable. Yukari will reverse the state of consecutive rooms every day. Sinsacks can only live in available rooms. And each available room should contain at least one sinsack.

As a 17-year-old girl, recently Yukari is interested in how many different ways to arrange sinsacks in rooms. At the beginning, all rooms are available. In the following D days, Yukari will ask you the number of ways after reversing. Two ways A and B are regarded as the same if for any room in A, there exists a room in B that the sinsacks in these two rooms have the same set of numbers. In other words, rooms are indistinguishable.

Input

The first line of the input contains an integer T (T ≤ 10), indicating the number of cases. For each test case:
The first line contains three integers N, M and D (1 ≤ MN, D ≤ 100000). Their meanings are described above.
The following D lines each contain two integers l and r (1 ≤ lr ≤ M) denoting the consecutive rooms l, l + 1, ..., r which are reversed by Yukari on that day.

Output

For each query, output the number of different ways to arrange sinsacks. The answer should modulo 880803841 for it can be very large.

Sample Input

2
3 3 2
2 2
1 3
5 5 3
1 3
2 2
1 5

Sample Output

3
1
15
25
15

Hint

None

Source

None

提交代码