← 返回题目列表

AtCoder · abc370_g

G. 可被 3 整除

中文机器翻译题面 查看原题

分数: 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