Divisors

Time limit2sMemory limit512 MB

Summary

Count increasing sequences of k divisors of n where each adjacent pair is coprime and the product of all k numbers is at most n.

Level: Medium7 of 10
Topics: Dynamic programming, Number theory, Backtracking
Solved: No attempts yet

Problem

A natural number $a$ is a divisor of a natural number $b$ if $b = ac$ for some natural number $c$ . For example, the divisors of 6 are 1, 2, 3, and 6. Two numbers are called coprime if they have no common divisor other than 1. For example, 16 and 27 are coprime, while 18 and 24 are not.

A set of $k$ numbers $(a_1, a_2, \dots, a_k)$ is called normal if all of the following conditions hold:

Each $a_i$ is a divisor of $n$ .
$a_1 < a_2 < \dots < a_k$ .
For every $i$ from 1 to $k-1$ , $a_i$ and $a_{i+1}$ are coprime.
The product $a_1 a_2 \cdots a_k$ does not exceed $n$ .

For example, $(2, 9, 10)$ is a normal set of 3 divisors of 360.

Given $n$ and $k$ , count the normal sets of $k$ divisors of $n$ .

Input

The first line contains two integers $n$ and $k$ ( $2 \le n \le 10^8$ , $2 \le k \le 10$ ).

Output

Print one integer: the number of normal sets of $k$ divisors of $n$ .

Examples2

Example 1
Input
```
90 3
```
Expected output
```
16
```
Example 2
Input
```
10 2
```
Expected output
```
4
```