Hưởng ứng phong trào toàn dân tập thể dục, An là một người thích đi bộ tập thể dục, thật may phía trước nhà An có một công viên ở đó có một cái hồ nhỏ. An thường đi bộ tập thể dục xung quanh hồ. An đi bộ đều chân đạt đến mức nếu đi một vòng quanh hồ, từ vị trí xuất phát sau khi đi trở về đúng vị trí xuất phát ban đầu theo cùng hay ngược chiều kim đồng hồ. Cô ấy luôn bước đúng ~N~ bước, khoảng cách giữa ~2~ vị trí giữa đầu và cuối của mỗi bước đều bằng nhau. Do vậy có thể đánh dấu ~1~ vòng trên bờ hồ theo chiều kim đồng hồ bằng các vị trí ~1, 2, 3, \dots, N~, hai vị trí liên tiếp cách đều đúng ~1~ bước chân của An.

Mỗi buổi sáng, An sẽ thực hiện đi bộ bước đúng ~k~ bước, xuất phát từ vị trí ~1~ và kết thúc cũng tại vị trí ~1~. Cô ấy muốn biết có bao nhiêu cách khác để nhau thực hiện kế hoạch trên. Hai cách đi đi bộ được gọi là khác nhau nếu như tồn tại một vị trí ~i~ ~(1 \le i \le k)~ mà vị trí ở bước thứ trong hai cách khác nhau.

Yêu cầu: Viết chương trình giúp An tính số cách đi bộ đúng ~k~ bước.

Input

Gồm duy nhất một dòng chứa ba số nguyên ~N, k, M~ ~(N < 4000, 1 \le k \le 10^6, M < 10^9 + 7)~

Output

Một số nguyên duy nhất là phần dư trong phép chia số lượng cách đi bộ tìm được cho ~M~

Scoring

Sample Input 1

3 4 100

Sample Output 1

6

Notes

Có ~6~ cách thực hiện thỏa mãn điều kiện là:

~(1, 2, 3, 2, 1)~ ~(1, 3, 2, 3, 1)~ ~(1, 2, 1, 2, 1)~ ~(1, 3, 1, 3, 1)~ ~(1, 2, 1, 3, 1)~ ~(1, 3, 1, 2, 1)~