Cho một hình lăng trụ với mỗi đáy là 1 đa giác n đỉnh. Một chất điểm xuất phát từ đỉnh 1 và muốn đi đến đỉnh x của hình lăng trụ và phải đi qua đúng p bước. Ta đánh số các đỉnh của đa giác như sau:

• Mặt đáy trên của đa giác được đánh số từ 1 đến n ngược chiều kim đồng hồ.
• Đỉnh nằm ở mắt đáy dưới và chung cạnh với đỉnh 1 sẽ là đỉnh n+1 và đánh dấu lần lượt ngược chiều kim đồng hồ cho đến đỉnh thứ 2*n.

Ví dụ với n = 5:

Yêu cầu:

• Đếm số cách đi từ đỉnh 1 đến đỉnh x qua đúng p bước sao cho tại mỗi bước chất điểm sẽ không đi lại đỉnh mà chất điểm đã thăm ở bước ngay trước đó.
• Hành trình phải đi qua trên các cạnh.
• Mỗi cạnh được phép đi nhiều lần trên hành trình.
• Kết quả theo module 2012.

Input

Gồm 3 số n, x, p (3 <= n <= 10, 1 <= x <= 2*n, 1 <= p <= 2*10^9)

Output

Kết quả theo module 2012.

Example

Input
5 2 3

Output
1

Chú ý: 50% số test với p <= 20