Description

Frank 喜欢平方数。平方数是指某个整数与自身相乘得到的数。Frank 还喜欢二次多项式，他尤其钟爱一个特定的二次多项式：$p(x) = a \cdot x^2 + b \cdot x + c$。

今天早上，Frank 用他最喜欢的二次多项式计算了从 $0$ 开始的连续 $n$ 个整数的值，并将所有结果相乘。

如果最终乘积是一个平方数，那么他今天就会非常开心。但实际情况可能并非如此。因此，他请你找出这个乘积的最大平方因数。

Input Format

输入仅有一行，包含 4 个整数 $a, b, c, n$（$1 \le a, b, c, n \le 600\,000$）。

Output Format

找出 $\prod\limits_{i=0}^{n-1}{p(i)}$ 的最大平方因数。由于这个数可能非常大，输出其对 $10^9+7$ 取模后的结果。

1 1 1 10

74529

1 2 1 10

189347824

Hint

在第一个样例中，乘积为 $1 \cdot 3 \cdot 7 \cdot 13 \cdot 21 \cdot 31 \cdot 43 \cdot 57 \cdot 73 \cdot 91 = 2893684641939 = 38826291 \cdot 273^2$。

翻译由 DeepSeek V3 完成