#1438. [L3-3] End Crystal

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: MCPlayer542

题目描述

MCPlayer542 想要复活末影龙。

在 MC 的 1.114514 版本的末地中有一列末影水晶,每个末影水晶都有一个编号,分别为 。每个末影水晶都有一个整数能量值

如果正确设定了末影水晶的初始能量值,末影龙的复活仪式就会开始。每隔一段时间,末影水晶的能量值都会产生如下变化:

编号为 的末影水晶吸收了所有编号为 的因数的末影水晶的能量,其能量变为被其吸收的所有末影水晶在上一瞬间的能量值之和,即

如果在经历了 次能量变化后,除了 号末影水晶能量值为 以外,其他所有末影水晶的能量值都变为了 ,则可以成功复活 只末影龙。

现在 MCPlayer542 想知道,如果想复活 只末影龙,那么前 个末影水晶的初始能量值之和 是多少。

输入格式

输入两个数,用一个空格分隔,即

输出格式

输出一行一个整数,表示答案。

样例

样例输入1

0 114514

样例输出1

1

样例输入2

1 10

样例输出2

998244352

样例输入3

327 542

样例输出3

433267855

样例输入4

1919810 114514

样例输出4

808572918

数据范围与提示

数据范围

的数据满足

的数据满足

的数据满足

的数据满足;

的数据满足

样例解释

样例1中,MCPlayer542 想要用仪式复活 只末影龙,因此只需要将 号末影水晶的初始能量值直接设为 ,其他的末影水晶初始能量值全部设为 即可。因此前 个末影水晶的初始能量值之和 得到的答案为

样例2中,MCPlayer542 想要用仪式复活 只末影龙,因此前个末影水晶的能量值应分别为

在下一次能量变化中,前个末影水晶的能量值的变化情况如下表:

编号 能量变化

故经历 次能量变化后仪式完成,可以成功复活 只末影龙。因此答案为