Given a quadratic function $f(x) = ax^2 + bx + c$. For $n$ positive integers $i$ satisfying $1 \leq i \leq n$, the corresponding values of the quadratic function are $f(1), f(2), \dots, f(n)$. In general, their product $\displaystyle \prod_{i=1}^n f(i)$ is not a perfect square. What is the largest perfect square that divides this product?

Maximum Square Problem: For a given quadratic function $f(x) = ax^2 + bx + c$, calculate the largest perfect square that divides $\displaystyle \prod_{i=1}^n f(i)$.

Input

The first line of input contains four integers $a, b, c, n$, representing the coefficients $a, b, c$ of the given quadratic function $f(x) = ax^2 + bx + c$ and the number of terms $n$ in the product.

Output

Output the largest perfect square that divides $\prod_{i=1}^n f(i)$, modulo $998\,244\,353$.

Examples

Input 1

1 2 3 4

Output 1

2916

Subtasks

For $100\%$ of the test data, $1 \leq a, n \leq 2 \times 10^5$ and $0 \leq b, c \leq 2 \times 10^5$.