Quốc gia nơ-ron

Một đất nước được tổ chức thành $L$ tầng, mỗi tầng có đúng $N$ thành phố. Ngoài ra có một điểm vào và một điểm ra.

• Từ điểm vào có đường đi tới mọi thành phố của tầng $1$. Chi phí đi tới thành phố thứ $j$ của tầng $1$ là $u_j$.
• Với hai tầng liên tiếp bất kỳ, mỗi thành phố của tầng trước nối tới mọi thành phố của tầng sau. Chi phí của cạnh đi vào thành phố thứ $j$ của tầng sau luôn bằng $v_j$: nó không phụ thuộc vào thành phố xuất phát, và mọi cặp tầng liên tiếp đều dùng chung bộ chi phí này.
• Từ thành phố thứ $j$ của tầng $L$ có đường đi tới điểm ra với chi phí $w_j$.

Một đường đi từ điểm vào tới điểm ra đi qua đúng một thành phố ở mỗi tầng, theo thứ tự tầng $1,2,\dots ,L$. Chi phí của đường đi là tổng chi phí các cạnh trên đường đi đó. Hai đường đi được xem là khác nhau nếu dãy thành phố mà chúng đi qua khác nhau, kể cả khi tổng chi phí bằng nhau.

Hãy đếm số đường đi có tổng chi phí chia hết cho $M$. In ra kết quả theo modulo ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $N$, $L$, $M$.
• Dòng thứ hai chứa $N$ số nguyên $u_1,u_2,\dots ,u_N$: chi phí từ điểm vào tới từng thành phố của tầng $1$.
• Dòng thứ ba chứa $N$ số nguyên $v_1,v_2,\dots ,v_N$: chi phí đi vào từng thành phố khi chuyển giữa hai tầng liên tiếp.
• Dòng thứ tư chứa $N$ số nguyên $w_1,w_2,\dots ,w_N$: chi phí từ từng thành phố của tầng $L$ tới điểm ra.

Dữ liệu ra

Một số nguyên duy nhất: số đường đi có tổng chi phí chia hết cho $M$, lấy theo modulo ${10}^9+7$.

Ràng buộc

• $1\le N\le {10}^6$
• $2\le L\le {10}^5$
• $2\le M\le 100$
• $0\le u_j,v_j,w_j\le M$

Ví dụ