题目描述
「ひびき……你又胖了吧」あやか突然指出。
ひびき最近又胖了，为此她十分苦恼，于是找到健身教练まちお帮她指定减肥健身计划。
まちお建议ひびき每天做 $n$ 次仰卧起坐，但是ひびき认为这个动作很累，まちお便提出可以把这些运动分成若干组进行，并且每做完一组 $ai$ 次仰卧起坐都会积累 $F{a_i}$ 点 $\text{SilvermanGym}$ 的积分，且序列 $F$ 满足关系 $$ \begin{cases} F_n=n &n<2\ xFn=aF{n-1}+bF{n-2} & n\ge2 \end{cases} $$ 为了不让身体过负荷且能够起到减肥效果，ひびき只会正好做 $n$ 次，每一种分组的方案都会让ひびき得到 $\prod F{a_i}$ 点积分，现在她想知道所有方案能得到的积分的总和是多少。
输入格式
输入仅一行，包含四个整数 $n,\,x,\,a,\,b$ ，含义见题面。
输出格式
输出包含一个整数，表示所有健身方案的积分和，由于这个结果可能很大，所以ひびき只想知道这个答案对 $10^9+7$ 取模后的结果即可。
样例
input
3 1 1 1output
5
数据范围与提示
| 测试点编号 | $n\le$ | $x,a,b$ |
|---|---|---|
| $1$ | $8$ | $=1$ |
| $2\sim 3$ | $10^3$ | $=1$ |
| $4$ | $10^3$ | $10^9$ |
| $5\sim 7$ | $10^6$ | $10^9$ |
| $8\sim 10$ | $10^{18}$ | $10^9$ |
对于 $100\%$ 的数据，保证 $n\le10^{18},\;x,a,b\le10^9$