Kỳ thi Olympic Tin học ICPC năm nay là lần đầu mà team TriplẻK được tham gia, các bạn rất hào hứng. Bên cạnh việc luyện tập thì mỗi đêm, công việc chính của các bạn là nghiên cứu các địa điểm du lịch để đi chơi cho thỏa thích. Huế có nhiều nơi để tham quan như: Đại Nội, lăng tẩm các vị vua, cầu Tràng Tiền, và đặc biệt trong đó có Kinh thành Huế, nơi đóng đô của triều Nguyễn trong gần 150 năm. Khu di tích có ~n~ địa điểm tham quan được đánh số từ ~1~ đến ~n~ và điểm thứ ~i~ có tọa độ ~(x_i, y_i)~ được kết nối với nhau bằng một số con đường một chiều. Vì địa hình đặc thù nên những bậc tiền bối chỉ xây dựng đường đi từ địa điểm ~i~ đến ~j~ nếu như ~x_i > x_j~ và ~y_i < y_j~. Để chuẩn bị kỹ lưỡng cho việc du lịch kinh thành một cách hiệu quả, team TriplẻK muốn tính xem với mỗi số ~1 \le k \le n~ thì có bao nhiêu hành trình tham quan đi theo những con đường có sẵn mà qua đúng ~k~ điểm tham quan (hai con đường là khác nhau nếu có một địa điểm có trên đường này mà không có trên con đường kia). Team đang code để giải thử nhưng toàn bị TLE, WA, RTE, ..., nhờ các bạn hỗ trợ giúp nhé.

Input

Dòng đầu tiên gồm số nguyên dương ~n~ với ~1 \le n \le 2000~.

Dòng thứ hai là ~n~ số nguyên ~x_1, x_2, ..., x_n~ và dòng cuối là ~n~ số nguyên ~y_1, y_2, ..., y_n~. Các số này nguyên và có giá trị tuyệt đối không quá ~10^9.~

Output

In ra ~n~ số nguyên không âm, trong đó số thứ ~k~ là số lượng con đường đi qua ~k~ địa điểm mà team TriplẻK muốn đi, lấy modulo ~10^9+7.~

Sample input

6
3 2 6 4 5 1
5 5 6 2 1 4

Sample output

6 7 3 0 0 0

Giải thích:

• Các hành trình gồm 1 điểm tham quan: ~(1); (2); (3); (4); (5); (6).~
• Các hành trình gồm 2 điểm tham quan: ~(4, 1); (4, 2); (4, 6); (5, 1); (5, 2); (5, 4); (5, 6).~
• Các hành trình gồm 3 điểm tham quan: ~(5, 4, 2); (5, 4, 6); (5, 4, 1).~
• Không có hành trình thoả mãn đi qua 4, 5 hoặc 6 điểm tham quan