题目描述

「ひびき……你又胖了吧」あやか突然指出。

ひびき最近又胖了，为此她十分苦恼，于是找到健身教练まちお帮她指定减肥健身计划。

まちお建议ひびき每天做 $n$ 次仰卧起坐，但是ひびき认为这个动作很累，まちお便提出可以把这些运动分成若干组进行，并且每做完一组 $a_i$ 次仰卧起坐都会积累 $F_{a_i}$ 点 $\text{SilvermanGym}$ 的积分，且序列 $F$ 满足关系

$$\begin{cases} F_n=n &n<2\\ xF_n=aF_{n-1}+bF_{n-2} & n\ge2 \end{cases} $$

为了不让身体过负荷且能够起到减肥效果，ひびき只会正好做 $n$ 次，每一种分组的方案都会让ひびき得到 $\prod F_{a_i}$ 点积分，现在她想知道所有方案能得到的积分的总和是多少。

输入格式

输入仅一行，包含四个整数 $n,\,x,\,a,\,b$ ，含义见题面。

输出格式

输出包含一个整数，表示所有健身方案的积分和，由于这个结果可能很大，所以ひびき只想知道这个答案对 $10^9+7$ 取模后的结果即可。

样例

3 1 1 1

5

数据范围与提示

测试点编号	$n\le$	$x,a,b$
$1$	$8$	$=1$
$2\sim 3$	$10^3$
$4$		$10^9$
$5\sim 7$	$10^6$
$8\sim 10$	$10^{18}$

对于 $100\%$ 的数据，保证 $n\le10^{18},\;x,a,b\le10^9$