C. 子序列

给定一个长度为 \( n \) 的非负整数序列 \( a_1,a_2,a_3,\cdots , a_n \)，求出和不小于\(S \)的连续子序列\( a_l,a_{l+1},\cdots,a_r (1\leq l \leq r \leq n)\)的最短长度，即满足\( \sum_{i=l}^r a_i \geq S \)的最短连续子序列长度。

由于序列可能很长，以生成的方式给出序列：给出序列的首项\( a_1\)和一个乘数\( b\)，序列其余各项的值为 \( a_i = (b \cdot a_{i-1} ) \mod (10^9 + 7) (1 < i \leq n)\) 。

输入格式

第一行两个整数 \( n,S (3\leq n \leq 5 \times 10^7, 1\leq S \leq 10^18) \)，代表序列长度以及序列和的限制。

第二行给出两个整数\( a_1, b (0 \leq a,b < 10^9 + 7) \) ，含义如题目描述。

• 对于\( 10\% \)的数据，\(1 \leq n \leq 500\)
• 对于\( 30\% \)的数据，\(1 \leq n \leq 10^4\)
• 对于\( 65\% \)的数据，\(1 \leq n \leq 2\times 10^6\)
• 对于\( 100\% \)的数据，\(3\leq n \leq 5 \times 10^7\)

输出格式

一行一个整数，代表满足要求的连续子序列的最短长度。如果和不小于 \(S\) 的连续序列不存在，输出 \(-1\)。

测试样例

样例1

Input

3 6
1 2

Output

2

Hint：实际序列为 \( 1,2,4 \)

样例2

Input

5 1743745293
714636908 681692770

Output

3

Hint:实际序列为 714636908, 948615497, 288206443, 85239381, 340225887。

样例3

Input

3 8
1 2

Output

-1

Hint：实际序列为 \( 1,2,4 \)