分解回响

地鼠网的控制台上浮动着密密麻麻的光点——每一个光点代表一个监控节点，也就是矿区的一口井架。Echo说Zero用一种特殊的"能量分配"来决定每个节点的监控能力。

"节点编号是 $A^B$。"Echo调出其中一个节点的参数，屏幕上跳出一个天文数字，"它的监控能力等于这个数字的所有约数的总和。"

CC凑近屏幕，眉头皱成一团："约数...是啥子？"

"能整除它的所有正整数。"你说，"比如12的约数是1、2、3、4、6、12，加起来是28。"

"那 $A^B$ 不是大得离谱？"

"对，不能直接数。"你盯着那个数字，开始拆解，"先把 $A$ 拆开——分解成几个质数的乘积。比如 $A = p_1^{c_1} \times p_2^{c_2} \times ...$。那么 $A^B$ 就是每个质数的指数再乘 $B$。"

Echo在旁边补充："然后对每个质因子，它的约数和是一个等比数列——从 $p_i^0$ 加到 $p_i^{c_iB}$。用等比数列的求和公式，可以递归地快速算。"

你开始写。先分解 $A$ 的质因数，然后对每个质因子，用递归快速求等比数列的和——把指数拆开，像昨天处理大数乘法那样，一份一份地累加，每次加完都用模数修剪。

CC在旁边看着，忽然问："这些公式...你从哪里学的？"

"你逼我学的。"

"我啥子时候——"她顿了一下，嘴角动了一下，"算了。继续。"

她的问题没有问完。但你猜到了她想问什么：这些公式，这些思路，是从地球带来的，还是在这三个月里被迫学会的？

答案是：两者都有。但更重要的是——CC在你身边的时候，你学得更快。

屏幕上跳出了结果。地鼠网所有节点的能量值被标注出来——大部分是中等的黄光，只有一个是刺眼的红光。

"G-10。"你说，"权重最高。"

Echo的投影站在屏幕旁边，看着那个红点："它在等我。它知道我会来。"

"那就让它等。"CC说，"等我们把它的地鼠网拆了，看它还能等多久。"

题目描述

求 $\sigma(A^B) \bmod 9901$。$\sigma(n)$ 是 $n$ 的所有正约数之和。

输入格式

$A, B$（$A,B \le 5 \times 10^7$）。

输出格式

$\sigma(A^B) \bmod 9901$。

输入样例

2
3

输出样例

15

提示

• 先把 $A$ 分解成质因数的乘积。$A^B$ 的每个质因子的指数变成原来的 $B$ 倍。
• 对每个质因子，用等比数列求和公式计算贡献，然后把所有质因子的贡献乘起来。
• 等比数列和可以用递归快速求模——把指数拆开，像快速累加那样做。
• 注意模数 9901。

地鼠网的能量分布图在穹顶内投下血红的光斑。CC绕着控制台走了一圈，忽然停下来："如果G-10是核心...那其他节点就是幌子？"

"对。"Echo说，"Zero把大部分能量集中在G-10，其他地方是空的。"

"那我们就走空的地方。"CC说，"从外围切断它的能量供给，再进攻核心。"

你看着她的侧脸——苍白的皮肤，紧抿的嘴唇，还有眼睛里那种猎人发现猎物破绽时的光。

Echo："CC..."

"不用商量。"CC已经把数据刀拔出来，"我去安干扰器。你们算哪些节点最该切。"