AT_abc370_g [ABC370G] Divisible by 3

题目描述

称正整数 $x$ 是好的，当且仅当 $x$ 的约数之和是 $3$ 的倍数。

给定 $n,m$，求有几个长度为 $m$ 的正整数序列，设其积为 $s$，满足 $s\le n$ 且 $s$ 是好的，答案对 $998244353$ 取模。

输入格式

一行两个正整数：$n,m$。

输出格式

一行一个整数，表示答案。

输入输出样例 #1

输入 #1

10 1

输出 #1

5

输入输出样例 #2

输入 #2

4 2

输出 #2

2

输入输出样例 #3

输入 #3

370 907

输出 #3

221764640

输入输出样例 #4

输入 #4

10000000000 100000

输出 #4

447456146

说明/提示

$1\le n\le 10^{10},1\le m\le 10^5$。

by @hxy0629