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

Будем называть нормальным набор из \(k\) чисел (\(a_1, a_2, \ldots, a_k\)), если выполнены следующие условия:

1. каждое из чисел \(a_i\) является делителем числа \(n\);
2. выполняется неравенство \(a_1 \lt a_2 \lt \ldots \lt a_k\);
3. числа \(a_i\) и \(a_{i+1}\) для всех \(i\) от \(1\) до \(k - 1\) являются взаимно простыми;
4. произведение \(a_1a_2\ldots a_k\) не превышает \(n\).

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

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

Рассматриваются все разбиения натурального числа \(N\) на сумму \(К\) неотрицательных слагаемых (\(1 \leq N \leq 32\), \(2 \leq K \leq 32\)). Суммы, отличающиеся только порядком слагаемых, считаем различными. Упорядочим все разбиения по убыванию первого слагаемого, а при равных первых слагаемых – по убыванию второго слагаемого, а при равных первых и вторых слагаемых – по убыванию третьего слагаемого и т. д. Пронумеруем их. Например, при \(N=4\), \(К=3\) имеем:

В парке растут два очень высоких дерева, на стволе каждого из которых расположены дупла одно под другим на равном расстоянии друг от друга. Однажды N дятлов решили заселить эти дупла. Некоторые из них знакомы и поэтому хотели бы иметь возможность летать друг к другу в гости. Дятлы летают прямолинейно и очень быстро. Чтобы уменьшить вероятность столкновения, они решили селиться по следующему принципу: