The input to a program is a set of operations with the queue. Each operation is either addition or removal of an item to or from the queue. After each operation find the smallest among all the numbers in a queue. Add up all the resulting numbers and get an answer. If after any operation the queue is empty, then add nothing to the answer. If it is impossible to remove an item because the queue is empty, then do nothing.

Input

The input data will be generated in your program. You will be given some parameters to get the input sequence.

The first input number n (1 ≤ n ≤ 106) is the number of operations with the queue. Then four nonnegative integers a, b, c, x0 are given. Their values are not greater than 10000.

Let's generate the input sequence x.

The first number of input sequence is x1. The first and each next number can be evaluated from the previous number using the formula:

xi = (a * xi-1 * xi-1 + b * xi-1 + c) / 100 mod 106,

where "/" is an integer division, 'mod' is the remainder from division.

If xi mod 5 < 2, you must delete the number from the queue, otherwise add number xi to the queue.

Output

Print the resulting sum.