AT_jsc2021_d.Nowhere P

给你一个大于或等于 $2$ 的整数 $P$。

如果一个整数序列 $A_1, A_2, ..., A_N$ 满足以下条件，那么它被称为一个非常好的序列。

对于 $1$ 到 $N$ 之间的任何整数 $i$，$A_1+A_2+\dots+A_i$ 不是 $P$ 的倍数

总共有 $(P-1)^N$ 个长度为 $N$ 的整数序列，其中每个元素都在 $1$ 和 $P-1$ 之间，这些序列中有多少个是非常好的？

答案可能非常大，所以输出对 $10^9+7$ 取模后的答案。

一行，输入 $N$，$P$。

输出对 $10^9+7$ 取模后的答案

• $1\le N\le 10^9$
• $2\le P\le 10^9$

样例 1 解释

序列 $(1,1,2)$ 和 $(2,2,1)$ 满足条件。