#P7219. [2023省队模拟]回文
[2023省队模拟]回文
题目描述
定义一个非空串 是回文的,当且仅当 反转后得到的串 与 完全一致。
一个串 是合法的,当且仅当它是回文串,或者可以由两个回文串拼接得到。例如,cftmtfcqwq 可以由 cftmtfc 和 qwq 两个回文串拼接得到,所以合法。 cftmtfc 本身就是回文串,所以也合法。 crying 无法由两个回文串拼接,且本身也不是回文串,所以不合法。
给定 ,其中 是字符集的大小。求长度不超过 的合法串有多少个。答案对 取模。
输入格式
第一行两个正整数 。
输出格式
输出一个整数,表示答案对 取模的结果。
样例输入 1
6 2
样例输出 1
114
样例输入 2
114 514
样例输出 2
250382807
数据范围与约定
对于全部数据,。
| 子任务 | 数据范围 | 分值 |
|---|---|---|
| 1 | 10 | |
| 2 | 5 | |
| 3 | 50 | |
| 4 | 无特殊限制 | 35 |