Задача C. Делители

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:3 сек
Входной файл:divisors.in   Ограничение памяти:256 Мб
Выходной файл:divisors.out  
Максимальный балл:100  

Условие

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

Будем называть нормальным набор из k чисел (a1, a2, , ak), если выполнены следующие условия:

  1. каждое из чисел ai является делителем числа n;
  2. выполняется неравенство a1 < a2 < … < ak;
  3. числа ai и ai+1 для всех i от 1 до k − 1 являются взаимно простыми;
  4. произведение a1 a2… ak не превышает n.

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

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

Система оценивания

Правильные решения для тестов, в которых n ≤ 1000 и k = 2, оцениваются из 30 баллов.

Правильные решения для тестов, в которых k = 2, оцениваются из 60 баллов (в эти баллы включаются также 30 баллов для случая n ≤ 1000 и k = 2).

Формат входного файла

Первая строка входного файла содержит два целых числа: n и k.

Формат выходного файла

В выходном файле должно содержаться одно число — количество нормальных наборов из k делителей числа n.

Ограничения

2 ≤ n ≤ 108

2 ≤ k ≤ 10

Примеры тестов

Входной файл (divisors.in) Выходной файл (divisors.out)
1
90 3
16
2
10 2
4

0.030s 0.006s 15