Натуральное число \(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\).

Даны натуральные числа a, b, c. Если уравнение ax+by=c имеет решения в целых числах, то выведите через пробел НОД(a,b), x и y (какое-нибудь решение). Если решения не существует, то выведите слово Impossible.

Найдите наименьшее общее кратное всех целых чисел от \(1\) до \(N\). Наименьшим общим кратным натуральных чисел \(a_1\),\(a_2\),…,\(a_k\) называется число \(A\), такое что \(А\) делится на \(a_i\) для всех \(i\) от \(1\) до \(k\), причем \(A\) – наименьшее натуральное число, обладающее этим свойством.