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