Thành phố X vừa hoàn thiện hệ thống giao thông gồm giao lộ và đoạn đường hai chiều nối giữa các giao lộ này. Hệ thống giao thông này có một đặc điểm quy hoạch đặc biệt để tránh ùn tắc cục bộ: mỗi đoạn đường chỉ thuộc về tối đa một chu trình đơn khép kín. Đảm bảo không có đoạn đường nào nối một giao lộ với chính nó, nhưng có thể có nhiều đoạn đường riêng biệt nối cùng một cặp giao lộ.
Sở Giao thông vận tải quyết định chuyển đổi toàn bộ đoạn đường hai chiều này thành đường một chiều để tối ưu hóa luồng di chuyển. Tuy nhiên, do hạn chế về cơ sở hạ tầng đèn tín hiệu, tại giao lộ thứ , hệ thống chỉ có thể điều tiết an toàn nếu có tối đa con đường dẫn luồng xe đi ra khỏi giao lộ đó.
Nhiệm vụ của bạn là hãy đếm xem có bao nhiêu phương án thiết lập chiều di chuyển cho tất cả các đoạn đường sao cho thỏa mãn điều kiện về khả năng thoát xe tại từng giao lộ.
Dữ liệu:
Dòng đầu tiên gồm hai số nguyên dương (số giao lộ và số đoạn đường).
dòng tiếp theo, mỗi dòng chứa hai số nguyên dương, biểu thị một đoạn đường nối giữa hai giao lộ.
Dòng cuối cùng gồm số nguyên dương, số thứ là giá trị của (giới hạn số đường đi ra tại giao lộ ).
Kết quả: In ra một số nguyên không âm là số lượng phương án quy hoạch thỏa mãn sau khi lấy phần dư cho .
Ví dụ:
Dữ liệu:
3 4
1 2
2 1
2 3
3 2
1 2 3
Kết quả:
7
Giới hạn: .
Subtask 1 (10% số điểm):
Subtask 2 (10% số điểm): và
Subtask 3 (20% số điểm):
Subtask 4 (20% số điểm):
Subtask 5 (20% số điểm): Mỗi giao lộ thuộc về tối đa một chu trình đơn.
Subtask 6 (20% số điểm): Không có giới hạn đặc biệt.
