使用Python编写程序，查找由m个字母组成的长度为n的字符串，该字符串不包含长度大于1的回文子字符串。

假设我们有m个字母和另一个值n。我们必须计算长度为n的字符串数量，这些字符串是由从这些m个字母中挑选的字母组成的，且字符串没有长度大于1的回文子字符串。如果答案太大，则将结果模除10 ^ 9 + 7。

因此，如果输入为n = 2，m = 3，则输出为6，因为m = 3，因此如果字母表为{x，y，z}，我们可以生成像这样的字符串：[xx，xy，xz，yx，yy，yz，zx，zy，zz]，但[xx，yy，zz]无效，因此有6个字符串。

要解决此问题，我们将按照以下步骤进行设置−

• p：= 10 ^ 9 + 7
• 如果n与1相同，则
  • 返回m mod p
• 如果n等于2，则
  • 返回m *（m-1）mod p
• 如果m ≤ 2，则
  • 返回0
• 返回m （m-1）（（m-2）^（n-2）mod p）mod p

例子

让我们看下面的实现，以便更好地理解−

def solve(n, m):
   p = 10 ** 9 + 7
   if n == 1:
       return m % p
   if n == 2:
       return m * (m - 1) % p
   if m <= 2:
       return 0
   return m * (m - 1) * pow(m - 2, n - 2, p) % p

n = 2
m = 3
print(solve(n, m))

输入

3，[1,2,3,4,1]

输出

6