문제

이 문제의 시간 제한은 6초로, 기본 제한의 3배이다. 메모리 제한은 512MB로, 기본 제한의 2배이다.

알고리즘 동아리 ANA의 부원 $N$ ($1 \le N \le 5000$)명이 $M$ ($1 \le M \le 10^6$)개의 칸으로 일정하게 나뉘어 있는 원형 트랙 위에 서 있다. 트랙의 각 칸은 시계 방향으로 $0$부터 $M-1$까지 번호가 매겨져 있다. $i$번째 부원은 처음에 $x_i$ 위치에 서 있으며, $0 = x_1 < x_2 < \dots < x_N < M$을 만족한다.

각 부원 $i$는 독립적으로 각자에게 주어진 확률에 따라 시계 방향 또는 반시계 방향 중 하나를 선택한다. 방향을 정하면, 모든 부원은 동시에 선택한 방향으로 매분 $1$칸씩 일정한 속도로 이동하기 시작한다. 이동하는 도중 두 부원이 같은 위치에서 만나면, 즉시 서로 튕겨져 나가며 방향을 반대로 바꾸고 기존과 같은 속도로 이동을 계속한다.

동아리원들은 $1$번 부원인 서현이가 어디에 있게 될지 궁금해졌다. 각 $0 \le i < M$에 대하여, $K$ ($1 \le K \le 10^{18}$)분이 지난 후 서현이가 위치 $i$에 있을 확률을 구하시오.

입력

첫째 줄에 독립적인 테스트 케이스의 개수 $T$ ($1 \le T \le 100$)가 주어진다. 각 테스트 케이스는 다음과 같이 구성된다.

각 테스트 케이스의 첫째 줄에 $N$, $M$, $K$가 공백으로 구분되어 주어진다. ($1 \le N \le 5000$; $1 \le M \le 10^6$; $1 \le K \le 10^{18}$)

둘째 줄에는 $N$개의 정수 $p_1, \dots, p_N$ ($0 \le p_i < 10^9 + 7$)이 주어진다. 만약 $i$번째 부원이 시계 방향으로 이동할 확률을 기약분수 $\frac{a_i}{b_i}$로 나타냈을 때, $p_i \cdot b_i \equiv a_i \pmod{10^9 + 7}$을 만족한다.

셋째 줄에는 $N$개의 정수 $x_1, x_2, \dots, x_N$이 공백으로 구분되어 주어진다.

모든 테스트 케이스에 대하여 $N^2$의 합은 $5000^2$ 이하이고, $M$의 합은 $10^6$ 이하임이 보장된다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 결과를 출력한다.

각 $0 \le i < M$에 대하여, $K$분이 지났을 때 서현이가 위치 $i$에 있을 확률을 $\frac{p_i}{q_i}$라고 하자. 이때 $p_i q_i^{-1} \pmod{10^9 + 7}$을 만족하는 $M$개의 정수를 공백으로 구분하여 출력한다.

예제 입력 1

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

예제 출력 1

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

점수

• 테스트 케이스 2: $K \le 100, N \le 10$.
• 테스트 케이스 3: $N \le 10$.
• 테스트 케이스 4-7: $\sum N^3 \le 500^3$.
• 테스트 케이스 8-11: $K < \frac{M}{2}$.
• 테스트 케이스 12-15: 추가적인 제약 조건 없음.