题目描述

给定一个包含 $\texttt{A} \sim \texttt{Z}$ 和 $\texttt{*}$ 的字符串 $S$。

首先，你需要将 $S$ 中的所有 $\texttt{*}$ 从左到右依次替换为 $\texttt{A},\texttt{B},\cdots,\texttt{Z},\texttt{A},\texttt{B},\cdots,\texttt{Z},\texttt{A},\cdots$，得到新的字符串 $T$。

如对于字符串 $S=\texttt{A**B*}$，替换后变为 $T=\texttt{AABBC}$。

接着，你需要计算一个数

$$H=\left(\sum_{i=1}^{|T|} (\operatorname{ord}(T_i)-1) \cdot 26^{|T|-i}\right) \bmod 2^{32}$$

其中 $\operatorname{ord}(T_i)$ 表示 $T_i$ 在所有大写字母中是在第几位，如 $\operatorname{ord}(\texttt{A})=1,\operatorname{ord}(\texttt{D})=4$。

你需要求出替换后的 $T$ 和 $H$ 的值。

输入格式

一行一个字符串 $S$。

输出格式

第一行一个字符串 $T$。

第二行一个整数 $H$。

样例

A**B*

AABBC
704

说明/提示

对于 $100\%$ 的数据：

• $1 \le |S| \le 10^6$；
• $S_i$ 为 $\texttt{A} \sim \texttt{Z},\texttt{*}$ 中的一个。

本题开启捆绑测试。

• Subtask #1（$10 \ \text{pts}$）：$S_i$ 不为 $\texttt{*}$。
• Subtask #2（$10 \ \text{pts}$）：$|S| \le 1000$。
• Subtask #3（$80 \ \text{pts}$）：无特殊限制。