Score : $650$ points

问题陈述

我们称一个正整数 $n$ 为好整数，当且仅当它的正除数之和能被 $3$ 整除。 给定两个正整数 $N$ 和 $M$。找出长度为 $M$ 的正整数序列 $A$ 的数量，模 $998244353$，使得 $A$ 中元素的乘积是一个不超过 $N$ 的好整数。

以上为大语言模型 kimi 翻译，仅供参考。

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