#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/16/problems/G

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████

Divisor Chain - Repovive Premier Round 6 | Repovive | 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.

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

16G. Divisor Chain

Constraints

Input

Output

Samples

16G. Divisor Chain

Constraints

Input

Output

Samples