題目描述

棟棟最近迷上了隨機算灋，而亂數是生成隨機算灋的基礎。 棟棟準備使用線性同餘法(Linear Congruential Me thod)來生成一個隨機數列，這種方法需要設定四個非負整數參數$m，a，c，X[0]$，按照下麵的公式生成出一系列亂數$X[n]\times X[n+1]=(a\times X[n]+c)$ $mod$ $m$其中$mod$ $m$表示前面的數除以$m$的餘數。 從這個式子可以看出，這個序列的下一個數總是由上一個數生成的。 用這種方法生成的序列具有隨機序列的性質，囙此這種方法被廣泛地使用，包括常用的C++和Pascal的產生亂數的庫函數使用的也是這種方法。 棟棟知道這樣產生的序列具有良好的隨機性，不過心急的他仍然想儘快知道$X[n]$是多少。 由於棟棟需要的亂數是$0,1，…，g-1$之間的，他需要將X[n]除以$g$取餘得到他想要的數，即$X[n]$ $mod$ $g$，你只需要告訴棟棟他想要的數$X[n]$ $mod$ $g$是多少就可以了。

輸入格式

$6$個用空格分割的整數$m，a，c，X[0]，n$和$g$，其中$a，c，X[0]$是非負整數，$m，n，g$是正整數.

輸出格式

輸出一個數，即$X[n]$ $mod$ $g$.

樣例

11 8 7 1 5 3

2

樣例說明

計算得$X[n]=X[5]=8$，故$(X[n]$ $mod$ $g)=(8$ $mod$ $3)=2$

數據規模與約定

對於所有數據：$n\ge 1，m\ge 1，a\ge 0，c\ge 0，X[0]\ge 0，g\ge 1$，$g\le10^8$