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