問題文

正整数 $N,A,B,K$ が与えられます。

数列 $\{a_n\}$ を次のように定めます。

$\begin{array}{r}{a}_i=\{\begin{array}{ll}A& (i=1)\\ B& (i=2)\\ {\displaystyle \frac{{a_{i-1}}^2+K}{a_{i-2}}}& (i\ge 3)\end{array}\end{array}$

$\{a_n\}$ の第 $N$ 項 $a_N$ を求めてください。

$a_N$ は有理数になることが示せるので、これを以下に述べるように$\mathrm{mod}{10}^9+7$ で出力してください。

有理数を出力する際は、まずその有理数を分数 $\frac{y}{x}$ として表してください。

ここで、$x,y$ は整数であり、$x$ は ${10}^9+7$ で割り切れてはなりません (この問題の制約下で、そのような表現は必ず可能です)。

そして、$xz\equiv y\mathrm{mod}{10}^9+7$ を満たすような $0$ 以上 ${10}^9+6$ 以下の唯一の整数 $z$ を出力してください。

制約

入力

$NABK$

出力

$a_N$ を指示に従って出力してください。

最後に改行してください。

サンプル

5 5 3 1

888888897

100 1 2 3

837764073

314159265358 271828 161803 57721

449615573