分数: 650 点
问题陈述
我们称正整数 n 一个好整数当且仅当其正除数之和可被整除 3.
给你两个正整数 N 和 M。求模数 998244353,长度-M 序列 A 的正整数,使得以下元素的乘积 A 是一个不超过的好整数 N.
约束
- 1 \leq N \leq 10^{10}
- 1 \leq M \leq 10^5
- N 和 M 是整数。
输入
输入由标准输入按以下格式给出:
N M
输出
打印答案。
示例输入 1
10 1
示例输出 1
5
满足条件的序列有五个:
- (2)
- (5)
- (6)
- (8)
- (10)
示例输入 2
4 2
示例输出 2
2
有两个序列满足条件:
- (1, 2)
- (2, 1)
示例输入 3
370 907
示例输出 3
221764640
示例输入 4
10000000000 100000
示例输出 4
447456146