给定整数 $$$n$$$、$$$k$$$。让我们考虑由 $$$k$$$ 不同元素组成的字母表。
设字符串$$$s$$$的美$$$f(s)$$$为索引$$$i$$$的个数,$$$1\le i<|s|$$$,其中长度为$$$i$$$的$$$s$$$的前缀等于长度为$$$i$$$的$$$s$$$的后缀。例如,字符串$$$abacaba$$$的美度等于$$$2$$$,对于$$$i = 1、3$$$长度$$$i$$$的前缀和后缀是相等的。
考虑给定字母表中长度为 $$$n$$$ 的所有单词。求随机均匀选择的单词 $$$f(s)^2$$$ 的期望值。我们可以证明它可以表示为 $$$\frac{P}{Q}$$$,其中 $$$P$$$ 和 $$$Q$$$ 互质,并且 $$$Q$$$ 不能除以 $$$10^9 + 7$$$。输出 $$$P\cdot Q^{-1} \bmod 10^9 + 7$$$。
输入
第一行也是唯一一行包含两个整数 $$$n$$$, $$$k$$$ ($$$1\le n \le 10^5$$$, $$$1\le k\le 10^9$$$) — 分别是字符串的长度和字母表的大小。
输出
输出单个整数 — $$$P\times Q^{-1} \bmod 10^9 + 7$$$。
示例
输入 #1
2 3
输出 #1
333333336
输入 #2
1 5
输出 #2
0
输入 #3
100 1
输出 #3
9801
输入#4
10 10
输出#4
412377396
注意
在第一个示例中,大小为 $$$3$$$ 的字母表中有 $$$9$$$ 长度为 $$$2$$$ 的单词 — $$$aa$$$、$$$ab$$$、$$$ac$$$、$$$ba$$$、$$$bb$$$、$$$bc$$$、$$$ca$$$、$$$cb$$$、 $$$cc$$$。其中 $$$3$$$ 的美丽值为 $$$1$$$,其中 $$$6$$$ 的美丽值为 $$$0$$$,因此平均值为 $$$\frac{1}{3}$$$。
在第三个例子中,只有一个这样的单词,并且它具有美感$$$99$$$,因此平均值为$$$99^2$$$。