我们称一个字符串为“好字符串”，当且仅当该字符串不包含长度大于 $2$ 的回文子串。
现在我们想知道，在所有长度恰好为 $n$ 且字符集大小为 $m$ 的字符串中，有多少个不同的好字符串（不一定需要使用字符集中的所有字符）。
输入格式
仅一行，包含两个整数 $n, m$ ($1 \le n \le 10^6, 1 \le m \le 10^9$)。
输出格式
输出一个整数，表示不同的好字符串的数量，答案对 $1000000007$ 取模。
样例
输入样例 1
3 3
输出样例 1
18
QOJ.ac
QOJ
حد الوقت: 1.0 s
حد الذاكرة: 256 MB
مجموع النقاط: 100
قابلة للهجوم ✓
#15201. 好的字符串
الإحصائيات
تم استخدام هذه المسألة في المسابقات التالية:
AI Translation —
This statement was translated using AI and may contain inaccuracies. Please refer to the original statement if in doubt.
Discussions
About Discussions
The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.
This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.
Open Discussions 0
No discussions in this category.
Issues
About Issues
If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.
Guidelines:
- This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
- Do not submit duplicated issues.
- Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.