Nhân ma trận: Đếm số đường đi độ dài đúng K trên đồ thị có hướng

Input

• Dòng đầu gồm bốn số nguyên N, M, K, S, T (1 ≤ N ≤ 100, 0 ≤ M ≤ 10 000, 1 ≤ K ≤ 10¹⁸, 0 ≤ S, T < N).
• M dòng tiếp theo, mỗi dòng gồm hai số nguyên u, v mô tả một cạnh có hướng từ u đến v (0 ≤ u, v < N).

Input:
3 4 3 0 2
0 1
1 2
2 0
0 2

Output:
1

Output

• In ra một số nguyên duy nhất là số đường đi thỏa mãn theo modulo 10⁹ + 7.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Input

• Các tham số truyền vào hàm/lớp solution hoặc dữ liệu đầu vào theo định dạng mô tả.

Output

• Kết quả trả về của hàm/lớp solution hoặc dữ liệu in ra màn hình theo đúng đặc tả.

Ràng buộc

• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào tuân thủ đúng định dạng và miền giá trị được mô tả.

Ví dụ 1

Thành công / Đáp ứng đầy đủ ràng buộc