Hoàng tử Nếch

Points: 4

Time limit: 1.0s

Memory limit: 977M

Author:

Problem type

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 \leq n \leq 15, 1 \leq x \leq 3 * n, 1 \leq k \leq 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 \leq 5, k \leq 20$ .

$30 %$ số test có $k \leq 1000$ .

$50 %$ số test còn lại không có ràng buộc gì thêm.

Ví dụ

Đầu vào

Copy

4 7 3

Đầu ra

Copy

Comments

1

TrinhThanhNam_CNTT1_K62 commented on Nov. 19, 2024, 6:18 a.m.

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!!!

0

NguyenHaKien_CNTT4_K63 commented on Nov. 19, 2024, 7:35 a.m.

sao bạn không giúp Nếch AC bài này đi =)))

0

Manh_KHMT_K64 commented on Nov. 19, 2024, 6:20 a.m.

khong, hay mo mot giac mo di

0

TrinhThanhNam_CNTT1_K62 commented on Nov. 19, 2024, 6:21 a.m.

nâuu

2

DongDucManh_KHMT_K64 commented on Nov. 4, 2024, 12:04 p.m.

Nếch đã về nhất trong giải những người về nhì