Zack 正在为他即将举办的编程竞赛感到担忧。具体来说，他担心参赛选手可能看过他之前组织的一场数学竞赛中的题目。直接询问新选手是否参加过他之前的比赛虽然简单，但这会向选手透露太多信息！于是，他想出了一个狡猾的计划。

首先，Zack 会要求选手提供一个字符串 $s$。然后，他会计算 $s$ 的所有长度为 5 的子序列，并统计其中有多少个是回文串。如果某个字符串作为 $s$ 的长度为 5 的子序列出现了多次，他会为每一次出现都进行计数。如果回文子序列的数量过多，他将禁止该选手参赛，否则他将允许他们通过。

不幸的是，Zack 在处理给定的一个字符串 $s$ 时遇到了困难。你能帮他计算 $s$ 中长度为 5 的回文子序列的数量吗？

由于该数值可能很大，请输出其对 $M$ 取模的结果。

输入格式

第一行包含字符串 $s$ ($1 \le |s| \le 10^6$)。你可以假设 $s$ 仅包含 ASCII 码在 33 到 126 之间的字符（所有这些字符均为可打印的非空白字符）。

接下来一行包含一个整数 $M$ ($2 \le M \le 10^9$)，即计算答案时所用的模数。

输出格式

输出一个整数，表示 $s$ 中长度为 5 的回文子序列的数量对 $M$ 取模的结果。

样例

样例输入 1

cmimccmimc
998244353

样例输出 1

34

样例输入 2

GoodLuckToday!!!(~.^)IHopeYouHaveFun!!
311

样例输出 2

69

样例输入 3

aaaaaa
1000000000

样例输出 3

6