問題文

$N$ 個のアイテムと、$K$ 個のナップザックがあります。
アイテムには $1$ から $N$ までの番号が振られており、ナップザックには $1$ から $K$ までの番号が振られています。
アイテム $i$ の重さは $w_i$ で、価値は $v_i$ です。

すたーと君は、それぞれのナップザックにいくつかのアイテムを入れます。
何も入れないナップザックがあっても構いませんが、
どのナップザックについても、入れるアイテムの重さの合計が $3$ 以下になるようにします。

このとき、$K$ 個のナップザックに入れるアイテムの価値の総和を、最大でいくらにできるでしょうか？

$w_i$ と $v_i$ はパラメータ $seed, a, b, m$ を使った漸化式によって定められます。
具体的には、% を余り演算としたとき
$f_1 = seed$
$f_{i + 1} = (a \times f_i + b)$ % $m$; $1 \le i \lt 2N$
という漸化式で数列 $(f_1, \cdots, f_{2N})$ を生成したのち、$i = 1, \cdots, N$ について
$w_i = f_i$ % $3 + 1$
$v_i = w_i \times f_{N + i}$
と定めます。

入力

$N$ $K$ $seed$ $a$ $b$ $m$

入力は整数
$1 \le K \le N \le 10^6$
$3 \le m \le 10^9$
$1 \le a \lt m$
$1 \le b \lt m$
$1 \le seed \lt m$

出力

価値の総和の最大値を表す整数を $1$ 行に出力してください。
最後に改行してください。

サンプル

6 2 15 26 31 97

536

100 25 5049654 306283215 360320319 370412443

21985715485