Một đất nước có \(n\) thành phố, đánh số \(1,2,\ldots,n\), được nối bởi \(m\) con đường hai chiều. Số đường nhiều hơn số thành phố không quá \(10\), và luôn có thể đi giữa hai thành phố bất kỳ qua một hoặc nhiều con đường.

Một du khách lập kế hoạch chuyến đi với các điều kiện sau:

• Chuyến đi bắt đầu tại thành phố \(1\) và kết thúc tại thành phố \(n\).
• Chuyến đi gồm đúng \(k\) bước, mỗi bước đi qua một con đường.
• Không được đi tới rồi quay lại ngay trên cùng một con đường trong hai bước liên tiếp. Vẫn được dùng cùng một con đường nhiều lần nếu giữa hai lần dùng có bước khác.

Có bao nhiêu kế hoạch đi từ thành phố \(1\) tới thành phố \(n\) trong đúng \(k\) bước? Hai kế hoạch khác nhau nếu tại một bước nào đó chúng đi tới hai thành phố khác nhau.

Dữ liệu vào

Dòng đầu chứa ba số nguyên \(n,m,k\), lần lượt là số thành phố, số con đường và số bước của chuyến đi.

\(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên phân biệt \(u,v\), biểu thị một con đường nối hai thành phố đó. Giữa hai thành phố có nhiều nhất một con đường.

Dữ liệu ra

In số kế hoạch khác nhau theo modulo \(10^9+7\).

Ràng buộc

• \(2\le n\le2\cdot10^5\).
• \(n-1\le m\le n+10\).
• \(1\le k\le10^4\).

Phân nhóm

1. \(7\) điểm: \(n,k\le10\).
2. \(8\) điểm: \(n,k\le100\).
3. \(11\) điểm: \(m=n-1\).
4. \(29\) điểm: \(m=n-1\) hoặc \(m=n\).
5. \(15\) điểm: \(n\le1000\).
6. \(30\) điểm: không có ràng buộc thêm.

4 5 5
1 2
1 3
2 3
2 4
3 4

4

4 3 4
1 2
2 3
2 4

0

Nguồn

Baltic Olympiad in Informatics 2026 - đề và dữ liệu chính thức.