#P18769. JQU
JQU
JQU
著名的 函数以一个非空字符串为参数,将其中每个字母循环后移一位。例如 、、。
给定一个仅含小写拉丁字母的字符串。你可以在其中插入一些括号,并将部分字母 m 解释为上述函数,其余字母仍是普通字母。
例如,字符串 mama 可以变为 m(am(a)),把两个 m 都当作函数后得到 bc。也可以变为 m(am)a,只将第一个 m 当作函数,得到 bna。
函数的参数不能为空。 例如,不能通过把 m 当作空参数函数而从 my 得到 y。
求能够得到的字典序最大的字符串,以及得到该最大字符串的方案数。方案数可能很大,输出它对 取模的结果。
输入格式
一行字符串 ,仅含小写拉丁字母,。
输出格式
输出最大字符串和方案数,二者以空格分隔。
样例
样例1
输入:
icpc
输出:
icpc 1
样例2
输入:
mma
输出:
nb 1
样例3
输入:
mmyx
输出:
nzy 1