Вам заданы два целых положительных числа x и y. Массив F называется y-факторизацией числа x тогда и только тогда, когда выполняется следующие условия:
- В массиве F ровно y элементов, все они являются целыми числами;
-
.
Посчитайте количество попарно различных массивов, являющихся y-факторизациями числа x. Два массива A и B считаются различными, если существует хотя бы одна позиция i (1 ≤ i ≤ y) такая, что Ai ≠ Bi. Так как ответ может быть очень большим, выведите его по модулю 109 + 7.
В первой строке записано одно целое число q (1 ≤ q ≤ 105) — количество запросов.
Затем идут q строк, в каждой записаны по два целых числа xi и yi (1 ≤ xi, yi ≤ 106). Каждая из этих строк представляет собой один запрос.
Выведите q целых чисел. i-е число должно быть ровно количеству yi-факторизаций числа xi по модулю 109 + 7.
2
6 3
4 2
36
6
Во втором запросе из примере есть 6 y-факторизаций:
- { - 4, - 1};
- { - 2, - 2};
- { - 1, - 4};
- {1, 4};
- {2, 2};
- {4, 1}.
