Minions and the rooms

Gru's basement holds $N$ minions numbered $1$ to $N$. The basement has $M$ rooms of unlimited capacity, and every room is either available or unavailable. Each day Gru flips the state of every room in one consecutive range.

A minion can live only in an available room, and every available room must hold at least one minion. The rooms are indistinguishable: two arrangements $A$ and $B$ count as the same when, for every room in $A$, some room in $B$ holds exactly the same set of minion numbers.

At the start every room is available. For each of the $D$ following days, report the number of arrangements right after Gru flips that day's range.

The first line contains an integer $T$, the number of test cases ($T \le 10$).

The first line of each test case contains three space separated integers $N$, $M$ and $D$ ($1 \le M \le N \le 100000$, $1 \le D \le 100000$).

Each of the next $D$ lines contains two space separated integers $L$ and $R$ ($1 \le L \le R \le M$). On that day Gru flips the state of rooms $L, L+1, \dots, R$.

For each query, print the number of arrangements modulo $880803841$ on its own line.