Frank 喜欢完全平方数。也就是说，这些数是某个整数与自身的乘积。此外，Frank 还喜欢二次多项式。他甚至有自己最喜欢的一个：$p(x) = a \cdot x^2 + b \cdot x + c$。

今天早上，Frank 计算了他最喜欢的二次多项式在从 $0$ 开始的 $n$ 个连续整数自变量下的值，并将得到的全部数值相乘。

如果最终的乘积是一个完全平方数，他的这一天就会非常完美，但情况可能并非总是如此。因此，他请求你帮他找到能整除该乘积的最大完全平方数。

输入格式

输入唯一的一行包含 $4$ 个整数 $a, b, c, n$ ($1 \le a, b, c, n \le 600\,000$)。

输出格式

求出 $\prod_{i=0}^{n-1} p(i)$ 的最大完全平方数约数。由于这个数可能非常大，请输出一个单个整数——其对 $10^9 + 7$ 取模后的余数。

样例

输入样例 1

1 1 1 10

输出样例 1

74529

输入样例 2

1 2 1 10

输出样例 2

189347824

说明

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