제곱수 찾기

프랭크는 제곱수를 좋아한다. 제곱수는 어떤 정수를 자기 자신과 곱한 수이다. 그는 이차 다항식도 좋아하며, 가장 좋아하는 다항식은 $p(x) = a \cdot x^2 + b \cdot x + c$이다.

오늘 아침 프랭크는 이 다항식에 0부터 시작하는 연속된 정수 $n$개를 대입하고, 얻은 값을 모두 곱했다.

곱한 결과가 제곱수이면 그의 하루는 완벽하겠지만, 그렇지 않을 수도 있다. 그래서 그는 곱한 결과를 나누는 가장 큰 제곱수를 구해 달라고 부탁한다.

입력의 첫 줄에 정수 $a, b, c, n$이 주어진다 ($1 \le a,b,c,n \le 600\,000$).

$\prod\limits_{i=0}^{n-1}{p(i)}$의 약수 중 가장 큰 제곱수를 구한다. 이 값은 매우 클 수 있으므로, $10^9+7$로 나눈 나머지를 정수 하나로 출력한다.

첫 번째 예시에서 곱은 $1\cdot 3\cdot 7\cdot 13\cdot 21\cdot 31\cdot 43\cdot 57\cdot 73\cdot 91 = 2893684641939 = 38826291 \cdot 273^2$와 같다.