Divisor Chain - Repovive Premier Round 6 | Repovive

16G. Divisor Chain

3000 pts2s512 MB

You are given three positive integers $n$ , $m$ , and $k$ . You need to find the number of arrays $a$ of length $n$ that satisfy the following conditions:

$1 \le a_i \le m$ for all $1 \le i \le n$ .
The sequence of prefix greatest common divisors (GCD) of array $a$ contains exactly $k$ distinct values.

Formally, let $p_i = \gcd(a_1, a_2, \dots, a_i)$ for $1 \le i \le n$ . The size of the set $\{p_1, p_2, \dots, p_n\}$ must be exactly $k$ .

Since the answer can be very large, output it modulo $998244353$ .

Constraints

$1 \le n \le 10^{18}$
$1 \le m \le 10^5$
$1 \le k \le 20$

Input

$n \quad m \quad k$

Output

$ans$

Samples

Input

2 3 2

Explanation

The array length is $2$ and the elements are chosen from $\{1, 2, 3\}$ . The prefix GCD sequence must contain exactly $2$ distinct values, which means $p_1 \neq p_2$ . The valid arrays $a$ and their corresponding prefix GCD sequences $p$ are:

$a = [2, 1] \implies p = [2, 1]$
$a = [2, 3] \implies p = [2, 1]$
$a = [3, 1] \implies p = [3, 1]$
$a = [3, 2] \implies p = [3, 1]$

There are $4$ valid arrays in total.

Output

Input

10 100 20

Explanation

The maximum possible number of distinct prefix GCDs for elements up to $100$ is $7$ (for example, the division chain $64 \to 32 \to 16 \to 8 \to 4 \to 2 \to 1$ ). It is mathematically impossible to have $k=20$ distinct values, so the answer is $0$ .

Output

Input

6 6 3

Output

You are given three positive integers $n$ , $m$ , and $k$ . You need to find the number of arrays $a$ of length $n$ that satisfy the following conditions:

$1 \le a_i \le m$ for all $1 \le i \le n$ .
The sequence of prefix greatest common divisors (GCD) of array $a$ contains exactly $k$ distinct values.

Formally, let $p_i = \gcd(a_1, a_2, \dots, a_i)$ for $1 \le i \le n$ . The size of the set $\{p_1, p_2, \dots, p_n\}$ must be exactly $k$ .

Since the answer can be very large, output it modulo $998244353$ .

$1 \le n \le 10^{18}$
$1 \le m \le 10^5$
$1 \le k \le 20$

$n \quad m \quad k$

$ans$

$a = [2, 1] \implies p = [2, 1]$
$a = [2, 3] \implies p = [2, 1]$
$a = [3, 1] \implies p = [3, 1]$
$a = [3, 2] \implies p = [3, 1]$

There are $4$ valid arrays in total.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

16G. Divisor Chain

Constraints

Input

Output

Samples

16G. Divisor Chain

Constraints

Input

Output

Samples