103706: [Atcoder]ABC370 G - Divisible by 3

Problem Statement

We call a positive integer $n$ a good integer if and only if the sum of its positive divisors is divisible by $3$.
You are given two positive integers $N$ and $M$. Find the number, modulo $998244353$, of length-$M$ sequences $A$ of positive integers such that the product of the elements in $A$ is a good integer not exceeding $N$.

Constraints

• $1 \leq N \leq 10^{10}$
• $1 \leq M \leq 10^5$
• $N$ and $M$ are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$

Output

Print the answer.

Sample Input 1

10 1

Sample Output 1

5

There are five sequences that satisfy the conditions:

• $(2)$
• $(5)$
• $(6)$
• $(8)$
• $(10)$

Sample Input 2

4 2

Sample Output 2

2

There are two sequences that satisfy the conditions:

• $(1, 2)$
• $(2, 1)$

Sample Input 3

370 907

Sample Output 3

221764640

Sample Input 4

10000000000 100000

Sample Output 4

447456146

问题陈述

如果且仅当正整数n的所有正约数之和能被3整除，我们称这个正整数n为好整数。
给你两个正整数N和M。找出长度为M的序列A的正整数个数，使得A中元素的乘积是一个不超过N的好整数，结果对998244353取模。

约束条件

• $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