시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
6 초 512 MB 5 1 1 20.000%

문제

Frank likes square numbers. That is numbers, which are the product of some integer with itself. Also Frank likes quadratic polynomials. He even has his favorite one: $p(x) = a \cdot x^2 + b \cdot x + c$. 

This morning Frank evaluated his favorite quadratic polynomial for $n$ consecutive integer arguments starting from $0$ and multiplied all the numbers he got.

If the resulting product is a square, his day is just perfect, but that might be not the case. So he asks you to find the largest square number which is a divisor of the resulting product.

입력

The only line of the input contains 4 integers $a, b, c, n$ ($1 \le a,b,c,n \le 600\,000$). 

출력

Find the largest square divisor of $\prod\limits_{i=0}^{n-1}{p(i)}$. As this number could be very large, output a single integer --- its remainder modulo $10^9+7$.

예제 입력 1

1 1 1 10

예제 출력 1

74529

예제 입력 2

1 2 1 10

예제 출력 2

189347824

힌트

In the first example, the product is equal to $1\cdot 3\cdot 7\cdot 13\cdot 21\cdot 31\cdot 43\cdot 57\cdot 73\cdot 91 = 2893684641939 = 38826291 \cdot 273^2$.