给定一个一元二次函数 $f(x) = ax^2 + bx+c$。对于满足 $1 \leq i \leq n$ 的 $n$ 个正整数 $i$，相应的二次函数值分别为 $f(1), f(2), \cdots, f(n)$。在通常情况下,它们的乘积 $\displaystyle \prod_{i=1}^n f(i)$ 不是一个平方数。能整除这个乘积的最大平方数是多少呢?

最大平方数问题：对于给定的一元二次函数 $f(x) = ax^2 + bx + c$，计算出能整除 $\displaystyle \prod_{i=1}^n f(i)$ 的最大平方数。

输入格式

输入的第一行有四个整数 $a, b, c, n,$，分别表示给定的一元二次函数 $f(x)=ax^2+bx+c$ 的相应系数为 $a,b,c$，以及乘积的项数为 $n$。

输出格式

输出能整除 $\prod_{i=1}^n f(i)$ 的最大平方数，对 $998\,244\,353$ 取模的结果。

样例数据

样例输入

1 2 3 4

样例输出

2916

子任务

测试数据中 $100\%$ 的数据满足 $1 \leq a,n \leq 2 \times 10^5$，$0 \leq b, c \leq 2 \times 10^5$ 。