Lưu ý: Giới hạn thời gian của bài này là 6 giây, gấp ba lần mặc định. Giới hạn bộ nhớ của bài này là 512 MB, gấp đôi mặc định.

Farmer John có \(N\) (\(1\leq N\leq 5000\)) chú bò đứng quanh một đường đua hình tròn được chia thành \(M\) (\(1\leq M\leq 10^6\)) vị trí cách đều nhau, đánh số từ \(0\) đến \(M-1\) theo chiều kim đồng hồ. Ban đầu, bò \(i\) đứng tại vị trí \(x_i\), trong đó \(0=x_1<x_2<\dots<x_N<M\).

Với mỗi \(1\leq i\leq N\), bò \(i\) sẽ độc lập chọn ngẫu nhiên quay mặt theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ, với xác suất riêng của chú bò đó. Sau khi chọn hướng ban đầu, mỗi chú bò bắt đầu di chuyển liên tục theo hướng ấy với vận tốc không đổi là một vị trí mỗi phút. Mỗi khi hai chú bò gặp nhau (tức là cùng chiếm một vị trí), chúng bật ngược lại khỏi nhau: lập tức đảo hướng rồi tiếp tục di chuyển với cùng vận tốc theo hướng mới.

Farmer John muốn biết bò \(1\) sẽ ở đâu. Với mỗi \(0\leq i<M\), hãy tìm xác suất bò \(1\) ở vị trí \(i\) sau \(K\) (\(1\leq K\leq 10^{18}\)) phút.

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(1\leq T\leq 100\)), là số bộ test độc lập. Mỗi bộ test có định dạng như sau:

Dòng đầu tiên của mỗi bộ test chứa \(N\) (\(1\leq N\leq 5000\)), \(M\) (\(1\leq M\leq 10^6\)) và \(K\) (\(1\leq K\leq 10^{18}\)).

Dòng thứ hai chứa \(N\) số nguyên \(p_1,\dots,p_N\) (\(0\leq p_i<10^9+7\)), trong đó nếu \(\frac{a_i}{b_i}\) là xác suất bò \(i\) đi theo chiều kim đồng hồ thì \(p_i\cdot b_i\equiv a_i\pmod{10^9+7}\).

Dòng thứ ba, cũng là dòng cuối cùng, chứa \(N\) số nguyên \(x_1,x_2,\dots,x_N\).

Đảm bảo rằng tổng \(N^2\) trên tất cả các bộ test không vượt quá \(5000^2\), và tổng \(M\) trên tất cả các bộ test không vượt quá \(10^6\).

Dữ liệu ra

Với mỗi bộ test, in ra một dòng mới. Dòng tương ứng với mỗi bộ test có định dạng như sau:

Với mọi \(0\leq i<M\), gọi \(\frac{p_i}{q_i}\) là xác suất bò \(1\) ở vị trí \(i\) sau \(K\) phút. In ra \(M\) số nguyên cách nhau bởi dấu cách \(p_iq_i^{-1}\pmod{10^9+7}\) (trong đó \(p_iq_i^{-1}\cdot q_i\equiv p_i\pmod{10^9+7}\)).

Ví dụ

3
2 2 1
500000004 500000004
0 1
3 3 1
500000004 500000004 500000004
0 1 2
5 10 13
500000004 1 500000004 0 500000004
0 3 4 7 9

500000004 500000004
500000004 250000002 250000002
0 0 0 125000001 375000003 0 125000001 375000003 0 0

Phân nhóm

• Test 2: \(K\leq 100\), \(N\leq 10\).
• Test 3: \(N\leq 10\).
• Các test 4–7: \(\sum N^3\leq 500^3\).
• Các test 8–11: \(K<\frac{M}{2}\).
• Các test 12–15: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 2, Platinum Division — bài gốc tiếng Anh “Cow Circle”. Tác giả: Sujay Konda. https://usaco.org/index.php?page=viewproblem2&cpid=1573