蝴蝶效应

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

蝴蝶效应是气象学家洛伦兹1963年提出来的。其大意为:一只南美洲亚马孙河流域热带雨林中的蝴蝶,偶尔扇动几下翅膀,可能在两周后引起美国德克萨斯引起一场龙卷风。其原因在于:蝴蝶翅膀的运动,导致其身边的空气系统发生变化,并引起微弱气流的产生,而微弱气流的产生又会引起它四周空气或其他系统产生相应的变化,由此引起连锁反应,最终导致其他系统的极大变化。此效应说明,事物发展的结果,对初始条件具有极为敏感的依赖性,初始条件的极小偏差,将会引起结果的极大差异。

我们将问题简化为方程 f(x) = (a*f(max(0,x-b)) + c*f(max(0,x-d)))%1000000007

现在给出不同的f(0)n以及参数a,b,c,d,计算出f(n)

Input

多组输入。

对于每组数据,有六个个整数n,f0(1 <= n <= 100001 <= f0 <= 10000)a,b,c,d(1 <= a,b,c,d <= 10000)

Output

对于每组数据输出f(n)

Sample Input

1 2 3 4 5 6

Sample Output

16

Hint

 

Source

zmx