Kỳ thi Duyên Hải bổ ích

Tháng 7 năm 2023, lần đầu tiên Hiếu được tham dự cuộc thi học sinh giỏi Duyên hải và Đồng bằng Bắc Bộ năm 2023 tại tỉnh Thái Nguyên. Lần đầu tiên được đi thi xa nhà cậu được bố mẹ giao cho công việc chuẩn bị và lên kế hoạch cho chuyến đi. Hiếu rất hào hứng và tìm hiểu các thông tin về tỉnh Thái Nguyên để sau kì thi bổ ích Hiếu có một chuyến tham quan bổ ích.

Tỉnh Thái Nguyên, là một trong những trung tâm chính trị, kinh tế của khu Việt Bắc nói riêng, của vùng trung du miền núi Đông Bắc nói chung, là cửa ngõ giao lưu kinh tế xã hội giữa vùng trung du miền núi với vùng đồng bằng Bắc Bộ; phía Bắc tiếp giáp với tỉnh Bắc Kạn, phía Tây giáp với các tỉnh Vĩnh Phúc, Tuyên Quang, phía Đông giáp với các tỉnh Lạng Sơn, Bắc Giang và phía Nam tiếp giáp với thủ đô Hà Nội; diện tích tự nhiên $3.562,82$ km².

Tỉnh Thái Nguyên có $n$ điểm tham quan được đánh số từ $1$ tới $n$, điểm tham quan thứ $i$ có tọa độ $(x_i,y_i)$, được kết nối với nhau bằng những con đường một chiều. Vì địa hình đặc thù nên chính phủ chỉ xây đường đi từ điểm tham quan thứ $i$ tới điểm tham quan thứ $j$ nếu như $x_i>x_j$ và $y_i<y_j$ (cả hai bất đẳng thức đều ngặt, và với mọi cặp $i,j$ thỏa mãn điều kiện này đều có đường đi từ $i$ tới $j$). Để chuẩn bị kĩ lưỡng cho chuyến đi, cậu muốn tìm hiểu xem với mỗi số nguyên dương $l$ $(1\le l\le n)$, có bao nhiêu hành trình tham quan đi theo những đường đi có sẵn mà đi qua đúng $l$ điểm tham quan. Một hành trình là một dãy điểm tham quan $p_1,p_2,\dots ,p_l$ mà có đường đi từ $p_t$ tới $p_{t+1}$ với mọi $1\le t<l$; mỗi điểm tham quan đứng riêng cũng là một hành trình đi qua $1$ điểm.

Các bạn lập trình viên hãy giúp Hiếu nghiên cứu vấn đề này nhé. Lấy kết quả theo modulo ${10}^9+7$.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương $n$ $(1\le n\le 2000)$, số điểm tham quan.
• Dòng thứ hai chứa $n$ số nguyên $x_1,x_2,\dots ,x_n$ $(0\le |x_i|\le {10}^9)$ là hoành độ của các điểm tham quan.
• Dòng thứ ba chứa $n$ số nguyên $y_1,y_2,\dots ,y_n$ $(0\le |y_i|\le {10}^9)$ là tung độ của các điểm tham quan.

Các tọa độ có thể âm và có thể trùng nhau.

Dữ liệu ra

In ra một dòng gồm $n$ số nguyên không âm, số thứ $i$ là số hành trình đi qua đúng $i$ điểm tham quan, tính theo modulo ${10}^9+7$.

Ràng buộc

• $1\le n\le 2000$.
• $|x_i|,|y_i|\le {10}^9$.

Subtasks

• Subtask 1 ($20\%$ số test): $n\le 10$.
• Subtask 2 ($20\%$ số test): $n\le 500$.
• Subtask 3 ($60\%$ số test): không có ràng buộc gì thêm.

Ví dụ