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