#P12033. [2024年联测]怪物

    ID: 11182 传统题 1000ms 512MiB 尝试: 2 已通过: 1 难度: 7 上传者: 标签>CF2300数学数论组合数学筛法字符串前缀和

[2024年联测]怪物

题面描述

在你帮出题人打总力战的时候,出题人在看番。

憧憬会比剧毒更凶猛,比疾病更深切的猎杀着人们,一旦被其捕获,就在劫难逃,如同诅咒一般,但是冒险者们,依然义无反顾的为此献身,对他们来说失去憧憬的人生,比死亡更可怕。

所以憧憬 OI 的你决定做出这道题。

莉可在深渊底层寻找一个字符串 SS ,你找到一个数 f(S)f(S) 与一头怪物。

记 nn 为 SS 的长度,S[l,r]S[l,r] 为 SlSl+1...Sr−1SrS_lS_{l+1}...S_{r-1}S_r。

这头怪物告诉你,它已经将字符串 SS 变为了数 f(S)f(S) ,具体等于 满足 2≤i≤n,S[1,i]=S[n−i+1,n]2\leq i\leq n,S[1,i]=S[n-i+1,n] 的 ii 的个数。

现在它告诉了你 nn 和 SS 的字符集大小 kk ,如果你能求出 f2(S)f^2(S) 的期望值对 109+710^9+7 取模,它就会把 f(S)f(S) 变回 SS,否则它会跟莉可做一些羞羞的事情后生下一只可莉。

输入格式

一行两个整数 n,kn,k。

输出格式

一行一个整数表示 f2(S)f^2(S) 的期望值。

数据范围

对于 100%100\% 的数据,1≤n≤1071\leq n\leq10^7,1≤k≤1091\leq k\leq10^9。

测试点编号 n≤n\leq k≤k\leq
1∼31\sim3 88
4∼54\sim5 10710^7 11
6∼106\sim10 20002000 10910^9
11∼1211\sim12 2×1042\times 10^4
13∼1513\sim15 10510^5
16∼1716\sim17 10610^6
18∼2018\sim20 10710^7