Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P178PROE - ROUND 8E - MINIONS

 

Có N minion đang sống trong nhà của Gru. Nhà có M phòng với khả năng chứa số lượng không hạn chế các minion. Mỗi phòng sẽ có hai trạng thái: sẵn sàng và không sẵn sàng. Các minion chỉ được vào ở trong các căn phòng đã sẵn sàng. Và mỗi phòng đã sẵn sàng cũng sẽ chứa ít nhất 1 minion.
Gru muốn tính xem có bao nhiêu cách khác nhau để sắp xếp các phòng ở cho các minion. Ban đầu, tất cả N phòng đều sẵn sàng. Trong D ngày tiếp theo, Gru muốn tính xem có bao nhiêu cách khác nhau nếu thay đổi trạng thái một số phòng so với ngày hôm trước. Hai cách sắp xếp A và B được coi là giống nhau nếu với mỗi phòng trong cách A có số lượng minion là k thì cũng sẽ có một phòng trong cách B có số lượng tương tự.

Có N minion đang sống trong nhà của Gru. Nhà có M phòng với khả năng chứa số lượng không hạn chế các minion. Mỗi phòng sẽ có hai trạng thái: sẵn sàng và không sẵn sàng. Các minion chỉ được vào ở trong các căn phòng đã sẵn sàng. Và mỗi phòng đã sẵn sàng cũng sẽ chứa ít nhất 1 minion.

Gru muốn tính xem có bao nhiêu cách khác nhau để sắp xếp các phòng ở cho các minion. Ban đầu, tất cả N phòng đều sẵn sàng. Trong D ngày tiếp theo, Gru muốn tính xem có bao nhiêu cách khác nhau nếu thay đổi trạng thái một số phòng so với ngày hôm trước. Hai cách sắp xếp A và B được coi là giống nhau nếu với mỗi phòng trong cách A có số lượng minion là k thì cũng sẽ có một phòng trong cách B có số lượng tương tự.

 

Input

Dòng đầu ghi số bộ test, không quá 10. Mỗi bộ test gồm:

- Dòng đầu tiên ghi 3 số N,M,D (1<=M<=N, D<=100000).

- Tiếp theo là D dòng, mỗi dòng ghi hai số L và R (1<=L<=R<=M) cho biết các phòng có thứ tự từ L đến R sẽ được Gru đảo ngược trạng thái trong ngày đó.

Output

Với mỗi ngày trong danh sách, ghi ra tổng số cách sắp xếp khác nhau tìm được, chia modulo cho 880803841.

Example

Input:
2
3 3 2
2 2
1 3
5 5 3
1 3
2 2
1 5 Output: 3
1
15
25
15 

Được gửi lên bởi:Admin
Ngày:2017-04-17
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.