21651번 - Делители 다국어

Натуральное число a называется делителем натурального числа b, если b = ac для некоторого натурального числа c. Например, делителями числа 6 являются числа 1, 2, 3 и 6. Два числа называются взаимно простыми, если у них нет общих делителей кроме 1. Например, 16 и 27 взаимно просты, а 18 и 24 — нет.

Будем называть нормальным набор из k чисел (a₁, a₂, …, a_k), если выполнены следующие условия:

1. каждое из чисел ai является делителем числа n; 
2. выполняется неравенство a₁ < a₂ < … < a_k;
3. числа a_i и a_i+1 для всех i от 1 до k – 1 являются взаимно простыми; 
4. произведение a₁a₂…a_k не превышает n. 

Например, набор (2, 9, 10) является нормальным набором из 3 делителей числа 360.

Требуется написать программу, которая по заданным значениям n и k определяет количество нормальных наборов из k делителей числа n.

Первая строка входного файла содержит два целых числа: n и k (2 ≤ n ≤ 10⁸, 2 ≤ k ≤ 10).

Первая строка входного файла содержит два целых числа: n и k (2 ≤ n ≤ 108, 2 ≤ k ≤ 10).