被 3 整除

题目描述

我们把正整数 $n$ 称为好整数,当且仅当它的所有正因数之和能被 $3$ 整除。

给你两个正整数 $N$ 和 $M$。求长度为 $M$、元素均为正整数的序列 $A$ 中,满足 $A$ 中所有元素的乘积是一个不超过 $N$ 的好整数的序列个数,对 $998244353$ 取模。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$

输出格式

输出答案。

样例

10 1

5

满足条件的序列有以下五个:

$(2)$

$(5)$

$(6)$

$(8)$

$(10)$

4 2

2

满足条件的序列有以下两个:

$(1, 2)$

$(2, 1)$

370 907

221764640

10000000000 100000

447456146

数据范围

• $1 \le N \le 10^{10}$
• $1 \le M \le 10^5$
• $N$ 和 $M$ 是整数。