Busy Beaver đang tham gia một lớp học lý thuyết đồ thị, và giáo viên của cậu ấy yêu cầu cậu đếm số lượng các đồ thị thỏa mãn một điều kiện đặc biệt. Hãy giúp cậu ấy giải bài toán đếm đồ thị sau đây!

Cho $P$ là một số nguyên tố lẻ và $N$ là một số nguyên dương. Hãy đếm số lượng đồ thị vô hướng, đơn, có nhãn với $NP$ đỉnh mà không chứa chu trình đơn nào có độ dài $P$. Hãy tính kết quả theo modulo $P$. Lưu ý sự lặp lại của $P$ trong phát biểu này!

Một chu trình đơn trong đồ thị vô hướng là một chu trình không đi qua bất kỳ đỉnh nào quá một lần.

Dữ liệu vào

Dữ liệu vào gồm một dòng chứa hai số nguyên: $P$ ($3 \le P < 5000$) và $N$ ($1 \le N \le 10^9$). $P$ là một số nguyên tố lẻ.

Dữ liệu ra

In ra một số nguyên duy nhất theo modulo $P$.

Nhiệm vụ con

• (25 điểm) $N \le P$ và $P \le 500$.
• (25 điểm) $N \le P$.
• (25 điểm) $P \le 500$.
• (25 điểm) Không có ràng buộc bổ sung.

Ví dụ

Dữ liệu vào 1

3 1

Dữ liệu ra 1

1

Ghi chú

Trong ví dụ đầu tiên, chúng ta đang đếm số lượng đồ thị có nhãn trên $1 \cdot 3 = 3$ đỉnh mà không có chu trình đơn độ dài 3. Trong tổng số $2^3 = 8$ đồ thị, chính xác một đồ thị chứa chu trình đơn độ dài 3, vì vậy có tổng cộng $8 - 1 = 7$ cách. Sau đó, $7 \pmod 3$ bằng 1.

Dữ liệu vào 2

5 4

Dữ liệu ra 2

1

Dữ liệu vào 3

479 166

Dữ liệu ra 3

344