Problem11152--ABC370 - G - Divisible by 3

11152: ABC370 - G - Divisible by 3

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

SubmitSolved: 2Submit Num: 3StatisticsShowOff!

Description

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

Input

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

$N$ $M$

Output

Print the answer.

Constraints

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

Sample 1 Input 

10 1

Sample 1 Output 

5

There are five sequences that satisfy the conditions:

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

Sample 2 Input 

4 2

Sample 2 Output 

2

There are two sequences that satisfy the conditions:

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

Sample 3 Input 

370 907

Sample 3 Output 

221764640


10000000000 100000


447456146

Source/Category

 
Submit