Submit solution
Points:
0.50 (partial)
Time limit:
1.0s
Memory limit:
256M
Input:
stdin
Output:
stdout
Author:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Bản đồ của ~1~ khu rừng được chia thành các ô vuông bằng nhau và biểu diễn dưới dạng mặt phẳng ~Oxy~ (mỗi ô ứng với ~1~ điểm có tọa độ nguyên). Một đám cháy rừng sẽ diễn ra như sau :
- Ban đầu chỉ có ~1~ ô bị cháy.
- Sau ~1~ đơn vị thời gian, đám cháy sẽ lan sang các ô có chung đỉnh hoặc chung cạnh với các ô đang cháy.
Cho ~2~ điểm ~A(0, a)~ và ~B(b, 0)~ trên mặt phẳng, bạn cần phải đi từ ~A~ đến ~B~ sao cho mỗi bước chỉ được đi xuống hoặc sang phải. Ngoài ra bạn cần trả lời các truy vấn sau:
- Mỗi truy vấn cho ~1~ cặp số ~x, t~. Hỏi nếu có ~1~ đám cháy ở ô ~(x, x)~ và đã kéo dài ~t~ đơn vị thời gian thì có bao nhiêu cách đi từ ~A~ tới ~B~ mà không đi qua các ô bị cháy ?
Ví dụ khi có điểm ~A(0, 4)~ và ~B(4, 0)~:
Input
- Gồm ~2~ dòng chứa ~2~ số nguyên ~a~ , ~b~ (thể hiện tọa độ điểm ~A~ và ~B~ như đề bài) và số nguyên ~Q~ là số lượng truy vấn. ~(1 \le a, b \le 10^{6})~ ~(1 \le q \le 3 \times 10^{5})~
- ~Q~ dòng tiếp theo , mỗi dòng chứa ~2~ số nguyên ~x~ , ~t~ là câu hỏi cho mỗi truy vấn. ~(0 \le |x|, t \le 10^{9})~
Output
- In ra ~Q~ dòng, mỗi dòng là phần dư của kết quả truy vấn đó sau khi chia cho ~10^9+7~.
Sample Input
4 4 2
2 1
2 0
Sample Output
2
34
Subtask
- ~20\%~ số test có ~a \times b \le 1000000~ , ~q = 1~
- ~20\%~ số test tiếp theo có ~q = 1~ và ~x \le 0~
- ~60\%~ số test còn lại không có điều kiện gì thêm
Comments