#P18769. JQU

JQU

JQU

著名的 mm 函数以一个非空字符串为参数,将其中每个字母循环后移一位。例如 m(a)=bm(a)=b、m(z)=am(z)=a、m(icpc)=jdqdm(icpc)=jdqd。

给定一个仅含小写拉丁字母的字符串。你可以在其中插入一些括号,并将部分字母 m 解释为上述函数,其余字母仍是普通字母。

例如,字符串 mama 可以变为 m(am(a)),把两个 m 都当作函数后得到 bc。也可以变为 m(am)a,只将第一个 m 当作函数,得到 bna。

函数的参数不能为空。 例如,不能通过把 m 当作空参数函数而从 my 得到 y。

求能够得到的字典序最大的字符串,以及得到该最大字符串的方案数。方案数可能很大,输出它对 998244353998244353 取模的结果。

输入格式

一行字符串 ss,仅含小写拉丁字母,1≤∣s∣≤5121\le|s|\le512。

输出格式

输出最大字符串和方案数,二者以空格分隔。

样例

样例1

输入:

icpc

输出:

icpc 1

样例2

输入:

mma

输出:

nb 1

样例3

输入:

mmyx

输出:

nzy 1