#P7219. [2023省队模拟]回文

    ID: 7053 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2600省选/NOI-字符串周期按不动点计数莫比乌斯反演倍数枚举交换求和顺序

[2023省队模拟]回文

题目描述

定义一个非空串 SS 是回文的,当且仅当 SS 反转后得到的串 S′S' 与 SS 完全一致。

一个串 SS 是合法的,当且仅当它是回文串,或者可以由两个回文串拼接得到。例如,cftmtfcqwq 可以由 cftmtfc 和 qwq 两个回文串拼接得到,所以合法。 cftmtfc 本身就是回文串,所以也合法。 crying 无法由两个回文串拼接,且本身也不是回文串,所以不合法。

给定 n,kn,k,其中 kk 是字符集的大小。求长度不超过 nn 的合法串有多少个。答案对 998244353998244353 取模。

输入格式

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

输出格式

输出一个整数,表示答案对 998244353998244353 取模的结果。

样例输入 1

6 2

样例输出 1

114

样例输入 2

114 514

样例输出 2

250382807

数据范围与约定

对于全部数据,1≤n,k≤2×1061\le n,k\le 2\times10^6。

子任务 数据范围 分值
1 1≤n,k≤51\le n,k\le 5 10
2 k=1k=1 5
3 n≤105n\le 10^5 50
4 无特殊限制 35