Busy Beaver 正在上图论课，他的老师要求他计算满足特定条件的图的数量。请帮他解决这个关于图计数的问题！

设 $P$ 为一个奇素数，$N$ 为一个正整数。计算顶点数为 $NP$ 的无向带标号简单图中，不包含长度为 $P$ 的简单圈的图的数量。计算结果对 $P$ 取模。注意题目中 $P$ 的重复出现！

无向图中的简单圈是指一个不重复经过任何顶点的圈。

输入格式

输入为一行，包含两个整数：$P$ ($3 \le P < 5000$) 和 $N$ ($1 \le N \le 10^9$)。$P$ 是一个奇素数。

输出格式

输出一个整数，表示结果对 $P$ 取模后的值。

子任务

• (25 分) $N \le P$ 且 $P \le 500$。
• (25 分) $N \le P$。
• (25 分) $P \le 500$。
• (25 分) 无附加限制。

样例

输入格式 1

3 1

输出格式 1

1

输入格式 2

5 4

输出格式 2

1

输入格式 3

479 166

输出格式 3

344

说明

在第一个样例中，我们计算的是顶点数为 $1 \cdot 3 = 3$ 的带标号图中，不包含长度为 3 的简单圈的图的数量。在总共 $2^3 = 8$ 个图中，恰好有一个图包含长度为 3 的简单圈，因此总共有 7 种情况。最后，$7 \pmod 3 = 1$。