問題文

線形合同法はひと昔前の乱数生成によく使われていた方法です。 周期が長くないため、現在ではあまり使われていません。

線形合同法ではパラメータ $M, a, b, c$ を決め、乱数列 $x_n$ を次のように定義します。

この問題においては、 $M = 998244353$ とします。

$T$ 個のテストケースに対して、以下の問題の答えを出力してください。

• $a, b, c, n$ が与えられたとき、乱数列の $n$ 番目の値 $x_n$ を答えてください。

制約

• $1 \le T \le 10^{5}$
• $0 \le a_i, b_i, c_i, n_i \le 10^9$
• 入力は全て整数である

入力

出力

$T$ 行出力してください。 $i = 1, 2, \ldots, T$ について、 $i$ 行目には $i$ 番目のテストケースの答えを出力してください。

入出力例

5
2 1 1 5
1 3 3 3
15311432 0 1 8388608
3 1 1 1000000000
123 456 789 10

63
12
1
351549422
639657991