Paint the Ceiling

Generate n side lengths: s[0]=seed, s[i]=s[i−1]+1+((k*s[i−1]+b) mod m). Both the length and the width are chosen from these side lengths, and a roof with area≤area can be painted for free. Count the ordered (length, width) combinations: swapping length and width gives a different option, and a square is counted once.

输入格式

One line: seed n k b m area. 1≤n≤6000000; 1≤seed,k,b,m≤10⁹, 1≤area≤10¹⁸; every generated s[i] is guaranteed to be in 1..10⁹ as well. The original upper bound of 6,000,000 for n is not reduced; use exact integer comparisons.

输出格式

Output the single integer required by the problem.

样例 1

输入：

2 3 3 3 2 15

输出：

5

样例 2

输入：

1 1 1 1 1 1

输出：

1

样例 3

输入：

2 2 1 1 1 4

输出：

1

样例说明

The answers to the three public examples are, in order: 5; 1; 1. The examples were checked by independent enumeration, state search, or direct simulation.