Tí rất thích đi dạo công viên. Công viên có thể được xem như một đồ thị có hướng gồm điểm và cạnh, không có khuyên và cạnh song song. Trong đó, điểm 1 là cổng vào, điểm là cổng ra. Mỗi cạnh có một trọng số không âm, đại diện cho thời gian Tí cần để đi qua cạnh đó.
Mỗi ngày Tí đều đi dạo công viên, luôn đi vào từ điểm 1 và ra tại điểm .
Tí thích những điều mới mẻ, không muốn có hai ngày nào đi dạo theo lộ trình hoàn toàn giống nhau. Đồng thời, bạn ấy cũng là một học sinh chăm chỉ, không muốn tốn quá nhiều thời gian cho việc dạo công viên mỗi ngày. Nếu đường đi ngắn nhất từ điểm 1 đến điểm có độ dài là , thì Tí chỉ thích những lộ trình có độ dài không quá .
Tí muốn biết tổng cộng có bao nhiêu lộ trình thỏa mãn điều kiện, bạn có thể giúp cậu ấy không?
Để tránh kết quả quá lớn, hãy đưa ra đáp án sau khi chia lấy dư cho . Nếu có vô số lộ trình hợp lệ, hãy xuất ra -1.
Dữ liệu:
Dòng đầu tiên chứa một số nguyên , đại diện cho số lượng bộ dữ liệu.
Tiếp theo là bộ dữ liệu, với mỗi bộ:
Dòng đầu tiên chứa bốn số nguyên .
dòng tiếp theo, mỗi dòng chứa ba số nguyên , đại diện cho một cạnh có hướng từ điểm đến với trọng số .
Dữ liệu đảm bảo: tồn tại ít nhất một lộ trình hợp lệ.
Kết quả: Xuất ra dòng, mỗi dòng một số nguyên là đáp án.
