#P6938. 回文串

    ID: 6769 传统题 2000ms 512MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF2900省选/NOI-对称性分析字符串周期莫比乌斯反演狄利克雷卷积交换求和顺序杜教筛整除分块筛法计算积性函数按不动点计数等比数列求和快速幂模逆元

回文串

题目描述

若字符串 SS 的每个字符都是 [1,C][1,C] 内的整数,并且 SS 可以由两个非空回文串拼接得到,就称 SS 是双回文串。

求长度不超过 NN 的不同双回文串的个数。若同一个字符串可以在不同位置拆成两个回文串,仍只计一次。

输入格式

一行两个正整数 N,CN,C。

输出格式

一行一个非负整数,表示答案对 109+710^9+7 取模后的结果。

数据范围

1≤N≤1091\le N\le10^9,2≤C≤1092\le C\le10^9。原赛时间限制 22 秒,内存限制 512512 MB。

原赛采用捆绑测试。

子任务 特殊限制 原赛分值
1 N≤15N\le15,C=2C=2 7
2 N≤18N\le18 15
3 N≤300N\le300 23
4 N≤106N\le10^6 27
5 无 28

原 PDF 题面