Counting Arrays

두 양의 정수 x와 y가 주어진다. 배열 F가 다음 조건을 만족할 때, 그리고 그럴 때에만 x의 y-인수분해라고 한다.

• F에는 y개의 원소가 있으며, 모두 정수이다;
• .

x의 y-인수분해인 서로 다른 배열의 개수를 구해야 한다. 두 배열 A and B에 대해, i (1 ≤ i ≤ y)인 인덱스 중 Ai ≠ Bi를 만족하는 것이 적어도 하나 존재할 때, 그리고 그럴 때에만 두 배열을 서로 다르다고 간주한다. 답이 매우 클 수 있으므로 109 + 7로 나눈 나머지를 출력한다.

첫째 줄에 해결해야 할 테스트 케이스의 개수를 나타내는 하나의 정수 q (1 ≤ q ≤ 105)가 주어진다.

이후 q개의 줄이 주어지며, 각 줄에는 두 정수 xi와 yi (1 ≤ xi, yi ≤ 106)가 주어진다. 각 줄은 하나의 테스트 케이스를 나타낸다.

q개의 정수를 출력한다. i-th 정수는 xi의 yi-인수분해 개수를 109 + 7로 나눈 나머지와 같아야 한다.

예제의 두 번째 테스트 케이스에는 여섯 개의 y-인수분해가 있다.

• { - 4, - 1};
• { - 2, - 2};
• { - 1, - 4};
• {1, 4};
• {2, 2};
• {4, 1}.