Zack is concerned about his upcoming programming contest. In particular, he's concerned that the contestants might have seen some problems from a math contest that he had previously organized. It would be simple to ask the new contestants whether they had competed in his other contest, but that would give away too much information to the contestants! Instead, he has come up with the following devious plan.
First, Zack will ask a contestant for a string $$$s$$$. He will then compute all five-letter subsequences of $$$s$$$ and count how many of them are palindromic. If a certain string appears multiple times as a five-letter subsequence of $$$s$$$, he will count it once for each time it appears. If too many subsequences are palindromic, he will ban that contestant from competing, otherwise he will let them through.
Unfortunately, Zack has been having issues with executing this plan for one $$$s$$$ that has been given to him. Can you count the five-letter palindromic subsequences of $$$s$$$ for him?
As this value may be large, compute the answer modulo $$$M$$$.
The first line of input contains the string $$$s$$$ ($$$1 \leq |s| \leq 10^6$$$). You may assume that $$$s$$$ only contains characters with ASCII codes between $$$33$$$ and $$$126$$$ inclusive (all such characters are printable, non-whitespace characters).
This is followed by a line containing a single integer $$$M$$$ ($$$2 \leq M \leq 10^9$$$) — the modulo with which to compute your answer.
Output a single integer — the number of five-letter palindromic subsequences of $$$s$$$, modulo $$$M$$$.
cmimccmimc 998244353
34
GoodLuckToday!!!(~.^)IHopeYouHaveFun!! 311
69
aaaaaa 1000000000
6
