Cho đồ thị có hướng không có cạnh nối từ một đỉnh đến chính nó, không có cạnh lặp, có trọng số gồm ~n~ đỉnh và ~m~ cạnh. Gọi ~d~ là độ dài đường đi ngắn nhất từ đỉnh ~1~ tới đỉnh ~n~. Đếm số lượng đường đi từ ~1~ tới ~n~ có độ dài không quá ~d + k~. Vì kết quả có thể rất lớn nên kết quả trả về là số dư của nó với số nguyên ~MOD~.

INPUT

Dòng đầu tiên chứa số nguyên ~T~ (~T > 0~), tương ứng với số lượng test case.

Với mỗi test case được đưa ra:

• Dòng đầu tiên chứa bốn số nguyên ~n, m, k, MOD~ (~n, m > 0~, ~k ≥ 0~, ~1 ≤ MOD ≤ 10^9~).
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~a_i~, ~b_i~, ~c_i~ (~1 ≤ a_i, b_i ≤ n~, ~0 \le c_i \le 10^3~) tương ứng với cạnh nổi từ đinh ~a_i~ đến ~b_i~ có trọng số ~c_i~.
• Dữ liệu đảm bảo tồn tại ít nhất một đường đi từ ~1~ tới ~n~.

OUTPUT

Với mỗi test case, ghi ra một số nguyên là kết quả trả về với test case đó trên một dòng. Nếu có vô số đường đi thoả mãn, kết quả trả về ~-1~.

SAMPLE INPUT

1
4 4 2 998244353
1 2 1
2 4 1
2 3 2
3 4 1

SAMPLE OUTPUT

2

SUBTASKS

• ~10 \%~ số điểm có ~T ≤ 5~, ~2n, m ≤ 10~, ~k = 0~, không có cạnh trọng số ~0~.
• ~30 \%~ số điểm có ~T ≤ 5~, ~2n, m ≤ 2 \times 10^3~, ~k = 0~, không có cạnh trọng số ~0~.
• ~10 \%~ số điểm có ~T ≤ 5~, ~2n, m ≤ 2 \times 10^3~, ~k \le 50~, không có cạnh trọng số ~0~.
• ~10 \%~ số điểm có ~T ≤ 5~, ~2n, m ≤ 2 \times 10^3~, ~k \le 50~.
• ~10 \%~ số điểm có ~T ≤ 5~, ~2n, m ≤ 2 \times 10^5~, ~k = 0~, không có cạnh trọng số ~0~.
• ~10 \%~ số điểm có ~T ≤ 3~, ~2n, m ≤ 2 \times 10^5~, ~k \le 50~, không có cạnh trọng số ~0~.
• ~20 \%~ số điểm có ~T ≤ 3~, ~2n, m ≤ 2 \times 10^5~, ~k \le 50~.