Hoàng tử Nếch
Công chúa đã bị tên phù thủy xấu xa bắt cóc và giam giữ trên một tòa tháp, và Hoàng tử Nếch phải tiến vào tòa tháp để giải cứu nàng. Tuy nhiên, để ngăn chặn điều này, tên phù thủy đã phù phép và biến tòa tháp thành một mê cung phức tạp với rất nhiều lối đi.
Tòa tháp sẽ có \(3\) tầng, mỗi tầng có \(n\) phòng được xây dựng như một đa giác có \(n\) đỉnh và được đánh số như sau:
- Tầng thứ nhất: Phòng \(1\) tới phòng \(n\).
- Tầng thứ hai: Phòng \(n+1\) tới phòng \(2*n\). Phòng \(n+1\) sẽ thẳng với phòng \(1\), phòng \(n+2\) thẳng với phòng \(2\), ... phòng \(2*n\) thẳng với phòng \(n\).
- Tầng thứ ba: Phòng \(2*n+1\) tới phòng \(3*n\). Phòng \(2*n+1\) sẽ thẳng với phòng \(n+1\) và \(1\), phòng \(2*n+2\) thẳng với phòng \(n+2\) và \(2\), ... phòng \(3*n\) thẳng với phòng \(2*n\) và \(n\).
Ví dụ với \(n = 4\):
Hoàng tử Nếch sẽ bước vào tòa tháp từ phòng \(1\). Tuy nhiên, do tòa tháp đầy rẫy nguy hiểm, anh cần biết chính xác có bao nhiêu cách để đi từ phòng \(1\) đến phòng \(x\) sau đúng \(k\) bước.
Chú ý:
- Hoàng tử Nếch sẽ không được quay lại phòng vừa thăm ở bước ngay trước đó.
- Anh chỉ có thể di chuyển dọc theo các hành lang là cạnh của tòa tháp.
- Các cạnh có thể được đi lại nhiều lần.
- Vì số lượng cách đi có thể rất lớn nên Hoàng tử Nếch cần kết quả theo modulo \(10^9+7\).
Đầu vào
Một dòng duy nhất gồm ba số nguyên \(n, x, k\). \((3 \le n \le 15, 1 \le x \le 3*n, 1 \le k \le 10^{10})\)
Đầu ra
Một số nguyên duy nhất là kết quả bài toán theo modulo \(10^9+7\).
Subtask
\(20\%\) số test có \(n \le 5, k \le 20\).
\(30\%\) số test có \(k \le 1000\).
\(50\%\) số test còn lại không có ràng buộc gì thêm.
Ví dụ
Đầu vào
4 7 3Đầu ra
6
Comments
tôi thật sự rất muốn theo dõi hành trình của Nếch, bạn có thể viết tiếp câu chuyện của Nếch và công chúa bằng 1 bài 5 điểm được không!!!
sao bạn không giúp Nếch AC bài này đi =)))
khong, hay mo mot giac mo di
nâuu
Nếch đã về nhất trong giải những người về nhì