#6704. 健身计划

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: SilveryStar

题目描述

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

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

まちお建议ひびき每天做 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