A41230.KMP算法

小明和小王是好朋友，他们正在一起学习字符串算法。今天，小明在学习 KMP 算法时遇到了一个难题：给定一个只包含大写字母的字符串$s$，问这个字符串中有多少个子序列等于 $\text{"KMP"}$。小明想了很久，还是没有思路。

小王看到小明苦恼的样子，决定帮她简化问题。他告诉小明：数据保证字符串中的字符 M 只出现一次，这样问题应该会简单一些。 但即便如此，小明还是不知道如何解决这个问题。于是，小王决定请你来帮助小明，告诉她这个问题的答案。

$\large{数据范围}$

• $1 \leq |s| \leq 10^3$，其中 $|s|$是 $s$ 字符串的长度
• 字符串中只包含大写字母

输入一个字符串占一行。

输出一个数字占一行，表示答案

样例中 $\text{"KMP"}$ 作为子序列出现了 $2$ 次，对应的下标(假设从1开始)为 $[1, 2, 3]$ 和 $[1, 2, 4]$。