该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

AT_abc370_g [ABC370G] Divisible by 3

题目描述

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

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

输入格式

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

输出格式

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

样例 1

输入

10 1

输出

5

样例 2

输入

4 2

输出

2

样例 3

输入

370 907

输出

221764640

样例 4

输入

10000000000 100000

输出

447456146

说明/提示

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

by @hxy0629