← 返回题目列表

Codeforces · 1205/E

E. 再次期望值

中文机器翻译题面 查看原题

给定整数 $$$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$$$。