Problem1367--PIPI买菜Ⅲ

1367: PIPI买菜Ⅲ

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 65  Solved: 11
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI他又双来买菜了。
同样的,一共有n个菜摊,编号为1-n,且每个菜摊贩卖的菜品都有其对应的健康值。PIPI为了健康考虑,希望购买的菜品中健康值最大的与健康值最小的差不超过k。当然,PIPI的强迫症依然没有治好,他买过菜的菜摊,其编号必须连续。比如:他在1,3号菜摊买菜是不行的,因为1,3不连续,但是他在1,2,3号菜摊买菜则是可行的。
请问PIPI最多能在多少个菜摊买菜?

Input

第一行两个整数n与k,其中1<=n<=10^7,0<=k<=10^9。
第二行三个正整数A[0],b,c,按照A[i]=(A[i-1]*b+c)%10^9的规则生成1-n号菜摊菜品的健康值,其中A[0]bc<=10^9。

Output

输出一个数,表示PIPI最多能在多少个菜摊买菜。

Sample Input

4 2
1 1 1

Sample Output

3

Source/Category